diff options
Diffstat (limited to 'geometry.c')
-rw-r--r-- | geometry.c | 76 |
1 files changed, 76 insertions, 0 deletions
@@ -57,6 +57,82 @@ int vertexInRect(const VERTEX *v, const RECTANGLE *rect) { 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; +} + 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; |