Check if a point lies inside a convex polygon

Introduction

There are many problems where one needs to check if a point lies completely inside a convex polygon. Before moving into the solution of this problem, let us first check if a point lies left or right of a line segment. A polygon consists of more than two line segments ordered in a clockwise or anti-clockwise fashion. If a point lies left (or right) of all the edges of a polygon whose edges are in anticlockwise (or clockwise) direction then we can say that the point is completely inside the polygon.

Check if a point is on the right or on the left of a line segment

Consider a line segment $(a, b)$ given in the figure below. The coordinates of the end points of the line segments are $(x_1, y_1)$ and $(x_2, y_2)$ respectively. Consider a point $p(x, y)$ somewhere on the $xy$ plane.

To check if the point $p(x, y)$ lies on the left or on the right of the line segment $(a, b)$, we first express the equation of the line segment in the following format.
$$Ax + By + C = 0$$
The values of $A, B$ and $C$ can be calculated using the end points coordinates as $A = -(y_2 - y_1)$, $B = x_2 - x_1$ and $C = -(Ax_1 + By_1)$. A point $p(x, y)$ lies on the left of the line segment given by $A, B$ and $C$ if,
$$Ax + By + C > 0$$
Similarly, the point $p(x, y)$ lies on the right of the line if,
$$Ax + By + C < 0$$
Finally, the point lies exactly on the line if it satisfies the following relation.
$$Ax + By + C = 0$$

Check if a point lies inside the polygon

Now we know how to check if a point lies on the left of a line segment. Since a polygon is a combination of more than two line segments (or edges), we check if the point lies on the left of the each edge (or we check if the point lies on the right of the each edge if the edges are in clockwise direction). Consider a polygon $abcdefa$ and a point $p$ given in the figure below.

In order for the point $p$ to be completely inside the polygon $abcdefa$, it must lie on the left of edges $ab$, $bc$, $cd$, $de$, $ef$ and $fa$.

Program

So far we have discussed the mathematical solution of the problem. The same problem can be solved programmatically using any programming language. In this article, I use python programming language but the implementation is nearly same for almost all programming languages.

Data Structures

Data structure to represent a point is sufficient for this problem. We do not need a data structure for a line segment for this particular problem since the two extreme points (end points) are sufficient to represent a line segment. A point consists of two components, x-coordinate and y-coordinate. x and y coordinates are sufficient to uniquely represent a point in a 2D plane. The following python code snippet creates a point data structure.

1
2
3
4

class Point:
	def __init__(self, x, y):
		self.x = x
		self.y = y

An instance of the Point can be easily created by calling the constructor as Point(3,4) which creates a point with coordinates $(3, 4)$

Source Code

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

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def is_within_polygon(polygon, point):
    A = []
    B = []
    C = []  
    for i in range(len(polygon)):
        p1 = polygon[i]
        p2 = polygon[(i + 1) % len(polygon)]
        
        # calculate A, B and C
        a = -(p2.y - p1.y)
        b = p2.x - p1.x
        c = -(a * p1.x + b * p1.y)

        A.append(a)
        B.append(b)
        C.append(c)

    D = []
    for i in range(len(A)):
        d = A[i] * point.x + B[i] * point.y + C[i]
        D.append(d)

    t1 = all(d >= 0 for d in D)
    t2 = all(d <= 0 for d in D)
    return t1 or t2

if __name__ == '__main__':
    polygon = [Point(0, 0), Point(5, 0), Point(6, 7), Point(2, 3), Point(0, 4)]
    p1 = Point(1, 1)
    print is_within_polygon(polygon, p1) # returns True
    p2 = Point(6, 2)
    print is_within_polygon(polygon, p2) # returns False

Non-Convex Polygon??

If the polygon is not convex, the above trick does not work. Consider a polygon given below.

As you can see, the polygon is not a convex polygon. We want to know if a point $p$ is inside the polygon. In this case, we do the following

1. We draw a horizontal ray originating from the point $p$ and extend it towards infinity in the right direction as shown in the figure above.
2. We count the number of intersection the ray makes with the edges of the polygon.
3. If number of intersection is even, the point is outside the polygon otherwise it is inside the polygon.

There are two special (degenerate) cases we need to address.

1. If an edge of the polygon lie along the ray, we ignore that edge (we do not count this as an intersection). This is illustrated in the figure below.
   

2. If the ray passes through the vertex of the polygon (as shown in figure below), only count the edge whose other vertex lies below the ray.

References

1. Finding whether a point lies inside a rectangle or not. (2010, May 2). Retrieved August 19, 2018, from https://stackoverflow.com/questions/2752725/finding-whether-a-point-lies-inside-a-rectangle-or-not