Ray Casting  Polygon Containment
tags = [ Ray Casting, Geometry, Polygon Containment, EvenOdd Rule ]
Even before I learned the word algorithm, I have always enjoyed exacting solutions to problems. Particularly, I love very visual algorithms. Such algorithms include the symmetry, and also indirectness that you see when solving a Rubik’s Cube and other spatial puzzles. These puzzles certainly have formal grammars and systems defining these patterns, yet I was initially attracted to the visual “truth” of the solutions I found.
I unexpectedly found another such “puzzle” when I was building a reverse geocoding service. My first round with the service was to perform city lookup. In this scenario, since cities can be represented as points, a GeoHash lookup was the optimal solution.
However, what about checking to see if a geo coordinate is contained within a polygon? This polygon could be a country, a province, a county, or any custom area. We can make a GeoHash work with a few modifications. But there is another way to check for polygon containment.
Ray Casting
Upon discovering this simple but effective algorithm many years back, I was excited to finally put it to some use. Note that this algorithm is also sometimes referred to as the EvenOdd Rule. I prefer to call it Ray Casting as we will literally be casting a ray (vector), and then applying the evenodd rule to determine containment of some point within the polygon. I have also found that this algorithm is intuitive enough to excite people who aren’t familiar with algorithms.
The steps of the algorithm are simple.
 Pick a point that is obviously outside the solution space. For example, in the case of latitude and longitude points, we would select a point that is outside of the valid coordinate range. e.g.
(987.654, 876.543)
. This is the point where we will cast our ray from.  Next we will draw a line from the cast point defined in step 1. to the point we want to test.
 We will count how many lines in the polygon our ray intersects with. If the count is odd, the point is inside the polygon; if even, the point is outside.
Example with Square
First we will begin with a trivial example, a square. The square is denoted by blue lines and dots. We have a point p that we want to determine whether or not it is inside the square. We will cast our ray from a place to the left of the square. It is important that this ray be placed in a spot that is guaranteed to not exist in the polygon.
fig 1.
In fig 1, the ray travels from the cast point to point p without intersecting a single line of the square. The intersection count is zero, which is even, therefore the point is outside the square.
fig 2.
We will next look at an example where the point p lies to the right of the square. Our ray intersects two lines in the square, which is even, therefore the point is outside the square.
fig 3.
Our next example will be a point that lies in the square as illustrated in fig 3. Tracing our ray shows that it intersected with exactly one side of the square, which is odd, therefore our point is inside the square.
Example with Polygon
fig 4.
Next we will apply the algorithm to a more complex polygon illustrated above in fig 4.
fig 5.
For this test we are going to start with a point p that is soundly located inside the polygon, and cast a series of rays from outside to point p and count the number of times each ray intersects with a line in the polygon. If our algorithm holds, each ray will intersect with an odd number of lines. Each of the rays are labeled in fig 5.
Ray  Intersections 
r1  1 
r2  1 
r3  1 
r4  1 
r5  1 
r6  3 
r7  3 
It seems our luck holds. As expected, each ray intersects with our polygon an odd number of times. Each verifying that the point is inside the polygon.
fig 6.
Next, we will place point p outside of the polygon as seen in fig 6. Once again, we will cast rays from external points to point p and test our hypothesis that the number of intersections with the polygon should be even.
Ray  Intersections 
r1  2 
r2  0 
r3  0 
r4  2 
r5  2 
r6  2 
r7  4 
Assuming our counting is correct, the algorithm holds true. Each ray intersects with our polygon an even number of times. Each verifying that the point is outside the polygon.
Other Polygon types.
So far we have demonstrated Ray Casting with a simple concave and convex polygon. Ray Casting also works with complex polygons such as selfintersecting polygons and even polygons with holes in them.
Pitfalls
As with any algorithm, you can’t have your cake and eat it too.
Performance
The algorithm itself is a bit slow. It runs in O(n) as you have to check every line in the polygon. If you have m polygons, then it becomes m * O(n). Given complex polygons such as high resolution polygons used to describe country or province boundaries, n can approach or even surpass m, and it approaches O(n^2).
A solution to this is to not use high resolution geo polygons. Chances are you can achieve high accuracy even with low resolution polygons. Another options is to use GeoHashing techniques mentioned above, but they too incur their own costs, usually in terms of space/memory.
Another critical optimization is to calculate a bounding rectangle when you are processing the polygon data. You can do this by storing the (min_x, min_y)
and the (max_x, max_y)
. Once you have obtained a bounding rectangle, you should first perform rectangle containment before performing the expensive polygon containment check. Rectangle containment is substantially cheaper in practice. This will be demonstrated below.
Vertex Intersection
A ray may intersect a vertex in the polygon. Does this mean the ray intersected with a line or not? There is no correct answer to this and it is up to the application to determine how to handle this. That said, there are ways to decrease the chance of a ray intersecting with a vertex. The method I employ is to set the ray cast point to something obscure and with multiple decimal places. e.g. (987.654, 876.543)
.
An example can be constructed of a square located at (1, 1), (2, 1), (2, 2), (1, 2)
and point p is located in the center of the square at (1.5, 1.5)
. If a ray is cast from the origin, (0, 0)
, then it will overlap with the vertex located at (1, 1)
. By simply offsetting the ray cast point to something obscure like above, it won’t overlap.
It should also be noted that dealing with real data like geo coordinates, such an artificial construct is less likely to happen and you will still have to figure out how you want to count vertex intersection. In many cases it’s easy enough to just ignore and accept the error.
Java 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 

The core data structures used in 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 

Our custom Point class (using doubles)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 

A nice unit test to wrap everything up.
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 47 48 49 50 51 52 53 54 55 56 
