Point in Polygon: The Old Problem
5 mins
Calculating whether a point on a 2D plane is inside a polygon on the same plane is a computer science problem from the beginnings of time!
If you are building a desktop based program, it can be simple  set up a drawing canvas off screen and colour it white, draw the polygon and colour it black, then get the colour of the point  black for inside, white for outside.
But what about those of us without the luxury of a GPU to work it out for us?
Let’s define our problem, a complex polygon, with three points  which are inside it.
For now, we will deal with the case of solid polygons. Later we’ll discuss polygons with holes, and look at methods of dealing with them.
We also want to do this as computationally simply as possible  we don’t want to be waiting for answers, even for extremely complex polygons.
A solution to this problem involves drawing a horizontal line from outside the polygon to the point.
We count the number of times the line intersects the polygon  if it is odd the point is inside the polygon, even and it is outside.
This will give us the right answer every time, but is not as simple as it could be. Luckily, we can do a pretest to exclude some points which is simple  is the point inside the bounding box?
Finding the bounding box is relatively simple, and checking whether the point is inside the bounding box is also very simple.
If our point is inside our bounding box, we continue and work out the line intersections, but if it is outside it definitely can’t be in polygon!
So how do we work out the intersections? As we know the corners of the polygon (an array of points defines the polygon) we can iterate clockwise over the points and look at each side  do the line segments intersect?
If these line segments were in fact lines, we could simply work out the equations and solve them simultaneously. Actually, it turns out we can do this anyway, with certain additional conditions.
Let’s work out the equations first, and we could look at the conditions later. The corner we are looking at is i, the corner before is j and the point is p. So we define the coordinates as:
The horizontal line is easy:
For the polygon segment, we can use the general equation of a line, and substitute our variables:
We know the y coordinate where our lines intersect, so we just need to work out the x coordinate. Let’s solve the equations simultaneously and rearrange to find x:
We now know the coordinates of where the two lines intersect, but we really want to know if the line segments intersect.We do this by limiting the coordinates on the end points of the line. The y coordinate of the point must lie between the y coordinates of the polygon side  this test is the easiest, so we do this first. As you can see from the diagram, if the y coordinate of the intersect is outside these boundaries, it is not on the polygon side.
Finally, the most complex calculation  we use the equation we worked out earlier and solve it for x. If this is above 0 and below the x coordinate of the point, it lies on the horizontal line segment.
If our point has passed all these tests, it intersects with this side of the polygon. After we have iterated over each side, we add up all the intersects and see if it is odd or even  we have our answer!
So what about the code? Let’s look at an implementation in JavaScript. Assuming that we have an array of corners for our polygon:


And so on…
We can define a general function that takes a point and the array that defines the polygon:


Feel free to use this function is any of your projects.
By the way, the equations above were created using the excellent LaTeX equation editor. My thanks go out to Will Bateman and Steve Mayer!