zoomedit: simplifyPolygon neu geschrieben

1 files changed, 71 insertions, 58 deletions

diff --git a/geometry.c b/geometry.c
index 2bbd6aa..d54348f 100644
--- a/geometry.c
+++ b/geometry.c
@@ -288,68 +288,81 @@ gboolean linePolygonIntersection(const LINE *l, const POLYGON *p) {
   return FALSE;
 }
 
-void simplifyPolygon(const POLYGON *in, const RECTANGLE *rect, POLYGON *out) {
-  int i, j;
-  int a;
-  int lastVertex, thisVertex;
-  VERTEX v, v2;
-  VERTEX_LIST vl = {0, NULL};
-  LINE line;
-  LINE d1 = {{rect->x, rect->y}, {rect->x+rect->width, rect->y+rect->height}};
-  LINE d2 = {{rect->x, rect->y+rect->height}, {rect->x+rect->width, rect->y}};
+
+static void edgeVertex(VERTEX *v, int edge, const RECTANGLE *rect) {
+  if(edge == EDGE_NONE)
+    edge = vertexInRect(v, rect);
   
+  if(edge & EDGE_LEFT) v->x = rect->x;
+  else if(edge & EDGE_RIGHT) v->x = rect->x+rect->width;
   
-  thisVertex = vertexInRect(&in->vertices[0], rect);
+  if(edge & EDGE_TOP) v->y = rect->y;
+  else if(edge & EDGE_BOTTOM) v->y = rect->y+rect->height;
+}
+
+static int simplifyVertex(VERTEX *v, const VERTEX *to, const RECTANGLE *rect) {
+  LINE l = {*v, *to};
+  int edge, edge2;
   
-  for(i = 0; i < in->nVertices; i++) {
-    line.v1 = in->vertices[i];
-    line.v2 = in->vertices[(i+1)%in->nVertices];
-    
-    lastVertex = thisVertex;
-    thisVertex = vertexInRect(&line.v2, rect);
-    
-    if(thisVertex == EDGE_NONE) {
-      if(lastVertex != EDGE_NONE && lineRectIntersection(&line, rect, lastVertex, &v))
-        addVertex(&vl, &v);
-      
-      addVertex(&vl, &line.v2);
-    }
-    else if(lastVertex == EDGE_NONE) {
-      if(lineRectIntersection(&line, rect, thisVertex, &v))
-        addVertex(&vl, &v);
-    }
-    else {
-      a = lineRectIntersections(&line, rect, lastVertex, &v, &v2);
-      
-      if((a & lastVertex) && (a & thisVertex)) {
-        addVertex(&vl, &v);
-        addVertex(&vl, &v2);
-      }
-      
-      if(lineIntersection(&line, &d1, &v) == INTERSECTION_SEGMENT_LINE) {
-        if(v.x <= rect->x) addVertex(&vl, &d1.v1);
-        else addVertex(&vl, &d1.v2);
-      }
-      
-      if(lineIntersection(&line, &d2, &v) == INTERSECTION_SEGMENT_LINE) {
-        if(v.x <= rect->x) addVertex(&vl, &d2.v1);
-        else addVertex(&vl, &d2.v2);
-      }
+  
+  edge = vertexInRect(v, rect);
+  if(edge == EDGE_NONE) return EDGE_NONE;
+  
+  edge2 = lineRectIntersection(&l, rect, edge, v);
+  if(edge2 != EDGE_NONE) return edge2;
+  
+  edgeVertex(v, edge, rect);
+  return edge;
+}
+
+
+
+static void addSimplifiedLine(const VERTEX *v1, const VERTEX *v2, const RECTANGLE *rect, int last, POLYGON *out) {
+  const LINE d1 = {{rect->x, rect->y}, {rect->x+rect->width, rect->y+rect->height}};
+  const LINE d2 = {{rect->x, rect->y+rect->height}, {rect->x+rect->width, rect->y}};
+  
+  LINE l = {*v1, *v2};
+  VERTEX v, vi;
+  int edge1, edge2;
+  
+  
+  v = *v1;
+  if((edge1 = simplifyVertex(&v, v2, rect)) != EDGE_NONE)
+    addVertex(out, &v);
+  
+  v = *v2;
+  edge2 = simplifyVertex(&v, v1, rect);
+  
+  if(edge1 != EDGE_NONE && edge2 != EDGE_NONE && !(edge1 & edge2)) {
+    if(lineIntersection(&l, &d1, &vi) == INTERSECTION_SEGMENT_LINE) {
+      edgeVertex(&vi, 0, rect);
+      addVertex(out, &vi);
     }
-    
-    while(vl.nVertices > 0) {
-      a = 0;
-      
-      for(j = 0; j < vl.nVertices; j++) {
-        if(vertexDistanceSquare(&line.v1, &vl.vertices[j]) < vertexDistanceSquare(&line.v1, &vl.vertices[a]))
-          a = j;
-      }
-      
-      if(out->nVertices == 0 || out->vertices[out->nVertices-1].x != vl.vertices[a].x ||
-         out->vertices[out->nVertices-1].y != vl.vertices[a].y)
-        addVertex(out, &vl.vertices[a]);
-      
-      deleteVertex(&vl, a);
+    else if(lineIntersection(&l, &d2, &vi) == INTERSECTION_SEGMENT_LINE) {
+      edgeVertex(&vi, 0, rect);
+      addVertex(out, &vi);
     }
   }
+  
+  if(!last)
+    addVertex(out, &v);
+}
+
+void simplifyPolygon(const POLYGON *in, const RECTANGLE *rect, POLYGON *out) {
+  VERTEX v;
+  int i;
+  
+  if(in->nVertices == 0) return;
+  else if(in->nVertices == 1) {
+    addVertex(out, &in->vertices[0]);
+    return;
+  }
+  
+  v = in->vertices[0];
+  simplifyVertex(&v, &in->vertices[in->nVertices-1], rect);
+  addVertex(out, &v);
+  
+  for(i = 0; i < in->nVertices; i++) {
+    addSimplifiedLine(&in->vertices[i], &in->vertices[(i+1)%in->nVertices], rect, (i == in->nVertices-1), out);
+  }
 }