*Note: This post assumes a basic knowledge of python. If you have never seen python then there is a good tutorial here.*

## Introduction

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

## Defining Point and Polygon

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
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.

1 2 3 4 5 6 7 8 9 10 |
@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 |

## The Algorithm

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.

## The Code

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:

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

## A Few Tests

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
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.