Geo Fencing - Sample Code

My first blog was about geofencing (read it here). The point-in-polygon algorithm may seem easy enough, but when actually trying to implement it, you will notice that there are some tricky parts to it (like when your point is on the edge of the polygon, or when your polygon contains horizontal lines, etc.). Therefor, I've decided to add some java sample code.

So, here goes...

Points, lines and polygons

First, we'll create some objects to represent our points, lines and polygons:
A point is a position with an x- and an y-coordinate. To apply it to geofencing, you can just think of x-coordinates as longitudes and y-coordinates as latitudes.

A line is a straigth line with a direction (vertex). It has a from-point and a to-point. We will use it to represent the edges of our polygon.

A polygon, obviously, is a multi-sided shape that consists of a number of points.

Objective

Our objective is to create a method for calculating if we are inside the polygon or not.

As described in my first blog post, this method will:

• calculate the lines of the polygon
• filter the lines that intersect with our y-position
• calculate the exact points on which the lines intersect with the y-position
• sort the points by x-position
• use ray casting (out-in-out-in) algorithm for checking if we are inside or outside of the polygon.

In java, it would look something like this:

Now, let's try to implement each sub-method separately...

Calculate the polygon lines

First, the method for calculating the lines of a polygon.

We just take the points of the polygon and connect them together. We then close the polygon by connecting the last point to the first point:
There's no real magic here, it's a very simple method.

Filter the lines that intersect with the y-axis

Next, we need to filter the lines that intersect with our y-axis...

Calculate the x-intersection points at the y-axis

Next we calculate the x-intersection points of the lines at the given y-position, using the following method:

We calculate the x-position of every line, at the provided y, using standard calculus.

Sort the points by x-position

Sorting the points by X-position is easy, we just use a java double comparator:

Check if we are inside or outside of the polygon

And finally, we check if we are inside or outside the polygon, using the ray-casting algorithm:

Initially, we are outside of the polygon. At each point, we invert our status (inside - outside - inside - outside - ...). Until we have reached our x-position. We then know if we're inside or outside of the polygon.

That's it!

We just use simple java code, it can easily be ported to Android, iOS, ...

This code can still be optimized a lot, but the idea was to show how geofencing works (technically).

References:

http://stefanbangels.blogspot.be/2012/12/for-several-years-now-i-have-been.html

http://en.wikipedia.org/wiki/Point_in_polygon

http://en.wikipedia.org/wiki/Slope

http://en.wikipedia.org/wiki/Geo-fence
http://geomalgorithms.com/a03-_inclusion.html