Point Geo Fencing - Sample Code

Point Geo Fencing is easier than polygon Geo Fencing.

As described in my first blog (read it here), you just have to calculate the distance between the point and your current location, and compare it with the radius of your point (circle).

First we need an object for representing our Point Geo Fence:


When your radius is defined in meters, you will need the Haversine formula.  This formula will calculate the distance between two points (in meters) while taking into account the earth curvation:


Now, we can calculate if we're inside the Geo Fence or not:


X and Y are your current longitude and -latitude.
The method will return true, when we're inside the Geo Fence and false when we're not.

More information can be found here:
- http://en.wikipedia.org/wiki/Haversine_formula
- http://stefanbangels.blogspot.be/2012/12/for-several-years-now-i-have-been.html
- http://stefanbangels.blogspot.nl/2013/10/geo-fencing-sample-code.html

Odo Meter: Behind the Magic

An odo meter is a clever component that measures the total distance travelled (like the mileage counter in your car).

In Mobile software development, we also use an odo meter for calculating the travelled distance in:

• track-and-trace applications
• mileage administration applications
• sports tracker applications (like Endomondo, RunKeeper, Strava...)
• bike computers
• taxi meters
• ...

There are multiple strategies for calculating the total distance travelled.

STRATEGY 1: Calculate distance using delta time and current speed

Imagine a process that fetches the current GPS speed at a fixed interval of x time.

At each interval, we can calculate the distance by multiplying the delta time with the current speed:

d = v * t

for example (at an interval of 5 seconds, the current speed is 10 meters/second):

d = 10 meters/second * 5 seconds = 50 m

The problem with this strategy is that, in order to have an accurate result, time (t) has to be very small. In other words: you have to fetch the GPS speed a lot (draining your device battery).

A second problem is: sudden (short) accelerations, can cause an huge increase in distance, even if this speed has only occurred for just a little while... causing the result to be less accurate.

STRATEGY 2: Calculate distance between two points, at a fixed interval

Instead of fetching the GPS speed, we can also use the GPS position (longitude/latitude).

At each interval, we calculate the distance between the previous position and the current position.

As with the previous strategy, the results become more accurate when the interval becomes smaller. But the results aren't affected by speed fluctuations. The problem with this strategy is: we don't drive a straight line.  If we were driving circles, passing the same location at each interval, we could get into a situation where the calculated distance is zero.

STRATEGY 3: Calculate distance between positions, at a dynamic interval

When calculating the distance between positions at a dynamic interval instead of a fixed interval, we could decrease the problems of the previous strategies.

The interval can increase or decrease due to criteria like:

• movement detected by an hardware acceleration- or gyro-meter.
• ignition detected by an input port, canbus or sensing power drop.
• an on/off switch.
• increased speed levels at the previous interval.
• distance threshold (for example, see Android LocationManager).
• course changes (like a compass).
• maps street information.
• ...

Conclusion

Applications that operate in environments with a fairly stable speed (like space applications, airplanes, machine measurements, ...), strategy 1 (calculate distance using delta time and current speed) will be suitable.

But for most applications, strategy 2 (calculate distance between two points, at a fixed interval) will be the best solution.

Just keep in mind, when you require more control (to save battery life or in environments with repetitive reoccurring locations, ...), strategy 3 (calculate distance between positions at a dynamic interval) can also be a solution.

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

Geo Fencing: Behind the Magic

