zoomedit: Implemented geometry functions.

1 files changed, 218 insertions, 0 deletions

diff --git a/geometry.c b/geometry.c
new file mode 100644
index 0000000..238e2fa
--- /dev/null
+++ b/geometry.c
@@ -0,0 +1,218 @@
+#include "geometry.h"
+#include <math.h>
+#include <stdlib.h>
+#include <gtk/gtk.h>
+
+
+void addVertex(VERTEX_LIST *list, VERTEX *v) {
+  list->nVertices++;
+  list->vertices = realloc(list->vertices, list->nVertices*sizeof(VERTEX));
+  list->vertices[list->nVertices-1] = *v;
+}
+
+void insertVertex(VERTEX_LIST *list, VERTEX *v, unsigned int n) {
+  int i;
+  
+  if(n > list->nVertices)
+    n = list->nVertices;
+  
+  list->nVertices++;
+  list->vertices = realloc(list->vertices, list->nVertices*sizeof(VERTEX));
+  
+  for(i = list->nVertices-1; i > n; i--)
+    list->vertices[i] = list->vertices[i-1];
+  
+  list->vertices[n] = *v;
+}
+
+void deleteVertex(VERTEX_LIST *list, unsigned int n) {
+  int i;
+  
+  list->nVertices--;
+  
+  for(i = n; i < list->nVertices; i++)
+    list->vertices[i] = list->vertices[i+1];
+  
+  list->vertices = realloc(list->vertices, list->nVertices*sizeof(VERTEX));
+}
+
+double vertexDistanceSquare(const VERTEX *v1, const VERTEX *v2) {
+  return (v1->x-v2->x)*(v1->x-v2->x) + (v1->y-v2->y)*(v1->y-v2->y);
+}
+
+double vertexDistance(const VERTEX *v1, const VERTEX *v2) {
+  return sqrt(vertexDistanceSquare(v1, v2));
+}
+
+
+int vertexInRect(const VERTEX *v, const RECTANGLE *rect) {
+  int ret = EDGE_NONE;
+  
+  if(v->x < rect->x) ret |= EDGE_LEFT;
+  else if(v->x >= rect->x+rect->width) ret |= EDGE_RIGHT;
+  
+  if(v->y < rect->y) ret |= EDGE_TOP;
+  else if(v->y >= rect->y+rect->height) ret |= EDGE_BOTTOM;
+  
+  return ret;
+}
+
+int lineIntersection(const LINE *la, const LINE *lb, VERTEX *v) {
+  double xa1 = la->v1.x, ya1 = la->v1.y;
+  double xa2 = la->v2.x, ya2 = la->v2.y;
+  double xb1 = lb->v1.x, yb1 = lb->v1.y;
+  double xb2 = lb->v2.x, yb2 = lb->v2.y;
+  double temp;
+  int switched = 0;
+  
+  
+  if(xa1 == xa2 && ya1 == ya2) return INTERSECTION_ERROR;
+  if(xb1 == xb2 && yb1 == yb2) return INTERSECTION_ERROR;
+  
+  if(xa1 == xa2 || xb1 == xb2) {
+    temp = xa1; xa1 = ya1; ya1 = temp;
+    temp = xa2; xa2 = ya2; ya2 = temp;
+    temp = xb1; xb1 = yb1; yb1 = temp;
+    temp = xb2; xb2 = yb2; yb2 = temp;
+    
+    switched = 1;
+  }
+  
+  double ma = (ya2-ya1)/(xa2-xa1);
+  double mb = (yb2-yb1)/(xb2-xb1);
+  double ba = ya1 - ma*xa1;
+  double bb = yb1 - mb*xb1;
+  
+  if(ma == mb) return (ba == bb) ? INTERSECTION_IDENTICAL : INTERSECTION_NONE; 
+  
+  if(isinf(ma)) {
+    v->x = xa1;
+    v->y = yb1;
+  }
+  else if(isinf(mb)) {
+    v->x = xb1;
+    v->y = ya1;
+  }
+  else {
+    v->x = (bb-ba)/(ma-mb);
+    v->y = ma*v->x + ba;
+  }
+  
+  if(switched) {
+    temp = v->x; v->x = v->y; v->y = temp;
+    
+    //switch back everything for segment tests
+    temp = xa1; xa1 = ya1; ya1 = temp;
+    temp = xa2; xa2 = ya2; ya2 = temp;
+    temp = xb1; xb1 = yb1; yb1 = temp;
+    temp = xb2; xb2 = yb2; yb2 = temp;
+  }
+  
+  if(v->x < MIN(xa1,xa2) || v->x > MAX(xa1, xa2) || v->y < MIN(ya1,ya2) || v->y > MAX(ya1, ya2)) {
+    if(v->x < MIN(xb1,xb2) || v->x > MAX(xb1, xb2) || v->y < MIN(yb1,yb2) || v->y > MAX(yb1, yb2))
+      return INTERSECTION_LINE_LINE;
+    else
+      return INTERSECTION_LINE_SEGMENT;
+  }
+  else if(v->x < MIN(xb1,xb2) || v->x > MAX(xb1, xb2) || v->y < MIN(yb1,yb2) || v->y > MAX(yb1, yb2))
+    return INTERSECTION_SEGMENT_LINE;
+  else
+    return INTERSECTION_SEGMENT_SEGMENT;
+}
+
+int lineRectIntersection(const LINE *l, const RECTANGLE *rect, int edge, VERTEX *v) {
+  const double minX = rect->x, maxX = rect->x+rect->width;
+  const double minY = rect->y, maxY = rect->y+rect->height;
+  const LINE top = {{minX, minY}, {maxX, minY}};
+  const LINE bottom = {{minX, maxY}, {maxX, maxY}};
+  const LINE left = {{minX, minY}, {minX, maxY}};
+  const LINE right = {{maxX, minY}, {maxX, maxY}};
+  
+  if((edge & EDGE_TOP) && (lineIntersection(&top, l, v) == INTERSECTION_SEGMENT_SEGMENT))
+    return EDGE_TOP;
+  if((edge & EDGE_BOTTOM) && (lineIntersection(&bottom, l, v) == INTERSECTION_SEGMENT_SEGMENT))
+    return EDGE_BOTTOM;
+  if((edge & EDGE_LEFT) && (lineIntersection(&left, l, v) == INTERSECTION_SEGMENT_SEGMENT))
+    return EDGE_LEFT;
+  if((edge & EDGE_RIGHT) && (lineIntersection(&right, l, v) == INTERSECTION_SEGMENT_SEGMENT))
+    return EDGE_RIGHT;
+  
+  v->x = v->y = 0;
+  
+  return EDGE_NONE;
+}
+
+int lineRectIntersections(const LINE *line, const RECTANGLE *rect, int edge, VERTEX *v1, VERTEX *v2) {
+  int ret = EDGE_NONE;
+  
+  ret |= lineRectIntersection(line, rect, edge, v1);
+  ret |= lineRectIntersection(line, rect, EDGE_ALL^edge, v2);
+  
+  return ret;
+}
+
+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}};
+  
+  
+  thisVertex = vertexInRect(&in->vertices[0], rect);
+  
+  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);
+      }
+    }
+    
+    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);
+    }
+  }
+}