Ray Casting Algorithm

An algorithm for determining whether a point is inside a polygon. This is useful for applications ranging from computer graphics to autonomous vehicles.
Note: This post assumes a basic knowledge of python. If you have never seen python then there is a good tutorial here.


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.

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.

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

        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:

    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

            if point.x < min(A.x, B.x): # The ray intersects with the edge
                inside = not inside

                m_edge = (B.y - A.y) / (B.x - A.x)
            except ZeroDivisionError:
                m_edge = _huge

                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

        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.

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.

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.