Geospatial technologies have come a long way since humans invented maps for navigation. In today’s times, these technologies encompass a wide range of sophisticated tools that help in geographical mapping of the earth. These maps provide crucial information that can be used to analyze trends and forecasts across geographies.
Geospatial solutions serve a multitude of areas including controlling social unrest in a specific region, containing a pandemic spread, weather forecasting, military applications, location-based advertising, finding the right location for an upcoming store, and many more. Some of the most prominent forms of geospatial technologies are remote sensing, global positioning systems (GPS), geographical information systems (GIS), and geofencing.
A geofence is a virtual perimeter within a real-world geographical region. It could either be plotted across a predefined set of boundaries or generated dynamically. Geofences use GPS technologies and range of IP addresses to create virtual fences. These fences can be used to track the physical location of any active device in a specific region.
Geofencing can be used for workplace security, theft alarms, child location services, notify tourists on safety issues, location-based targeting to serve relevant ads to customers, and so on.
Consider a hypothetical situation wherein, a departmental store chain wants to target those customers who are within a radius of N meters from any of their given store. The value of N could vary based on the store. Here, the Geofence is the combination of the latitude, longitude, and radius. So, if an ad request arrives with a given latitude and longitude, we should be able to return the list of fences that contains that point.
R-trees are tree data structures (balanced search tree) used for spatial access methods. They index multi-dimensional information such as geographical coordinates, rectangles, or polygons. The key idea of the data structure is to group nearby objects and represent them with the minimum bounding rectangle in one level up the tree hierarchy, where the "R" in R-tree depicts a rectangle. Since all the objects lie within this bounding rectangle, a query that does not intersect the bounding rectangle also cannot intersect any of the contained objects. At the leaf level, each rectangle describes a single object. At higher levels, the aggregation includes an increasing number of objects. This can also be seen as an increasingly coarse approximation of the data set.
R-tree Data Structure
Luckily, we already have an R-Tree library in Java that we could use:
Java Spatial Index - JSI (Java Spatial Index) RTree Library
Now we will go through the following steps:
Store fence data in R-Tree
Query the R-Tree
Create a square having the edge twice the radius and center at the latitude and latitude of the fence. Store this in the R-Tree data structure as shown in the code below.
Our fence is in the shape of a circle whereas the library being used stores rectangles in its nodes. In case you want a more accurate system you can create a custom library that inserts and queries circles into R-Tree. Here, since the error percentage is within permissible limits we can go with this implementation.
Once your R-Tree is inserted with your fences, it is ready for querying. You can query the R-Tree to return a list of objects for the given latitude and longitude using the code snippet below.
R-Tree data structures are one of the widely prevalent approaches in implementing geofences.
If you wish to learn more about geospatial solutions where we used S2 cells for geo targeting check out our blog How InMobi Serves Audience Using Geospatial Queries
Sign up with your email address to receive news and updates from InMobi Technology
