Geofencing Methods



On this page, I will discuss a couple of methods for geofencing GNSS-enabled tools. These are of particular interest to those developing high-altitude balloon and UAV devices, but can be applied in a variety of settings. Please note that many other methods exist, the following is intended as an entry point for beginners to GNSS and GIS development.


Radius

Radius geofences are the simplest to construct and compute. This is because there are only two waypoints required for comparison: a current position, and a center point. If the distance between the current position and the center point position are less than the radius of the geofence, the current position is known to be within the circular fence. See the example code below:

double current_pos[2] = {lat, lon};
double center_pos[2] = {lat, lon};
double fence_radius = radius;

double distance = haversine(current_pos, center_pos);
return distance <= fence_radius;

This requires the haversine formula, a mathematical operation to find the great-circle distance between two points on a sphere. There are more accurate methods that use models like WGS-84, but a spherical earth is practical for most uses. Naturally, if using a grid system rather than points of latitude and longitude, haversine is no longer necessary and one can simply find two-dimensional distance before comparing it to varius radii.


Polygon

Polygon geofencing can often be more practical for precision applications, but comes at the cost of additional memory allocation and CPU instructions. Rather than just a center point and radius, all external vertices for each polygon must be stored in a lookup table, however the operation required to determine whether or not one is inside a given fence remains relatively simple. There are a few methods for computing a polygon geofence - point-in-polygon, which is perhaps the most intuitive, and also ray-casting. Ray casting counts intersections with a ray from the current position, and determines whether or not the point is inside the geofence by whether or not the intersections are odd or even. Below you can see example code for the ray casting method:

int i, j, crossings = 0;
for (i = 0, j = n - 1; i < n; j = i++) {
double lat1 = polygon[i].lat, lon1 = polygon[i].lon;
double lat2 = polygon[j].lat, lon2 = polygon[j].lon;

if (((lat1 > p.lat) != (lat2 > p.lat)) &&
(p.lon < (lon2 - lon1) * (p.lat - lat1) / (lat2 - lat1) + lon1)) {
crossings++;
 }
}
return crossings % 2;

The reason that ray casting is superior to point-in-polygon methods is that it supports both convex and concave polygon shapes natively. This makes it a lightweight but powerful method for embedded systems without the need for floating point operations and trigonometry.


Practical Applications

Okay, okay, we get it! Math is cool or whatever. But what can all this be good for?


Sources

A great deal of what I know (and some of what I likely don't) can be found in Joseph O'Rourke's Computational Geometry in C. This is a fantastic book for programmers and mathematicians alike at any skill level.