summaryrefslogtreecommitdiffstats
path: root/geometry.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'geometry.cpp')
-rw-r--r--geometry.cpp368
1 files changed, 368 insertions, 0 deletions
diff --git a/geometry.cpp b/geometry.cpp
new file mode 100644
index 0000000..ef5acfd
--- /dev/null
+++ b/geometry.cpp
@@ -0,0 +1,368 @@
+#include "geometry.h"
+#include <math.h>
+#include <stdlib.h>
+#include <gtk/gtk.h>
+
+
+void addVertex(VERTEX_LIST *list, const VERTEX *v) {
+ list->nVertices++;
+ list->vertices = (VERTEX*)realloc(list->vertices, list->nVertices*sizeof(VERTEX));
+ list->vertices[list->nVertices-1] = *v;
+}
+
+void insertVertex(VERTEX_LIST *list, const VERTEX *v, unsigned int n) {
+ int i;
+
+ if(n > list->nVertices)
+ n = list->nVertices;
+
+ list->nVertices++;
+ list->vertices = (VERTEX*)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 = (VERTEX*)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 vertexOnLine(const VERTEX *v, const LINE *l) {
+ if(l->v1.x == l->v2.x && l->v1.y == l->v2.y) {
+ if(l->v1.x == v->x && l->v1.y == v->y) return 1;
+ else return 0;
+ }
+
+ if(l->v1.x == l->v2.x) {
+ if(l->v1.x != v->x) return 0;
+ else if(v->y >= MIN(l->v1.y, l->v2.y) && v->y <= MAX(l->v1.y, l->v2.y)) return 1;
+ else return 1;
+ }
+
+ if(l->v1.y == l->v2.y) {
+ if(l->v1.y != v->y) return 0;
+ else if(v->x >= MIN(l->v1.x, l->v2.x) && v->x <= MAX(l->v1.x, l->v2.x)) return 1;
+ else return 1;
+ }
+ if((v->x-l->v1.x)/(l->v2.x-l->v1.x) - (v->y-l->v1.y)/(l->v2.y-l->v1.y) == 0) return 1;
+ else return 0;
+}
+
+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;
+}
+
+static int quadrant(VERTEX *v) {
+ if(v->x > 0 && v->y >= 0) return 1;
+ if(v->x >= 0 && v->y < 0) return 2;
+ if(v->x < 0 && v->y <= 0) return 3;
+ if(v->x <= 0 && v->y > 0) return 4;
+
+ return 0;
+}
+
+gboolean vertexInPolygon(const VERTEX *v, const POLYGON *p) {
+ int d = 0, i, li;
+ int q, ql, q2;
+ LINE d1 = {{-1, -1}, {1, 1}};
+ LINE d2 = {{-1, 1}, {1, -1}};
+ LINE l;
+ VERTEX v2;
+
+
+ if(p->nVertices == 0) return FALSE;
+
+ v2.x = p->vertices[p->nVertices-1].x - v->x;
+ v2.y = p->vertices[p->nVertices-1].y - v->y;
+ q = quadrant(&v2);
+
+ if(q == 0) return TRUE;
+
+ for(i = 0; i < p->nVertices; i++) {
+ ql = q;
+
+ v2.x = p->vertices[i].x - v->x;
+ v2.y = p->vertices[i].y - v->y;
+ q = quadrant(&v2);
+
+ if(q == 0) return TRUE;
+
+ switch(q-ql) {
+ case 0:
+ break;
+ case 1:
+ case -3:
+ d++;
+ break;
+ case 3:
+ case -1:
+ d--;
+ break;
+ default:
+ l.v1.x = p->vertices[(i>0)?i-1:p->nVertices-1].x - v->x;
+ l.v1.y = p->vertices[(i>0)?i-1:p->nVertices-1].y - v->y;
+
+ l.v2 = v2;
+
+ if(q == 1 || q == 3) {
+ if(!(lineIntersection(&l, &d2, &v2) & INTERSECTION_LINE)) return FALSE;
+
+ q2 = quadrant(&v2);
+ if(q2 == 0) return TRUE;
+
+ if((q == 1 && q2 == 2) || (q == 3 && q2 == 4)) d -= 2;
+ else d += 2;
+ }
+ else {
+ if(!(lineIntersection(&l, &d1, &v2) & INTERSECTION_LINE)) return FALSE;
+
+ q2 = quadrant(&v2);
+ if(q2 == 0) return TRUE;
+
+ if((q == 2 && q2 == 3) || (q == 4 && q2 == 1)) d -= 2;
+ else d += 2;
+ }
+ }
+ }
+
+ return (d == 0) ? FALSE : TRUE;
+}
+
+double polygonPerimeter(const POLYGON *p) {
+ int i;
+ double d = 0.0;
+
+ for(i = 0; i < p->nVertices; i++)
+ d += vertexDistance(&p->vertices[i], &p->vertices[(i+1)%p->nVertices]);
+
+ return d;
+}
+
+double polygonArea(const POLYGON *p) {
+ int i;
+ double d = 0.0;
+
+ for(i = 0; i < p->nVertices; i++)
+ d += (p->vertices[(i+1)%p->nVertices].x+p->vertices[i].x)*(p->vertices[(i+1)%p->nVertices].y-p->vertices[i].y);
+
+ return fabs(d/2);
+}
+
+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;
+ VERTEX v2;
+
+
+ if(v == NULL) v = &v2;
+
+ 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;
+ }
+
+ if(xa1 == xa2 && xb1 == xb2)
+ return (xa1 == xb1) ? INTERSECTION_IDENTICAL : INTERSECTION_NONE;
+
+ if(xa1 == xa2) {
+ v->x = xa1;
+ v->y = yb1;
+ }
+ else if(xb1 == xb2) {
+ v->x = xb1;
+ v->y = ya1;
+ }
+ else {
+ 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;
+
+ 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;
+}
+
+gboolean linePolygonIntersection(const LINE *l, const POLYGON *p) {
+ int i;
+ LINE line;
+
+ for(i = 0; i < p->nVertices; i++) {
+ line.v1 = p->vertices[i];
+ line.v2 = p->vertices[(i+1)%p->nVertices];
+
+ if(lineIntersection(l, &line, NULL) == INTERSECTION_SEGMENT_SEGMENT)
+ return TRUE;
+ }
+
+ return FALSE;
+}
+
+
+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;
+
+ 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;
+
+
+ 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);
+ }
+ 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);
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-16 01:40:56 +0200