1 files changed, 68 insertions, 23 deletions

diff --git a/Polygon.cpp b/Polygon.cpp
index 3425727..eb63a61 100644
--- a/Polygon.cpp
+++ b/Polygon.cpp
@@ -1,10 +1,11 @@
 #include "Polygon.h"
+#include "Line.h"
 #include <list>
 #include <math.h>
 
 
-double Polygon::signedArea() const {
-  double d = 0.0;
+float Polygon::signedArea() const {
+  float d = 0.0;
   
   for(const_iterator it = begin(); it != end(); it++) {
     const_iterator it2 = it+1;
@@ -17,17 +18,17 @@ double Polygon::signedArea() const {
 }
 
 Polygon::Direction Polygon::getDirection() const {
-  double area = signedArea();
+  float area = signedArea();
   
   return (area > 0) ? Triangle::CW : (area < 0) ? Triangle::CCW : Triangle::Unknown;
 }
 
-double Polygon::area() const {
+float Polygon::area() const {
   return fabs(signedArea());
 }
 
-double Polygon::perimeter() const {
-  double d = 0.0;
+float Polygon::perimeter() const {
+  float d = 0.0;
   
   for(const_iterator it = begin(); it != end(); it++) {
     const_iterator it2 = it+1;
@@ -173,8 +174,9 @@ bool Polygon::isSimple() const {
   return !intersections();
 }
 
-bool Polygon::simplify(Polygon &polygon) const {
+bool Polygon::simplify(std::list<Polygon> &polygons) const {
   std::vector<Intersection> ins;
+  std::vector<Intersection*> inlist;
   
   if(!intersections(&ins)) return false;
   
@@ -194,6 +196,8 @@ bool Polygon::simplify(Polygon &polygon) const {
   const Vertex *v2 = &at(i2);
   bool intersected;
   
+  polygons.push_back(Polygon());
+  
   do {
     intersected = false;
     
@@ -207,51 +211,86 @@ bool Polygon::simplify(Polygon &polygon) const {
 	const Vertex *v1 = v2;
 	v2 = &at(i2);
 	
+	float dl = v2->distanceSq(*v1);
+	
+	Intersection *intr = NULL;
 	Vertex *v = NULL;
+	float dv = 0;
 	int v3, v4;
 	
 	for(std::vector<Intersection>::iterator in = ins.begin(); in != ins.end(); ++in) {
-	  if(v2->distanceSq(in->v) >= v2->distanceSq(*v1) || v1 == &in->v)
+	  float di = v2->distanceSq(in->v);
+	  
+	  if(di >= dl || v1 == &in->v)
 	    continue;
 	  
-	  if(v) {
-	    if(v1->distanceSq(in->v) >= v1->distanceSq(*v))
-	      continue;
-	  }
+	  if(v && di < dv)
+	    continue;
 	  
 	  if((i == in->va1 && i2 == in->va2) || (i == in->va2 && i2 == in->va1)) {
+	    intr = &*in;
+	    
 	    v = &in->v;
+	    dv = di;
 	    v3 = in->vb1;
 	    v4 = in->vb2;
 	  }
 	  else if((i == in->vb1 && i2 == in->vb2) || (i == in->vb2 && i2 == in->vb1)) {
+	    intr = &*in;
+	    
 	    v = &in->v;
+	    dv = di;
 	    v3 = in->va1;
 	    v4 = in->va2;
 	  }
     }
 	
-	if(v) {
+	if(intr) {
+	  if(isConcave(Triangle::CW, *v1, *v2, at(v4))) {
+	    if(!Line(*v1, *v2).contains(at(v3))) {
+	      i2 = v3;
+	      dir = Triangle::CW;
+	    }
+	  }
+	  else {
+	    if(!Line(*v1, *v2).contains(at(v4))) {
+	      i2 = v4;
+	      dir = Triangle::CCW;
+	    }
+	  }
+	  
 	  v2 = v;
 	  intersected = true;
 	  
-	  if(isConcave(Triangle::CW, *v1, *v2, at(v4))) {
-	    i2 = v3;
-	    dir = Triangle::CW;
+	  std::vector<Intersection*>::reverse_iterator it = inlist.rbegin();
+	  for(; it != inlist.rend(); it++) {
+	    if(*it == intr) break;
+	  }
+	  
+	  if(it != inlist.rend()) {
+	    inlist.erase(it.base()-1, inlist.end());
+	    
+	    polygons.push_back(Polygon());
+	    
+	    while(!polygons.front().empty()) {
+	      polygons.back().push_back(polygons.front().back());
+	      polygons.front().pop_back();
+	      
+	      if(v->distanceSq(polygons.back().back()) < 1E-6)
+	        break;
+	    }
 	  }
 	  else {
-	    i2 = v4;
-	    dir = Triangle::CCW;
+	    inlist.push_back(intr);
 	  }
 	}
 	
-	polygon.push_back(*v2);
+	polygons.front().push_back(*v2);
   } while(i2 != start || intersected);
   
   return true;
 }
 
-// FIXME: has still some problems...
 void Polygon::doTriangulate(std::vector<Triangle> &triangles) const {
   size_t s = size();
   
@@ -277,12 +316,14 @@ void Polygon::doTriangulate(std::vector<Triangle> &triangles) const {
     const Vertex *v3 = &at(p[(i+3)%s2]);
     const Vertex *v4 = &at(p[(i+4)%s2]);
     
+    
     if(isConcave(dir, *v1, *v2, *v3))
       continue;
     
     Triangle t(*v1, *v2, *v3);
     
     std::list<size_t>::iterator it = concave.begin();
+    
     for(; it != concave.end(); it++) {
       if(*it != p[(i+1)%s2] && *it != p[(i+3)%s2] && t.contains(at(*it)))
         break;
@@ -301,15 +342,19 @@ void Polygon::doTriangulate(std::vector<Triangle> &triangles) const {
     }
     
     p.erase(p.begin()+(i+2)%s2);
-    i = 0;
+    i = -1;
   }
   
+  
   triangles.push_back(Triangle(at(p[0]), at(p[1]), at(p[2])));
 }
 
 void Polygon::triangulate(std::vector<Triangle> &triangles) const {
-  Polygon p;
+  std::list<Polygon> polygons;
   
-  if(simplify(p)) p.doTriangulate(triangles);
+  if(simplify(polygons)) {
+    for(std::list<Polygon>::iterator p = polygons.begin(); p != polygons.end(); p++)
+      p->doTriangulate(triangles);
+  }
   else doTriangulate(triangles);
 }