76 lines
4.1 KiB
Plaintext
76 lines
4.1 KiB
Plaintext
{{Wikipedia|Point_in_polygon}}
|
|
|
|
<br>
|
|
Given a point and a polygon, check if the point is inside or outside the polygon using the [[wp:Point in polygon#Ray casting algorithm|ray-casting algorithm]].
|
|
|
|
A pseudocode can be simply:
|
|
|
|
count ← 0
|
|
'''foreach''' side '''in''' polygon:
|
|
'''if''' ray_intersects_segment(P,side) '''then'''
|
|
count ← count + 1
|
|
'''if''' ''is_odd''(count) '''then'''
|
|
'''return''' inside
|
|
'''else'''
|
|
'''return''' outside
|
|
|
|
Where the function <tt>ray_intersects_segment</tt> return true if the horizontal ray starting from the point P intersects the side (segment), false otherwise.
|
|
|
|
An intuitive explanation of why it works is that every time we cross
|
|
a border, we change "country" (inside-outside, or outside-inside), but
|
|
the last "country" we land on is surely ''outside'' (since the inside of the polygon is finite, while the ray continues towards infinity). So, if we crossed an odd number of borders we were surely inside, otherwise we were outside; we can follow the ray backward to see it better: starting from outside, only an odd number of crossing can give an ''inside'': outside-inside, outside-inside-outside-inside, and so on (the - represents the crossing of a border).
|
|
|
|
So the main part of the algorithm is how we determine if a ray intersects a segment. The following text explain one of the possible ways.
|
|
|
|
[[Image:intersect.png|200px|thumb|right]]
|
|
Looking at the image on the right, we can easily be convinced of the fact that rays starting from points in the hatched area (like P<sub>1</sub> and P<sub>2</sub>) surely do not intersect the segment AB. We also can easily see that rays starting from points in the greenish area surely intersect the segment AB (like point P<sub>3</sub>).
|
|
|
|
So the problematic points are those inside the white area (the box delimited by the points A and B), like P<sub>4</sub>.
|
|
|
|
[[Image:posslope.png|128px|thumb|right]]
|
|
[[Image:negslope.png|128px|thumb|right]]
|
|
|
|
Let us take into account a segment AB (the point A having y coordinate always smaller than B's y coordinate, i.e. point A is always below point B) and a point P. Let us use the cumbersome notation PAX to denote the angle between segment AP and AX, where X is always a point on the horizontal line passing by A with x coordinate bigger than the maximum between the x coordinate of A and the x coordinate of B. As explained graphically by the figures on the right, if PAX is greater than the angle BAX, then the ray starting from P intersects the segment AB. (In the images, the ray starting from P<sub>A</sub> does not intersect the segment, while the ray starting from P<sub>B</sub> in the second picture, intersects the segment).
|
|
|
|
Points on the boundary or "on" a vertex are someway special and through this approach we do not obtain ''coherent'' results. They could be treated apart, but it is not necessary to do so.
|
|
|
|
An algorithm for the previous speech could be (if P is a point, Px is its x coordinate):
|
|
|
|
'''ray_intersects_segment''':
|
|
P : the point from which the ray starts
|
|
A : the end-point of the segment with the smallest y coordinate
|
|
(A must be "below" B)
|
|
B : the end-point of the segment with the greatest y coordinate
|
|
(B must be "above" A)
|
|
'''if''' Py = Ay '''or''' Py = By '''then'''
|
|
Py ← Py + ε
|
|
'''end''' '''if'''
|
|
'''if''' Py < Ay '''or''' Py > By '''then'''
|
|
'''return''' false
|
|
'''else''' '''if''' Px >= max(Ax, Bx) '''then'''
|
|
'''return''' false
|
|
'''else'''
|
|
'''if''' Px < min(Ax, Bx) '''then'''
|
|
'''return''' true
|
|
'''else'''
|
|
'''if''' Ax ≠ Bx '''then'''
|
|
m_red ← (By - Ay)/(Bx - Ax)
|
|
'''else'''
|
|
m_red ← ∞
|
|
'''end''' '''if'''
|
|
'''if''' Ax ≠ Px '''then'''
|
|
m_blue ← (Py - Ay)/(Px - Ax)
|
|
'''else'''
|
|
m_blue ← ∞
|
|
'''end''' '''if'''
|
|
'''if''' m_blue ≥ m_red '''then'''
|
|
'''return''' true
|
|
'''else'''
|
|
'''return''' false
|
|
'''end''' '''if'''
|
|
'''end''' '''if'''
|
|
'''end''' '''if'''
|
|
|
|
(To avoid the "ray on vertex" problem, the point is moved upward of a small quantity <big>ε</big>.)
|
|
<br><br>
|