1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
|
#include "newtonpolytope.h"
#include "lp.h"
void removeNonExtremeVerticesOfPolytope(IntegerVectorList &polytope)
{
if(polytope.empty())return;
int n=polytope.begin()->size();
for(IntegerVectorList::iterator j=polytope.begin();j!=polytope.end();j++)
{
j->resize(n+1);
(*j)[n]=1;
}
for(IntegerVectorList::iterator j=polytope.begin();j!=polytope.end();j++)
if(!isFacet(polytope,j))
{
IntegerVectorList::iterator k=j;
j++;
polytope.erase(k);
j--;
}
for(IntegerVectorList::iterator j=polytope.begin();j!=polytope.end();j++)
j->resize(n);
}
IntegerVectorList newtonPolytope(Polynomial const &p)
{
IntegerVectorList polytope;
for(TermMap::const_iterator i=p.terms.begin();i!=p.terms.end();i++)
{
polytope.push_back(i->first.exponent);
}
removeNonExtremeVerticesOfPolytope(polytope);
return polytope;
}
/*
This routine should be split into several so that it can also handle closed cones and tropical hypersurfaces.
*/
HalfOpenConeList normalFan(int dimension, IntegerVectorList l, TermOrder const &t)
{
HalfOpenConeList ret;
removeNonExtremeVerticesOfPolytope(l);
for(IntegerVectorList::const_iterator i=l.begin();i!=l.end();i++)
{
IntegerVectorList strictList,nonStrictList;
for(IntegerVectorList::const_iterator j=l.begin();j!=l.end();j++)
if(j!=i)
{
IntegerVector v=*i-*j;
if(t(*i,*j))//we don't need to find the facets, right?
strictList.push_back(v);
else
nonStrictList.push_back(v);
IntegerVectorList empty;
ret.push_back(HalfOpenCone(dimension,empty,nonStrictList,strictList,true));
}
}
return ret;
}
|