triangulate.cpp

#include "set"
#include "vector"
#include "deque"
#include "algorithm"


struct PointRef {
   int vecIdx;
   int ptIdx;
};

struct Point {
   double x;
   double y;
   inline friend bool operator<(const Point &p1, const Point &p2) {
      return p1.y > p2.y || (p1.y == p2.y && p1.x > p2.x);
   }
};

struct Triangle {
   PointRef p1;
   PointRef p2;
   PointRef p3;
   int tr1;
   int tr2;
   int tr3;
};
   
struct TriState {
   Point **inPoly;
   int nPoly;
   int *polySizes;
   PointRef **newEdges;
   Triangle *triangles;
};

enum VertexType {
   Split,
   Merge,
   Left,
   Right,
   Start,
   End
};

struct Vertex {
   inline friend bool operator<(const Vertex &p1, const Vertex &p2) {
      return p1.pt < p2.pt;
   }
   PointRef ref;
   Point pt;
   VertexType type;
};

struct Edge {
   Edge(Point &p1, Point &p2, Vertex *help);

   friend bool operator<(const Edge &e1, const Edge &e2);
   Point from;
   Point to;
   Vertex *helper;
};

Edge::Edge(Point &p1, Point &p2, Vertex *help) {
   if(p1 < p2) {
       from = p1;
       to = p2;
   } else {
       from = p2;
       to = p1;
   }
   helper = help;
}

bool operator<(const Edge &e1, const Edge &e2)
{
   if(e1.from < e2.from)
      return e1.from.x + (e1.from.x - e1.to.x)/
	  (e1.from.y - e1.to.y)
	  *(e2.from.y - e1.to.y)
	  < e2.from.x;
   else
      return e2.from.x + (e2.from.x - e2.to.x)/
	    (e2.from.y - e2.to.y)
	    *(e1.from.y - e2.to.y)
	    < e1.from.x;
}

Point nextPt(TriState &st, Vertex &v) {
}

Point prevPt(TriState &st, Vertex &v) {

}

inline bool crossProduct(Point p, Point q)
{
   return p.x*q.y - q.x*p.y;
}

inline Point subPt(Point p, Point q) {
   p.x -= q.x;
   p.y -= q.y;

   return p;
}

VertexType calcVertexType(TriState &st, PointRef ref, Point pt)
{
   Point prevPt, nextPt;
   
   if(ref.ptIdx == 0)
      prevPt = st.inPoly[ref.vecIdx][st.polySizes[ref.vecIdx]-1];
   else
      prevPt = st.inPoly[ref.vecIdx][ref.ptIdx-1];

   if(ref.ptIdx == st.polySizes[ref.vecIdx]-1)
      nextPt = st.inPoly[ref.vecIdx][0];
   else
      nextPt = st.inPoly[ref.vecIdx][ref.ptIdx+1];

   if(prevPt < pt)
   {
       if (nextPt < pt) {
	   if(crossProduct(subPt(nextPt, pt), subPt(prevPt, pt)) <= 0)
	      return End;
	   else 
	      return Merge;
       } else 
	  return Left;
   }
   else
   {
       if(pt < nextPt) {
	   if(crossProduct(subPt(nextPt, pt), subPt(prevPt, pt)) <= 0)
	      return Split;
	   else
	      return Start;
       } else
	  return Right;
   }
}

void monoDir (TriState st, std::deque<Vertex> startVertices)
{
   int i, j, size;
   std::vector<Vertex>::iterator vi;
   std::set<Edge> edges;
   std::set<Edge>::iterator ei;

   std::vector<Vertex> vertices;
   
   size = 0;
   for(i = 0; i < st.nPoly; i++)
      size += st.polySizes[i];

   // collect all vertices
   vertices.reserve(size);
   for(i = 0; i < st.nPoly; i++) {
       size = st.polySizes[i];
       for(j = 0; j < size; j++){
	   Vertex pi;
	   pi.ref.vecIdx = i;
	   pi.ref.ptIdx = j;
	   pi.pt = st.inPoly[i][j];
	   pi.type = calcVertexType(st, pi.ref, pi.pt);
	   vertices.push_back(pi);
       }
   }

   //sort the vertices
   std::sort(vertices.begin(), vertices.end());

   for(vi = vertices.begin(); vi < vertices.end(); vi++) {
       switch (vi->type) {
	 case Split:
	 {
	     Point next = nextPt(st, *vi);
	     Edge nextEdge(vi->pt, next, &*vi);
	     ei = edges.find(nextEdge);
	     Vertex *h = ei->helper;
	     st.newEdges[h->ref.vecIdx][h->ref.ptIdx] = vi->ref;
	     ei->helper = &*vi;
	     edges.insert(nextEdge);
	     break;
	 }
	 case Merge:
	 {
	    break;
	 }
	 case Left:
	 {
	    break;
	 }
	 case Right:
	 {
	     
	     break;
	 }
	 case Start:
	 {
	     // insert e_1 in T and set helper(e_i) to v_i;
	     Point next = nextPt(st, *vi);
	     Edge newEdge(vi->pt, next, &*vi);
	     edges.insert(newEdge);
	     break;
	 }
	 case End:
	 {
	     Edge prevEdge(vi->pt, vi->pt, NULL);
	     ei = edges.find(prevEdge);
	     Vertex *h = ei->helper;
	     if(h->type == Merge){
		 st.newEdges[h->ref.vecIdx][h->ref.ptIdx] = vi->ref;
	     }
	     edges.erase(ei);
	     break;
	 }
       }
	   
   } 
}

-- mode: compilation; default-directory: "~/Programs/triangulate/" --
Compilation started at Thu Jun 29 18:49:15

g++ triangulate.cpp -c
triangulate.cpp: In function ‘void monoDir(TriState, std::deque)’:
triangulate.cpp:183:18: error: assignment of member ‘Edge::helper’ in read-only object
ei->helper = &*vi;
^

Compilation exited abnormally with code 1 at Thu Jun 29 18:49:15