Unless you are a math nerd you will likely skip this article right about… now.

For those math nerds that are still reading, I learned something new today that I found interesting.   It makes perfect sense and is one of those “why didn’t I think of this” moments.  Working on a territories algorithm for Store Locator Plus presented a problem I’ve not had to solve in the past 4 years of building the production.   How do you determine if a given point on earth is inside of an area that is described by a series of locations that represent the boundary of a territory.  In plain English – “When a user says ‘I am here’, is ‘here’ within the territory serviced by a company?”

Point In Polygon Algorithms

There are a number of ways to determine if ‘here’ is inside a given area.  In mathematics locating ‘here’ in a territory can be directly associated with the point in polygon problem.   ‘Here’ is the point where the user is now and the latitude/longitude combination represent the x,y coordinates for that point.   The polygon is described as a series of latitude/longitude (x,y) coordinates that form the outline of a polygon.   You can now employ a number of algorithms to calculate if a point is inside the polygon, such as the “Winding number” algorithm.   However my favorite is the “Even Odd Rule” algorithm due to its simplicity and the speed at which it can be computed.    Winding number uses “circular math” which involves things like sine and cosine which are computationally expensive.

Even Odd Rule

Even Odd Rule uses the given point and creates a ray from that point that traverses at least one side of the polygon.   If the ray crosses an even number of borders it is outside the polygon.  if it crosses an odd number it is in the polygon.   There is a caveat where if it is ON the border it will be considered “outside” but that can be a matter of semantics ; “you said INSIDE not on the edge”.   Also , for territories the < 1 meter of distance that Store Locator Plus uses with floating point decimals representing latitude/longitude, it is probably fine to lose that 1 meter to the “on the border” rule.

Calculating the number of “border crossings” is fairly easy and operates quickly unless you have an extremely complex polygon with thousands of points prescribing the border.  That won’t be the case for my product.  The efficiency and accuracy of this algorithm is perfect.

Sometimes you can discover beauty in the simplicity of what otherwise can seem like a complex problem by using math to describe your world.

Yes I know.  I’m a math geek.