Building a scalable geofencing API on Google’s App Engine

Building a scalable geofencing API on Google’s App Engine

Posted: Thursday, December 11, 2014

  

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 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.

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061

package com.google.appengine.geo.fencing; /** The object model for the data we are sending through endpoints */ public class MyFence { private long id = -1; public String name; public String entityGroup; public String description; public double[][] vertices; public MyFence() {}; public MyFence(long id, String name, String entityGroup, String description, double[][] vertices) { this.id = id; this.name = name; this.entityGroup = entityGroup; this.description = description; this.vertices = vertices; } public long getId() { return id; } public void setId(long id) { this.id = id; } public String getName() { return name; } public void setName(String name) { this.name = name; } public String getEntityGroup() { return entityGroup; } public void setEntityGroup(String entityGroup) { this.entityGroup = entityGroup; } public String getDescription() { return description; } public void setDescription(String description) { this.description = description; } public double[][] getVertices() { return vertices; } public void setVertices(double[][] vertices) { this.vertices = vertices; } }

view rawMyFence.java hosted with ❤ by GitHub

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.

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950

@ApiMethod(name = "add", httpMethod = "post", path = "add") public MyFence addFence(@Named("group") String group, @Named("index") boolean buildIndex, MyFence fence) { //Get the last fences' id. DatastoreService datastore = DatastoreServiceFactory.getDatastoreService(); Key fenceKey = KeyFactory.createKey("Geofence", group); long nextId; if (fence.getId() != -1) { nextId = fence.getId(); } else { long lastId; Query query = new Query("Fence", fenceKey).addSort("id", Query.SortDirection.DESCENDING); List < Entity > lastFence = datastore.prepare(query).asList(FetchOptions.Builder.withLimit(1)); if (lastFence.isEmpty()) { lastId = -1; } else { lastId = (long) lastFence.get(0).getProperty("id"); } nextId = lastId + 1; } //Create new Entity with nextId. Entity fenceEntity = new Entity("Fence", fenceKey); fenceEntity.setProperty("id", nextId); fenceEntity.setProperty("name", fence.getName()); fenceEntity.setProperty("description", fence.getDescription()); Gson gson = new Gson(); String jsonString = gson.toJson(fence.getVertices()); //Convert to DataStore-Text-Object to store the vertices. Text jsonText = new Text(jsonString); fenceEntity.setProperty("vertices", jsonText); //Write to DataStore. datastore.put(fenceEntity); MyFence newFence = new MyFence(); newFence.setId(nextId); //Rebuild the Index. if (buildIndex) { try { MyIndex.buildIndex(group); } catch (IOException e) { e.printStackTrace(); } } return newFence; }

view rawaddFence_snippet.java hosted with ❤ by GitHub

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.

12345678910111213141516171819202122232425262728

@ApiMethod(name = "list", httpMethod = "get", path = "list") public ArrayList < MyFence > listFences(@Named("group") String group) { ArrayList < MyFence > fences = new ArrayList < MyFence > (); DatastoreService datastore = DatastoreServiceFactory.getDatastoreService(); Key fenceKey = KeyFactory.createKey("Geofence", group); Query query = new Query("Fence", fenceKey).addSort("id", Query.SortDirection.DESCENDING); List < Entity > fencesFromStore = datastore.prepare(query).asList(FetchOptions.Builder.withDefaults()); if (fencesFromStore.isEmpty()) { return fences; } else { for (Entity fenceFromStore: fencesFromStore) { long id = (long) fenceFromStore.getProperty("id"); String name = (String) fenceFromStore.getProperty("name"); String description = (String) fenceFromStore.getProperty("description"); Gson gson = new Gson(); Text vText = (Text) fenceFromStore.getProperty("vertices"); String vString = vText.getValue(); double[][] vertices = gson.fromJson(vString, double[][].class); MyFence tempFence = new MyFence(id, name, group, description, vertices); fences.add(tempFence); } return fences; } }

view rawlistFences_snippet.java hosted with ❤ by GitHub

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.

12345678910111213141516171819202122

@ApiMethod(name = "getById", httpMethod = "get", path = "getById") public ArrayList < MyFence > getFenceById(@Named("group") String group, @Named("id") long id) { DatastoreService datastore = DatastoreServiceFactory.getDatastoreService(); Key fenceKey = KeyFactory.createKey("Geofence", group); Filter propertyFilter = new FilterPredicate("id", FilterOperator.EQUAL, id); Query query = new Query("Fence", fenceKey).setFilter(propertyFilter); Entity fenceFromStore = datastore.prepare(query).asSingleEntity(); ArrayList < MyFence > fences = new ArrayList < MyFence > (); if (fenceFromStore != null) { String name = (String) fenceFromStore.getProperty("name"); String description = (String) fenceFromStore.getProperty("description"); Gson gson = new Gson(); Text vText = (Text) fenceFromStore.getProperty("vertices"); String vString = vText.getValue(); double[][] vertices = gson.fromJson(vString, double[][].class); MyFence tempFence = new MyFence(id, name, group, description, vertices); fences.add(tempFence); } return fences; }

view rawgetFenceById_snippet.java hosted with ❤ by GitHub

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.

1234567891011121314151617181920212223242526272829303132

//Get all fences of group from DataStore. DatastoreService datastore = DatastoreServiceFactory.getDatastoreService(); Key fenceKey = KeyFactory.createKey("Geofence", group);   Query query = new Query("Fence", fenceKey).addSort("id", Query.SortDirection.DESCENDING); List < Entity > fencesFromStore = datastore.prepare(query).asList(FetchOptions.Builder.withDefaults());   if (!fencesFromStore.isEmpty()) { //Create STRTree-Index. STRtree index = new STRtree(); //Loop through the fences from DataStore. for (Entity fenceFromStore: fencesFromStore) { long id = (long) fenceFromStore.getProperty("id"); Gson gson = new Gson(); Text vText = (Text) fenceFromStore.getProperty("vertices"); String vString = vText.getValue(); double[][] vertices = gson.fromJson(vString, double[][].class);   //Store coordinates in an array. Coordinate[] coordinates = new Coordinate[vertices.length]; int i = 0; for (double[] point: vertices) { Coordinate coordinate = new Coordinate(point[0], point[1]); coordinates[i++] = coordinate; } //Create polygon from the coordinates. GeometryFactory fact = new GeometryFactory(); LinearRing linear = new GeometryFactory().createLinearRing(coordinates); MyPolygon polygon = new MyPolygon(linear, null, fact, id); //Add polygon to index. index.insert(polygon.getEnvelopeInternal(), polygon); }

view rawMyIndex_add_polys_snippet.java hosted with ❤ by GitHub

You then build the index and write it to memcache for fast read access.

123456

//Build the index. index.build(); //Write the index to Memcache. MemcacheService syncCache = MemcacheServiceFactory.getMemcacheService(); //Last param is expiration date. Set to null to keep it in Memcache forever. syncCache.put(group, index, null);

view rawMyIndex_build_snippet.java hosted with ❤ by GitHub

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.

12345678910111213141516171819202122232425262728293031

@ApiMethod(name = "point", httpMethod = "get", path = "point") public ArrayList < MyFence > queryPoint(@Named("group") String group, @Named("lng") double lng, @Named("lat") double lat) { ArrayList < MyFence > fences = new ArrayList < MyFence > ();   //Get the Index from Memcache. MemcacheService syncCache = MemcacheServiceFactory.getMemcacheService(); GeometryFactory gf = new GeometryFactory(); STRtree index = (STRtree) syncCache.get(group); // read from cache if (index != null) { Coordinate coord = new Coordinate(lng, lat); Point point = gf.createPoint(coord); List < MyPolygon > items = index.query(point.getEnvelopeInternal()); if (!items.isEmpty()) { for (MyPolygon poly: items) { if (poly.contains(point)) { long id = poly.getID(); MyFence newFence = new MyFence(); newFence.setId(id); fences.add(newFence); } } } } else { try { MyIndex.buildIndex(group); } catch (IOException e) { e.printStackTrace(); } } return fences; }

view rawqueryPoint_snippet.java hosted with ❤ by GitHub

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.

123456789101112131415161718192021222324252627282930313233343536373839404142

@ApiMethod(name = "polyline", httpMethod = "post", path = "polyline") public ArrayList < MyFence > queryPolyLine(@Named("group") String group, MyPolyLine polyline) { ArrayList < MyFence > fences = new ArrayList < MyFence > ();   //Get the index from Memcache. MemcacheService syncCache = MemcacheServiceFactory.getMemcacheService(); GeometryFactory gf = new GeometryFactory(); STRtree index = (STRtree) syncCache.get(group); // read from cache if (index != null) { //Create coordinate array. double[][] points = polyline.getCoordinates(); Coordinate[] coordinates = new Coordinate[points.length]; int i = 0; for (double[] point: points) { Coordinate coordinate = new Coordinate(point[0], point[1]); coordinates[i++] = coordinate; } //Create polyline. GeometryFactory fact = new GeometryFactory(); LineString linestring = new GeometryFactory().createLineString(coordinates);   List < MyPolygon > items = index.query(linestring.getEnvelopeInternal()); if (!items.isEmpty()) { for (MyPolygon poly: items) { if (linestring.crosses(poly) || poly.contains(linestring)) { long id = poly.getID(); MyFence newFence = new MyFence(); newFence.setId(id); fences.add(newFence); } } } } else { try { MyIndex.buildIndex(group); } catch (IOException e) { e.printStackTrace(); } }   return fences; }

view rawpolyline_snippet.java hosted with ❤ by GitHub

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.

123456789101112131415161718192021222324252627282930313233343536373839404142

@ApiMethod(name = "polygon", httpMethod = "post", path = "polygon") public ArrayList < MyFence > queryPolygon(@Named("group") String group, MyPolyLine polyline) { ArrayList < MyFence > fences = new ArrayList < MyFence > ();   //Get index from Memcache MemcacheService syncCache = MemcacheServiceFactory.getMemcacheService(); STRtree index = (STRtree) syncCache.get(group); // read from cache if (index != null) { //Create coordinate array. double[][] points = polyline.getCoordinates(); Coordinate[] coordinates = new Coordinate[points.length]; int i = 0; for (double[] point: points) { Coordinate coordinate = new Coordinate(point[0], point[1]); coordinates[i++] = coordinate; } //Create polygon. GeometryFactory fact = new GeometryFactory(); LinearRing linear = new GeometryFactory().createLinearRing(coordinates); Polygon polygon = new Polygon(linear, null, fact);   List < MyPolygon > items = index.query(polygon.getEnvelopeInternal()); if (!items.isEmpty()) { for (MyPolygon poly: items) { if (polygon.contains(poly) || !polygon.disjoint(poly)) { long id = poly.getID(); MyFence newFence = new MyFence(); newFence.setId(id); fences.add(newFence); } } } } else { try { MyIndex.buildIndex(group); } catch (IOException e) { e.printStackTrace(); } }   return fences; }

view rawpolygon_snippet.java hosted with ❤ by GitHub

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.