summaryrefslogtreecommitdiffstats
path: root/geometry.c
diff options
context:
space:
mode:
Diffstat (limited to 'geometry.c')
-rw-r--r--geometry.c218
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);
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-19 05:16:18 +0100