For several years now, I have been developing software for embedded systems. Not your everyday device (loaded with Android or iOS), but specialized devices: custom made devices for one customer or a group of customers. Its operating system is Linux, and you can basically run whatever-you-want on it (as long as it's ARM compiled).

The hardware architecture of the device is comparable with that of Beagle Board. On board you will find some add-ons (like for example: GPS, GPRS, WIFI, Bluetooth, In- and Output Ports, Serial Ports, Accelerometers, Gyrometers, Dallas Key, Temperature Sensors, Hydrometers, Ignition Detection, Canbus Interfacing, Touch Screen, etc) which can be used by my applications.

I have worked for a wide range of customers, in many different sectors, and have written a variety of applications (geotracking, geofencing, mileage/hour administration, driver profiling, canbus, car engine optimizers, taxi software, navigation software, task management, messaging, driver identification, radar detection, theft detection, etc).

Something I've noticed over all these years: in embedded development, there aren't that many different kinds of applications. The vast variety of applications can be reduced to only a hand ful. Of which geotracking and geofencing are considered the most popular.

I have been planning to write a blog for a while now. It's only logical that my first post will be on embedded software. As the subject reveiled: my first talk will be on geofencing, because it's popular and also because it's an interesting topic to talk about.

Geo Fencing

For the readers that are new to the topic, geofencing stands for geo (geographical) fencing (setting a perimeter). For me, geofencing really means: The process of checking whether an object (vehicle, person, animal, asset, etc) has entered or left a geographical area. This area can be pre-defined (calculation happens in real time on the device itself or on a server), or post-processed (the data is being stored and post-processed on a server).

Some applications of geofencing are:

• prisoner tracker systems (ankle monitor)
• notifying parents if their child leaves a designated area
• sending alerts when a vehicle leaves predefined borders (reporting a stolen vehicle)
• gps wildlife tracking: notifying rangers when wildlife leaves their habitat
• taxi drivers getting notified of customers in their current sector
• navigation software: knowing if the driver has reached its destination
• asset tracking: notifying when a power generator leaves a working site

For me, geofencing only means the process of checking if an object has entered or left an area. It doesn't dictate the actions to be taken whenever such an event happens. This is always application specific: sending an SMS, notifying a server, write to a log file, trigger an output port, play a sound, etc.

The form in which a geographical area is described, (in my applications) can be resolved to two different types: Point Geofencing (a circle, with a specific radius) and Polygon Geofencing

Point

Point geofencing is the easiest to implement. You just take the current GPS position of the device, and if the distance between the center of the point and current longitude/latitude is smaller than the radius of the point then you are inside the area. If not, you are outside of the area. It's just a small state machine that remembers the current state for each defined area.

For calculating the distance, take into account the earths curvature. Use the Haversine formula to calculate the distance between two points. Many code examples can be found on the web.

Some customers like to define two circles, with a different radius: one for entering, and one for leaving the area (a Schmitt Trigger, a threshold to filter GPS drift).

Polygon

Polygon Geofencing is a little bit more complicated, but still easy to implement. For detecting if the current longitude/latitude is inside the polygon, we use a simple algorithm called Ray Casting algorithm.

  This is a short description of the algorithm:

• Take the lines of the polygon, and retain only the lines of which the latitude (Y) intersects with the current latitude:

  Y1 < Y < Y2

• For each of the lines, calculate the exact longitude-position (X) at which each line intersects the current latitude (Y). To do this, first calculate the Slope (the steepness at which the Y of the line rises/drops for each change in X). For each line:

  m = (Y2 - Y1) / (X2 - X1)

Then, calculate the longitude (X) for each line at the current latitude (Y):

X = X1 + (Y - Y1) / m

• Sort the longitudes ascending.
• Iterate over all longitudes. The first longitude you cross, you are inside the polygon. The second longitude, you are outside again. The third, you are in again, ...

• Compare your current longitude with the longitudes that you've iterated, to determine if you're inside or outside the polygon area.

Keep in mind that this algorithm also doesn't take into account earth curvature. So for big areas, the calculation can be inaccurate. But for most applications, this approach is good enough.

The difficulty in implementing this algorithm lies in the special cases: when your point is on the border of the polygon or when your polygon contains horizontal lines (calculating your slope will cause a divide by zero).

For a code sample, read my next blogs:
http://stefanbangels.blogspot.be/2013/10/geo-fencing-sample-code.html
http://stefanbangels.blogspot.be/2014/03/point-geo-fencing-sample-code.html