summaryrefslogtreecommitdiffstats
path: root/geometry.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'geometry.cpp')
-rw-r--r--geometry.cpp240
1 files changed, 17 insertions, 223 deletions
diff --git a/geometry.cpp b/geometry.cpp
index e709fb8..e3adb6b 100644
--- a/geometry.cpp
+++ b/geometry.cpp
@@ -4,39 +4,6 @@
#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));
-}
-
-
int vertexOnLine(const Vertex *v, const LINE *l) {
if(l->v1.getX() == l->v2.getX() && l->v1.getY() == l->v2.getY()) {
if(l->v1.getX() == v->getX() && l->v1.getY() == v->getY()) return 1;
@@ -70,166 +37,6 @@ int vertexInRect(const Vertex *v, const RECTANGLE *rect) {
return ret;
}
-static int quadrant(Vertex *v) {
- if(v->getX() > 0 && v->getY() >= 0) return 1;
- if(v->getX() >= 0 && v->getY() < 0) return 2;
- if(v->getX() < 0 && v->getY() <= 0) return 3;
- if(v->getX() <= 0 && v->getY() > 0) return 4;
-
- return 0;
-}
-
-gboolean vertexInPolygon(const Vertex *v, const POLYGON *p) {
- int d = 0, i, li;
- int q, ql, q2;
- LINE d1 = {Vertex(-1, -1), Vertex(1, 1)};
- LINE d2 = {Vertex(-1, 1), Vertex(1, -1)};
- LINE l;
- Vertex v2;
-
-
- if(p->nVertices == 0) return FALSE;
-
- v2 = p->vertices[p->nVertices-1] - *v;
- q = quadrant(&v2);
-
- if(q == 0) return TRUE;
-
- for(i = 0; i < p->nVertices; i++) {
- ql = q;
-
-
- v2 = p->vertices[i] - *v;
-
- 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 = p->vertices[(i>0)?i-1:p->nVertices-1] - *v;
- 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 += p->vertices[i].distance(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].getX()+p->vertices[i].getX())*(p->vertices[(i+1)%p->nVertices].getY()-p->vertices[i].getY());
-
- return fabs(d/2);
-}
-
-int lineIntersection(const LINE *la, const LINE *lb, Vertex *v) {
- double xa1 = la->v1.getX(), ya1 = la->v1.getY();
- double xa2 = la->v2.getX(), ya2 = la->v2.getY();
- double xb1 = lb->v1.getX(), yb1 = lb->v1.getY();
- double xb2 = lb->v2.getX(), yb2 = lb->v2.getY();
- 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->setX(xa1);
- v->setY(yb1);
- }
- else if(xb1 == xb2) {
- v->setX(xb1);
- v->setY(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->setX((bb-ba)/(ma-mb));
- v->setY(ma*v->getX() + ba);
- }
-
- if(switched) {
- temp = v->getX(); v->setX(v->getY()); v->setY(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->getX() < MIN(xa1,xa2) || v->getX() > MAX(xa1, xa2) || v->getY() < MIN(ya1,ya2) || v->getY() > MAX(ya1, ya2)) {
- if(v->getX() < MIN(xb1,xb2) || v->getX() > MAX(xb1, xb2) || v->getY() < MIN(yb1,yb2) || v->getY() > MAX(yb1, yb2))
- return INTERSECTION_LINE_LINE;
- else
- return INTERSECTION_LINE_SEGMENT;
- }
- else if(v->getX() < MIN(xb1,xb2) || v->getX() > MAX(xb1, xb2) || v->getY() < MIN(yb1,yb2) || v->getY() > 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;
@@ -262,21 +69,6 @@ int lineRectIntersections(const LINE *line, const RECTANGLE *rect, int edge, Ver
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)
@@ -306,7 +98,7 @@ static int simplifyVertex(Vertex *v, const Vertex *to, const RECTANGLE *rect) {
-static void addSimplifiedLine(const Vertex *v1, const Vertex *v2, const RECTANGLE *rect, int last, POLYGON *out) {
+static void addSimplifiedLine(const Vertex *v1, const Vertex *v2, const RECTANGLE *rect, int last, Polygon *out) {
const LINE d1 = {Vertex(rect->x, rect->y), Vertex(rect->x+rect->width, rect->y+rect->height)};
const LINE d2 = {Vertex(rect->x, rect->y+rect->height), Vertex(rect->x+rect->width, rect->y)};
@@ -317,7 +109,7 @@ static void addSimplifiedLine(const Vertex *v1, const Vertex *v2, const RECTANGL
v = *v1;
if((edge1 = simplifyVertex(&v, v2, rect)) != EDGE_NONE)
- addVertex(out, &v);
+ out->push_back(v);
v = *v2;
edge2 = simplifyVertex(&v, v1, rect);
@@ -325,33 +117,35 @@ static void addSimplifiedLine(const Vertex *v1, const Vertex *v2, const RECTANGL
if(edge1 != EDGE_NONE && edge2 != EDGE_NONE && !(edge1 & edge2)) {
if(lineIntersection(&l, &d1, &vi) == INTERSECTION_SEGMENT_LINE) {
edgeVertex(&vi, 0, rect);
- addVertex(out, &vi);
+ out->push_back(vi);
}
else if(lineIntersection(&l, &d2, &vi) == INTERSECTION_SEGMENT_LINE) {
edgeVertex(&vi, 0, rect);
- addVertex(out, &vi);
+ out->push_back(vi);
}
}
if(!last)
- addVertex(out, &v);
+ out->push_back(v);
}
-void simplifyPolygon(const POLYGON *in, const RECTANGLE *rect, POLYGON *out) {
+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]);
+ if(in->empty()) return;
+ else if(in->size() == 1) {
+ out->push_back(in->front());
return;
}
- v = in->vertices[0];
- simplifyVertex(&v, &in->vertices[in->nVertices-1], rect);
- addVertex(out, &v);
+ v = in->front();
+ simplifyVertex(&v, &in->back(), rect);
+ out->push_back(v);
- for(i = 0; i < in->nVertices; i++) {
- addSimplifiedLine(&in->vertices[i], &in->vertices[(i+1)%in->nVertices], rect, (i == in->nVertices-1), out);
+ for(Polygon::const_iterator it = in->begin(); it != in->end(); it++) {
+ Polygon::const_iterator it2 = it+1;
+ if(it2 == in->end()) it2 = in->begin();
+
+ addSimplifiedLine(&*it, &*it2, rect, (it2 == in->begin()), out);
}
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-01 05:37:01 +0100