Building a scalable geofencing API on Google’s App Engine

December 11, 2014


Link copied to clipboard
Thorsten Schaeff has been studying Computer Science and Media at the Media University in Stuttgart and the Institute of Art, Design and Technology in Dublin. For the past six months he’s been interning with the Maps for Work Team in London, researching best practice architectures for working with big geo data in the cloud.

Google’s Cloud Platform offers a great set of tools for creating easily scalable applications in the cloud. In this post, I’ll explore some of the special challenges of working with geospatial data in a cloud environment, and how Google’s Cloud can help. I’ve found that there aren’t many options to do this, especially when dealing with complicated operations like geofencing with multiple complex polygons. You can find the complete code for my approach on GitHub.

Geofencing is the procedure of identifying if a location lies within a certain fence, e.g. neighborhood boundaries, school attendance zones or even the outline of a shop in a mall. It’s particularly useful in mobile applications that need to apply this extra context to someone’s exact location. This process isn’t actually as straight forward as you’d hope and, depending on the complexity of your fences, can include some intense calculations and if your app gets a lot of use, you need to make sure this doesn’t impact performance.

In order to simplify this problem this blogpost outlines the process of creating a scalable but affordable geofencing API on Google’s App Engine.

And the best part? It’s completely free to start playing around.
geofencing_API_example.PNG
Geofencing a route through NYC against 342 different polygons that resulted from converting the NYC neighbourhood tabulation areas into single-part polygons.

Getting started

To kick things off you can work through the Java Backend API Tutorial. This uses Apache Maven to manage and build the project.

If you want to dive right in you can download the finished geofencing API from my GitHub account.

The Architecture

The requirements are:

  • Storing complex fences (represented as polygons) and some metadata like a name and a description. For this I use Cloud Datastore, a scalable, fully managed, schemaless database for storing non-relational data. You can even use this to store and serve GeoJSON to your frontend.
  • Indexing these polygons for fast querying in a spatial index. I use an STR-Tree (part of JTS) which I store as a Java Object in memcache for fast access.
  • Serving results to multiple platforms through HTTP requests. To achieve this I use Google Cloud Endpoints, a set of tools and libraries that allow you to generate APIs and client libraries.

That’s all you need to get started - so let’s start cooking!

Creating the Project

To set up the project simply use Apache Maven and follow the instructions here. This creates the correct folder structure, sets up the routing in the web.xml file for use with Google’s API Explorer and creates a Java file with a sample endpoint.

Adding additional Libraries

I’m using the Java Topology Suite to find out which polygon a certain latitude-longitude-pair is in. JTS is an open source library that offers a nice set of geometric functions.

To include this library into your build path you simply add the JTS Maven dependency to the pom.xml file in your project’s root directory.

In addition I’m using the GSON library to handle JSON within the Java backend. You can basically use any JSON library you want to. If you want to use GSON import this dependency.

Writing your Endpoints

Adding Fences to Cloud Datastore

For the sake of convenience you’re only storing the fences’ vertices and some metadata. To send and receive data through the endpoints you need an object model which you need to create in a little Java Bean called MyFence.java.

https://gist.github.com/tschaeff/778b12fb116c36e3c08c
Now you need to create an endpoint called add. This endpoint expects a string for the group name, a boolean indicating whether to rebuild the spatial index, and a JSON object representing the fence’s object model. From this App Engine creates a new fence and writes it to Cloud Datastore.

https://gist.github.com/tschaeff/02840865b7a25f75f014

Retrieving a List of our Fences

For some use cases it makes sense to fetch all the fences at once in the beginning, therefore you want to have an endpoint to list all fences from a certain group.

Cloud Datastore uses internal indexes to speed up queries. If you deploy the API directly to App Engine you’re probably going to get an error message, saying that the Datastore query you’re using needs an index. The App Engine Development server can auto-generate the indexes, therefore I’d recommend testing all your endpoints on the development server before pushing it to App Engine.

https://gist.github.com/tschaeff/7d20d452f0890ef9b339

Getting a Fence’s Metadata by its ID

When querying the fences you only return the ids of the fences in the result, therefore you need an endpoint to retrieve the metadata that corresponds to a fence’s id.

https://gist.github.com/tschaeff/1b7b0ec5a987bdc697fe

Building the Spatial Index

To speed up the geofencing queries you put the fences in an STR tree. The JTS library does most of the heavy lifting here, so you only need to fetch all your fences from the Datastore, create a polygon object for each one and add the polygon’s bounding box to the index.

https://gist.github.com/tschaeff/ae7279e8d0e5317e4862
You then build the index and write it to memcache for fast read access.

https://gist.github.com/tschaeff/b432537502080f648ede

Testing a point

You want to have an endpoint to test any latitude-longitude-pair against all your fences. This is the actual geofencing part. That’s so you will be able to know, if the point falls into any of your fences and if so, it should return the ids of the fences the point is in.

For this you first need to retrieve the index from memcache. Then query the index with the bounding box of the point which returns a list of polygons. Since the index only tests against the bounding boxes of the polygons, you need to iterate through the list and test if the point actually lies within the polygon.

https://gist.github.com/tschaeff/5ea0eae9b7e7399af065

Querying for a Polylines or Polygons

The process of testing for a point can easily be adapted to test the fences against polylines and polygons. In the case of polylines you query the index with the polyline’s bounding box and then test if the polyline actually crosses the returned fences.

https://gist.github.com/tschaeff/b23844335ec70688ea4c
When testing for a polygon you want to get back all fences that are either completely or partly contained in the polygon. Therefore you test if the returned fences are within the polygon or are not disjoint. For some use cases you only want to return fences that are completely contained within the polygon. In that case you want to delete the not disjoint test in the if clause.

https://gist.github.com/tschaeff/b23844335ec70688ea4c

Testing & Deploying to App Engine

To test or deploy your API simply follow the steps in the ‘Using Apache Maven’ tutorial.

Scalability & Pricing

The beauty of this is, since it’s running on App Engine, Google’s platform as a service offering, it scales automatically and you only pay for what you use.

If you want to insure best performance and great scalability you should consider to switch from the free and shared memcache to a dedicated memcache for your application. This guarantees enough capacity for your spatial index and therefore ensures enough space even for a large amount of complex fences.

That’s it - that’s all you need to create a fast and scalable geofencing API.
Preview: Processing Big Spatial Data in the Cloud with Dataflow
In my next post I will show you how I geofenced more than 340 million NYC Taxi locations in the cloud using Google’s new Big Data tool called Cloud Dataflow.