An algorithm for determining whether a point is inside a polygon. This is useful for applications ranging from computer graphics to autonomous vehicles.

** 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.