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