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
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).
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: