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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
|
<html>
<body>
<h1> Reliable point-in-polygon test </h1>
<h2> Input and output </h2>
<p>
Input is a contour based description of a multi-island polygon with holes
and a virtual point (VP), all in 2d space with integer coordinates. The
virtual point is infinitely close, but is shifted a tiny bit left and up
or down from RP; RP is a point specified by integer coordinates RPx and
RPy. The location of VP relative to RP is specified by an input direction
vector, whose scale is ignored but angle is used.
<p>
The output is a boolean value that is true if VP is in a solid ("filled")
portion of the input polygon.
<h2> the algorithm </h2>
<p>
The algorithm casts an infinite horizontal ray from RP to the right and
counts how many edge segments of the polygon it would hit if it was cast
from VP.
<p>
Set up a counter CNT with initial value 0. In arbitrary order take
each contour segment SEG the ray intersects and:
<ul>
<li> [H1] if SEG is horizontal, ignore it
<li> [H2] otherwise if RP matches one of the SEG's endpoint:
<Ul>
<li> [H2.1] compute dy, the difference of y component the other
endpoint if SEG (that's not RP) and RP; if dy's sign is not
equal to the y component of the direction vector, skip this SEG
<li> [H2.2] take an infinite line L that SEG is part of, then check
which side of L the direction vector's far end falls on; if
it's the left side of L, increase CNT by 1 (else ignore the SEG).
</ul>
<li> [H3] otherwise if the ray crosses SEG in the middle (which also means the
x coordinate of this crossing point is >= RPx) increase CNT by 1.
<li> [H4] otherwise ignore the SEG
</ul>
<p>
Note: orientation of SEG or whether it's a polygon hole or outer contour
does not matter; it is assumed there are no overlapping segments or odd stubs
and there are no zero length segments. There are no open loops in the input.
<p>
Note: the ray is traveling on a non-integer y coordinate (topologically
speaking) so it never actually hits a vertex, only SEGs, sometimes very close
to their endpoints.
<p>
After dealing with all intersection the result is:
<ul>
<li> CNT is odd: VP is inside the filled area of the input polygon
<li> CNT is even: VP is outside the filled area of the input polygon
</ul>
<p>
Note: in practice this test is ran on a rightmost point of a polybool2 face
contour with a direction vector pointing inside the face.
<p>
Note: value 0 is considered an even number.
<h2> Examples </h2>
<p>
On the figure below, the integer coordinate grid is drawn with thin black lines
and an input polygon with a single hole is drawn in red. Straight line segments
making up the outer contours and hole contours are labeled with green integers.
Test RPs are marked with blue crosses and are labeled from A..J.
<p>
<center>
<img src="point-in-poly.svg" width="800px">
<br>
Figure 2. point-in-poly tests
</center>
<p>
From RP 'A', with a direction vector pointing up-left 45 degrees:
RP falls on the endpoint of segment 0 and 1. Segment 0 is ignored
because of [H2.1] (segment going down from RP, direction pointing up).
Segment 1 increases CNT because of [H2.2] as the end of the upward pointing
direction vector is left of it. Then the ray is crossing edges 2 and 4 in the
middle, each increasing CNT because of [H3]. CNT is 0+1+1+1=3 at the end.
3 is odd, VP (the point very close to but up-left of 'A') is inside the
solid of the red polygon.
<p>
From RP 'B' with a direction vector pointing up-left 45 degrees:
RP is at the shared endpoint of 1 and 2. They are both ignored
because of [H2.1]: (SEGs are pointing downward, dir vector upward). Then
the ray crosses 4 in the middle so CNT is increased according to [H3].
CNT is 0+0+1=1 at the end. 1 is odd, VP (the point very close to but up-left of 'B')
is inside the solid of the red polygon.
<p>
From RP 'B' with a direction vector pointing down-left 45 degrees:
<ul>
<li> seg 1: [H2.2]; ignored because it is left of the dir vector's end
<li> seg 2: [H2.2]; CNT++ because it is right of the dir vector's end
<li> seg 4: [H3]; CNT++ for middle crossing
</ul>
<p>
Resulting CNT is 2, even: VP down-left of 'B' is outside of the solid red
(sitting in the hole).
<p>
From RP 'C' dir pointing left-up or left-down: RP is not on any vertex; ray hits
midpoint 2 (CNT++) then midpoint 4 (CNT++); Final CNT is 2 which is even: VP
is outside (as it is sitting in a hole).
<p>
From RP 'D' dir pointing left-up:
<ul>
<li> RP is not on any vertex
<li> seg 2: [H3]; ray crossing a tiny bit above the lower endpoint; CNT++
<li> seg 3: [H4]; ray misses the upper endpoint of the seg, going a tiny bit above
<li> seg 4: [H3]; clean middle crossing, CNT++.
</ul>
<p>
Resulting CNT is 2, even: VP left-up of 'D' is outside of the solid red
(sitting in the hole).
<p>
From RP 'D' dir pointing left-down: same as the previous example, except
seg 2 is ignored and seg 3 is intersected because the ray is now a tiny
bit under their shared vertex. Same result.
<p>
From RP 'F', dir left-up or left-down: RP is not on a vertex; normal
[H3] mid-crossing for seg 7 and 10; resulting CNT is 2, even, VP is outside
(sitting in the hole on the left side of seg 7).
<p>
From RP 'G' dir pointing up-left:
<ul>
<li> seg 9: [H1]; ignored because it is horizontal
<li> seg 5: [H2.2]; both dir and seg going upward from RP, dir's endpoint is left of segment; CNT++
<li> seg 8: [H3]; CNT++ for middle crossing (a tiny bit above the lower endpoint)
<li> seg 10: [H3]; CNT++ for middle crossing
</ul>
<p>
Resulting CNT is 3, VP is in solid red.
<p>
From RP 'H' dir pointing up-left:
<ul>
<li> seg 9: [H1]; ignored because it is horizontal
<li> seg 8: [H3]; CNT++ for middle crossing (a tiny bit above the lower endpoint)
<li> seg 10: [H3]; CNT++ for middle crossing
</ul>
<p>
Resulting CNT is 2, VP is outside (sitting in the hole above H)
<p>
From RP 'J' dir pointing up-left 45 degree:
<ul>
<li> seg 9: [H1]; ignored because it is horizontal
<li> seg 8: [H2.2]; dir and seg both upward, dir's end being left of the seg: CNT++
<li> seg 10: [H3]; CNT++ for middle crossing
</ul>
<p>
Resulting CNT is 2, VP is outside (sitting in the hole above J, left of 8)
<p>
From RP 'J' dir pointing up-left 1 degree (almost vertical):
same as the previous example, except seg 8 is ignored because the dir
endpoint is on the right side of it so the final CNT is 1 and the result is
"inside the red solid": VP is above J, between seg 8 and the vertical black
grid line crossing J, close to the grid line.
<p>
From RP 'K' dir pointing up-left or down-left: RP is not on vertex;
16 is ignored ([H1] horizontal). [H3] middle crossing for 11, 19 and 20;
resulting CNT is 3, odd, VP is inside the red solid.
<p>
From RP 'L' left-up or left down: same, except the ray is not hitting 11
so the resulting CNT is 2, even, VP is outside the red solid.
<p>
From RP 'M' left-up:
<ul>
<li> [H2.1] ignore 15
<li> [H1] ignore 16
<li> [H3] middle cross 19 and 20
<ul>
<p> Resulting CNT is 2 (outside)
<p>
From RP 'M' left-down near-vertical:
<ul>
<li> [H2.2] ignore 15 (dir is right of)
<li> [H1] ignore 16
<li> [H3] middle cross 17, 19 and 20
<ul>
<p> Resulting CNT is 3 (inside)
<p>
The reset of the points are marked and labeled to serve as an exercise
for the reader.
|
