From 6c9c0b8a29cd0eb64e3f1103ca3363ccff7b3eba Mon Sep 17 00:00:00 2001 From: neoraider Date: Sat, 23 Jun 2007 19:00:05 +0000 Subject: zoomedit: Implemented geometry functions. --- geometry.c | 218 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 218 insertions(+) create mode 100644 geometry.c (limited to 'geometry.c') 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 +#include +#include + + +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); + } + } +} -- cgit v1.2.3