diff options
Diffstat (limited to 'geometry.c')
-rw-r--r-- | geometry.c | 368 |
1 files changed, 0 insertions, 368 deletions
diff --git a/geometry.c b/geometry.c deleted file mode 100644 index d54348f..0000000 --- a/geometry.c +++ /dev/null @@ -1,368 +0,0 @@ -#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 = 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 = 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 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); - } -} |