1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
/*
This software may only be used by you under license from AT&T Corp.
("AT&T"). A copy of AT&T's Source Code Agreement is available at
AT&T's Internet website having the URL:
<http://www.research.att.com/sw/tools/graphviz/license/source.html>
If you received this software without first entering into a license
with AT&T, you have an infringing copy of this software and cannot use
it without violating AT&T's intellectual property rights.
*/
#pragma prototyped
/*
* in_poly
*
* Test if a point is inside a polygon.
* The polygon may have concavities.
* Doesn't work with twisted polygons.
* From O'Rourke book (via erg@research.att.com)
*/
#include <stdlib.h>
#include <vispath.h>
#include <pathutil.h>
#ifdef DMALLOC
#include "dmalloc.h"
#endif
static Ppoint_t subpt(Ppoint_t p, Ppoint_t q)
{
Ppoint_t rv;
rv.x = p.x - q.x;
rv.y = p.y - q.y;
return rv;
}
int in_poly(Ppoly_t argpoly, Ppoint_t q)
{
int i, i1; /* point index; i1 = i-1 mod n */
double x; /* x intersection of e with ray */
int crossings = 0; /* 2 * number of edge/ray crossings */
Ppoly_t poly; /* original O'Rourke code overwrites the arg polygon! */
Ppoint_t *P;
int n;
/* Shift so that q is the origin. */
poly = copypoly(argpoly);
P = poly.ps;
n = poly.pn;
for (i = 0; i < n; i++)
poly.ps[i] = subpt(poly.ps[i],q);
/* For each edge e=(i-1,i), see if crosses ray. */
for (i = 0; i < n; i++ ) {
i1 = ( i + n - 1 ) % n;
/* if edge is horizontal, test to see if the point is on it */
if ((P[i].y == 0 ) && ( P[i1].y == 0)) {
if ((P[i].x * P[i1].x) < 0)
return TRUE;
else
continue;
}
/* if e straddles the x-axis... */
if (((P[i].y >= 0 ) && ( P[i1].y <= 0 ) ) ||
( ( P[i1].y >= 0 ) && ( P[i].y <= 0 ) ) ) {
/* e straddles ray, so compute intersection with ray. */
x = (P[i].x * P[i1].y - P[i1].x * P[i].y)
/ (double)(P[i1].y - P[i].y);
/* if intersect at origin, we've found intersection */
if (x == 0)
return TRUE;
/* crosses ray if strictly positive intersection. */
if (x > 0) {
if ( P[i].y == 0 ) {
if ( P[(i-1+n)%n].y*P[(1+i)%n].y < 0) {
/* count half a crossing */
crossings++;
}
else if ( P[i].y*P[(2+i)%n].y < 0) {
/* count half a crossing */
crossings++;
}
}
else {
/* count a full crossing */
crossings += 2;
}
}
}
}
freepoly(poly);
/* q inside if an odd number of crossings. */
if( (crossings % 4) >= 2 )
return TRUE;
else
return FALSE;
}
|
