Problem: Given a point and a polygon, test if the point is inside the polygon.
Solution: In this post we will implement a Ray-casting algorithm that, if given a point $P$, and a polygon $Q$, will return a value of true if $P$ is inside $Q$ and false otherwise. The algorithm starts with $P$ and traces a ray in any direction, counting the number of times the ray intersects with $Q$. If the ray intersects with $Q$ an even number of times then $P$ is outside of $Q$ as seen in Figure 1. If the ray intersects with $Q$ an odd number of times then $P$ is inside the polygon as seen in Figure 2.
Before implementing the algorithm we implement two classes, Point and Polygon. For simplicity we will assume that a Polygon is instantiated with a list of Point's in clockwise order.
class Point:
def __init__(self, x, y):
"""
A point specified by (x,y) coordinates in the cartesian plane
"""
self.x = x
self.y = y
class Polygon:
def __init__(self, points):
"""
points: a list of Points in clockwise order.
"""
self.points = points
To make the polygon class easier to work with, we create a method that returns the edges of a polygon. The method loops through all the points in the polygon creating tuples of each two connected points.
@property
def edges(self):
''' Returns a list of tuples that each contain 2 points of an edge '''
edge_list = []
for i,p in enumerate(self.points):
p1 = p
p2 = self.points[(i+1) % len(self.points)]
edge_list.append((p1,p2))
return edge_list
Now we can start with the actual algorithm. The algorithm will have 2
inputs, a polygon and a point. We will refer to the point as $P$ and the
polygon as $Q$. We will refer to the ray, starting at $P$ and going right
to infinity, as $R$.
First, we will initialize a boolean variable called inside
that will be toggled each time we find an edge intersected by $R$. By
initializing inside to false, we can be sure that the final
value of inside will be true if $P$ is inside $Q$ and false
if $P$ is outside of $Q$.
Next, the algorithm will loop through all the edges in $Q$ and test whether
$R$ intersects with each edge. For each edge, we set two variables $A$ and
$B$, corresponding to the edge's points such that $A$ always has a y value
less than $B$. The following figures demonstrate this.
We must also check to see if $P$ is at the same level as a vertex of the polygon. If $R$ intersects with a vertex on $Q$, there is a chance that $P$ is outside $Q$ and only has a one intersection instead of two. To remedy the situation we add a small epsilon value to any point that has the same y-value as a vertex of $Q$. The next step is to check if $P$ is above or below each edge. To check this we can check the truth of the following two statements: $$ P_{y} > B_{y} \\ P_{y} < A_{y} $$ If either of these statments is true, then $P$ is above or below the dotted lines shown in Figure 5 and $R$ does not intersect with the edge. We can also check to see if $P$ is to the right of the edge using the following statement: $$ P_{x} > max(A_{x}, B_{x}) $$ If this statement is true then $P$ is to the right of the dotted line in Figure 6 and, again, $R$ does not intersect with the edge.
We can now be sure that $P$ is somewhere in the red or green section of the rectangle in Figure 7. For the final part of the algorithm we must determine the cases where $P$ is in the green section of the rectangle and the cases where $P$ is in the red section of the rectangle. If $P$ is in the green section, $R$ intersects with the edge. If $P$ is in the red section, $R$ does not intersect with the edge.
The first step is to check if $P$ is to the left of both $A$ and $B$. If this is the case, then we can be sure that $P$ is not in the red region and therefore intersects with the edge. This limits our search to the rectangle shown below.
Finally, we can check the slopes of the line segments $\overrightarrow{AB}$ and $\overrightarrow{AP}$. If the slope of $\overrightarrow{AP}$ is greater than the slope of $\overrightarrow{AB}$ then we know that $R$ intersects with the edge. The figure below is an interactive demo that shows how the position of $P$ affects the slope.
To implement the algorithm we will add a contains method to
the polygon class. To use the method you create a polygon and pass a point
to the polygon's contains method. The method will then return
a boolean value based on whether the point is inside the polygon or not.
Here is the final implementation of the algorithm:
def contains(self, point):
import sys
# _huge is used to act as infinity if we divide by 0
_huge = sys.float_info.max
# _eps is used to make sure points are not on the same line as vertexes
_eps = 0.00001
# We start on the outside of the polygon
inside = False
for edge in self.edges:
# Make sure A is the lower point of the edge
A, B = edge[0], edge[1]
if A.y > B.y:
A, B = B, A
# Make sure point is not at same height as vertex
if point.y == A.y or point.y == B.y:
point.y += _eps
if (point.y > B.y or point.y < A.y or point.x > max(A.x, B.x)):
# The horizontal ray does not intersect with the edge
continue
if point.x < min(A.x, B.x): # The ray intersects with the edge
inside = not inside
continue
try:
m_edge = (B.y - A.y) / (B.x - A.x)
except ZeroDivisionError:
m_edge = _huge
try:
m_point = (point.y - A.y) / (point.x - A.x)
except ZeroDivisionError:
m_point = _huge
if m_point >= m_edge:
# The ray intersects with the edge
inside = not inside
continue
return inside
Now that we understand the algorithm and have the code fully written, it's time to make a few test cases. Below are a few test cases I have created to demonstrate the code that was written above.
if __name__ == "__main__":
q = Polygon([Point(20, 10),
Point(50, 125),
Point(125, 90),
Point(150, 10)])
# Test 1: Point inside of polygon
p1 = Point(75, 50);
print "P1 inside polygon: " + str(q.contains(p1))
# Test 2: Point outside of polygon
p2 = Point(200, 50)
print "P2 inside polygon: " + str(q.contains(p2))
# Test 3: Point at same height as vertex
p3 = Point(35, 90)
print "P3 inside polygon: " + str(q.contains(p3))
# Test 4: Point on bottom line of polygon
p4 = Point(50, 10)
print "P4 inside polygon: " + str(q.contains(p4))
Figure 9 shows a graphical representation of the test cases above. The green dots correspond to the points that are evaluated as inside the polygon and black dots correspond to the points that are evaluated as outside the polygon.
Output:
>>>
P1 inside polygon: True
P2 inside polygon: False
P3 inside polygon: False
P4 inside polygon: True
Notice that the point on the bottom line of the polygon evaluates to being inside the polygon. This is caused when a point and a vertex on the polygon are at the same height, and the point is moved up an epsilon value.
One of the nice things about this algorithm is that it is easy to implement and has a runtime of $O(n)$. This makes it useful in computer graphics for applications such as hit-testing.