Building Your Own Geofence Server

Well, it looks like I might have peaked your interest enough from the previous post for you to keep reading. Good for me! If you’ve stumbled across this post, then you might want to know that it is part of a series (of which you are reading part 2). If you wish to read (or re-read) part 1, you can do so here.

In this post, I’m going to walk you through the mechanics of creating a (very) simple geofence server. We’ll start first with the conceptual approach that we will be taking, then we’ll see how we can make those ideas a reality. And, when it is all said and done, I have a little surprise for you.

Conceptual Approach

Before we get into the nitty-gritty details, we’ll go over the conceptual approach that we will be taking. My hope is that the theoretical foundation will aid in understanding the concrete details.

Utilizing Mongo

As we’re planning our geofence server, we know we want to use existing technologies, where possible, to aid in development time. In this example, we’re going to use some of the geo-spatial indexing and search features that are available in Mongo.

In particular, Mongo allows you index Lat-Lon points and search within a specified radius. To visualize this, I’ve put together a map full of points (on the left) and a nearby-search query with a specified radius (on the right) for you below.

Mongo geo-spatial index and query visualization

Although Mongo does not currently provide support for full-featured geofences, this particular feature will save us a lot of time as we build our own geofence server.

Geofences as Grids

Knowing that we can utilize Mongo’s geo-spatial indexing capabilities with points, we now have to think about how we can store our geofence within Mongo as a set of points (so that we can most take advantage of the hard work that the open source community has put into Mongo).

My approach is to visualize that we are drawing our geofence (really just a polygon) on a grid. Then we can estimate our polygon by using only the grid-blocks that lie within the polygon (or at least their center-points lie within the polygon). We can then take the estimated polygon (the set of grid-blocks) and get their center-points. It is these center-points which we can then store in Mongo.

polygon estimation with grids, grid-blocks, and center-points

You might thinking that this is all fine and dandy, but how are we going to use this to determine if someone or something is inside or outside of the fence?

Simple! If we think of each point as the conceptual grid-block, from which the point was derived, then we can do a nearby-search in Mongo with a radius of one-half the length of the diagonal of the grid-block (plus a little extra to account for some rare edge-cases). To illustrate:

polygon query with points and nearby-search

Voilà! Now if you search the points (your geofence) with a specific point and the pre-determined radius, you’ll either get back 0 points (meaning that you are outside of the fence) or 1 to 4 points (meaning that you are inside of the fence).

Turning Polygons into Grids

So far, things have been pretty easy (although possibly not easy to follow along the first time through) conceptually. Now you might have to get some pin a paper out to draw this next piece to fully understand how we are going to do this.

Our objective is to turn a random, regular polygon into a set of grid-blocks which estimate its shape. We’re going to be using an algorithm similar to how you get the area of a polygon. I’ll give you the steps, then I’ll lay it out visually for you.

  1. Create an array to contain your estimated polygon (array of grid-blocks), we’ll call it E
  2. Generate a grid that contians your polygon
  3. For each latitude (y-value on an x-y plane), draw a horizontal line
  4. For each area in-between the horizontal lines:
    1. Get all grid-blocks that are between the lines, we’ll call this list G
    2. Get all lines that intersect the horizontal-section, and for each one, called l:
      1. Get all grid-blocks in G to the left of l, called G2
      2. For each grid-block in G2, called g:
        1. If g is in E, remove g from E
        2. If g is not in E, add g to E
  5. Store grid-block center-points from E in Mongo. Done!


If you didn’t quite follow that (or can’t visualize that well), then no worries. Here is a visual:

detailed estimation visualization 1 detailed estimation visualization 2 detailed estimation visualization 3

Coding Time

Okay, now that we have gone through evertyhing at the conceptual level, it’s time for some real code. If you had any trouble understanding the previous sections, it will be worth your time to go back with pen and paper and draw out all of the steps until it makes sense.

Creating Our Grid

Assuming that we’re going to get out polygon in the form of some Lat-Lon points, then we can generate our grid like the following:

 1 # Assuming that the coordinates for the polygon adhere to the
 2 # format of:
 3 # [
 4 #   [:lon, :lat],
 5 #   [:lon, :lat],
 6 #   ...
 7 # ]
 8 #
 9 # We can use the following methods:
10  
11  
12  
13 # Method to get the min and max values for the polygon (plus
14 # some padding) that the grid can be generated within
15 def get_bounding_box(coords)
16   # get max and min coords
17   max = coords.inject({lat:0, lon:0}) do |max, c|
18     max[:lon] = c[0] if c[0] > max[:lon]
19     max[:lat] = c[1] if c[1] > max[:lat]
20     max
21   end
22   min = coords.inject({lat:MAX_LAT, lon:MAX_LON}) do |min, c|
23     min[:lon] = c[0] if c[0] < min[:lon]
24     min[:lat] = c[1] if c[1] < min[:lat]
25     min
26   end
27   # add a little padding to the max and min
28   max.each {|k, v| max[k] += 1 }
29   min.each {|k, v| min[k] -= 1 }
30  
31   {min: min, max: max}
32 end
33  
34  
35 # We need to create a conceptual grid in which to do our estimation
36 # against. We're actually going to represent our grid-blocks by their
37 # centerpoint. Ex:
38 # 
39 #  _______
40 # |       |
41 # |   +   |  -- Box and center-point
42 # |_______|
43 # 
44 # We're representing our blocks as points because that's how we're
45 # going store and index our fence in Mongo when it's all said and
46 # done.
47 # 
48 # Note: In real-life, we might want to adjust the size of the grid-block
49 #       based on how large the geofence is, how granular your estimation
50 #       will be, etc. For this example, we're going to use a fixed size
51 #       grid block of  0.5 x 0.5
52 def generate_grid(bounds)
53   lon_range = bounds[:min][:lon]...bounds[:max][:lon]
54   lat_range = bounds[:min][:lat]...bounds[:max][:lat]
55  
56   grid = []
57   lon_range.each do |lon|
58     lat_range.each do |lat|
59       grid << [lon + 0.25, lat + 0.25]
60       grid << [lon + 0.25, lat + 0.75]
61       grid << [lon + 0.75, lat + 0.25]
62       grid << [lon + 0.75, lat + 0.75]
63     end
64   end
65  
66   grid
67 end
68  
69  
70  
71 # And they would be called like so:
72 bounds = get_bounding_box(coords)
73 grid = generate_grid(bounds)

Getting our Horizontal Sections

 1 # The horizontal sections generated are the spaces in-between each
 2 # pair of contiguous horizontal lines (derived from the latitude
 3 # value).
 4 #
 5 # Horizontal sections in format of:
 6 # [
 7 #   [<latN>, <lat1>],
 8 #   [<lat1>, <lat2>],
 9 #   ..., 
10 #   [<latN-1>, <latN>]
11 # ]
12 def get_horizontals(coords)
13   #get all individual horizontals
14   h1 = coords.inject([]) do |arr, (lon, lat)|
15     arr << lat unless arr.include? lat
16     arr
17   end
18  
19   #wrap those individuals up into cyclic pairs
20   h1.sort!
21   h2 = h1.dup
22   h1.pop
23   h2.shift
24   h1.zip(h2)
25 end

Once we have our horizontal sections, we can then filter our grid-items to only process those that are included in the sub-section. This would look something like:

1 horizontals = get_horizontals(coords)
2  
3 horizontals.each do |horizontal|
4   sub_grid = grid.select do |g|
5     g.last.between?(horizontal.first, horizontal.last)
6   end
7  
8   # ... some more processing...
9 end

Intersecting Lines

Alright! Now we just need to get the intersecting lines though the sub-grid and we’ll be one step away from adding grid-blocks into our estimated polygon array. (If you don’t know what I’m talking about, please review the conceptual aproach, and visuals, above.)

 1 # Given a horizonal (two lat points) and the set of lines that constitute
 2 # our polygon, determine what lines intersect the space created by the
 3 # horizontal (or horizontal sub-section if you prefer to think of it that
 4 # way)
 5 # 
 6 # 
 7 # ---*------------------------------------------------
 8 #     \
 9 #      \  - intersecting line           [horizontal section]
10 #       \
11 # -------*--------------------------------------------
12 #        |
13 #        |
14 #        |   
15 #        ... 
16 # 
17 # 
18 # h  = horizontal
19 # ls = lines
20 def intersecting_lines(h, ls) 
21   ls.select do |l| 
22     l.first.last <= h.first && l.last.last >= h.last
23   end 
24 end
25  
26  
27  
28 # The "lines" is the set of all lines for the polygon.
29 lines = coords.zip(coords.dup.rotate(-1))
30 lines.map! {|l| l.sort! {|a,b| a.last <=> b.last } }
31  
32 # Assuming that we already have our horizontals
33 horizontals.each do |horizontal|
34   intersects = intersecting_lines(horizontal, lines)
35   # ... more processing ...
36 end

Is a Point to the Left or Right?

Now that we can get out intersecting lines, we need to determine, for each point within the sub-grid, if that point is to the left of the intersecting line or to the right of the line. If it is to the left of the line, then two things can happen. If that point is already included in the estimated-polygon array, then it will be removed and if it was not in the array, then it will be added. And finally, the code:

 1 # Get the determinant of a line and a point. This is conceptually
 2 # represented by the following:
 3 # 
 4 # point = (a,b)
 5 # line  = [(x1, y1), (x2, y2)], such that y2 > y1
 6 # 
 7 # matrix:
 8 # | (x2 - x1)    (a-x1) |
 9 # | (y2 - y1)    (b-y1) |
10 # 
11 # determinent: 
12 #   (x2 - x1)*(b-y1)  -  (y2-y1)*(a-x1)
13 # 
14 # 
15 # Assertions:
16 #   determinent > 0  <->  point lies to left of line
17 #   determinent = 0  <->  point lies on the line
18 #   determinent < 0  <->  pont lies to right of line
19 #
20 # Line:  [[x1,y1],[x2,y2]]
21 # Point: [a,b]
22 def self.det(line, point)
23   x1 = line.first.first
24   y1 = line.first.last
25  
26   x2 = line.last.first
27   y2 = line.last.last
28  
29   a = point.first
30   b = point.last
31  
32   (x2 - x1)*(b-y1)  -  (y2-y1)*(a-x1)
33 end
34  
35  
36  
37 # Process each grid-item for each intersecting line
38 estimated_polygon = []
39 intersecting_lines.each do |line|
40   sub_grid.each do |grid_item|
41     if det(line, grid_item) > 0
42       if estimated_polygon.include?(grid_item)
43         estimated_polygon.delete(grid_item)
44       else
45         estimated_polygon << grid_item
46       end
47     end
48   end
49 end

Estimation Complete!

While it may not seem like you are done, trust me when I say you have completed all of the necessary steps to estimate a geofence. The only thing missing is to put all of the steps together (stay tuned). Now that we have our estimation, we simply need to store it in Mongo.

Mongo-Land

Okay, now that we have our estimated polygon/fence, it’s time to store those points in Mongo-land. First, we need to understand what our resulting estimation looks like:

1 [
2   [:lon, :lat],
3   [:lon, :lat],
4   ...
5 ]

The :lon and :lat would obviously be replaced with real values. We’re going to tranform this array of points to store in Mongo in the following format:

1 {
2   _id: ObjectId(),
3   coordinates: [
4     { lon: x, lat: y },
5     { lon: x, lat: y },
6     ...
7   ]
8 }

We have to use this particular format because it is required for us to apply our geo-spatial index (which I’ll show in a moment). If you want more info on Mongo’s geo-spatial indexes, check out their docs.

To store our estimated polygon/fence into mongo, we’re going to use the following code:

 1 # Fence Document in Mongo looks like:
 2 # {
 3 #   _id: ObjectId(),#   coordinates: [
 4 #     { lon: x, lat: y },
 5 #     ...
 6 #   ]
 7 # }
 8 def store_fence(fence)
 9   # TODO test mongo driver
10   # convert fence from array to format above
11   mongo_fence = []
12   fence.each do |coord|
13     mongo_fence << {
14       lon: coord[0],
15       lat: coord[1]
16     }
17   end
18   # store fence in Mongo
19   @coll.insert( { coordinates: mongo_fence } )
20   # ensure the index is applied
21   @coll.ensure_index([[:coordinates, Mongo::GEO2D]])
22 end

Querying Mongo

Now that we have everything stored in Mongo, it’s time to utilize the DB’s geo-spatial indexing features to bring out geofences to life! And it’s so simple; the code is only:

 1 # Coord is of format:
 2 # {
 3 #   lon: x,
 4 #   lat: y
 5 # }
 6 def within_fence?(coord)
 7   # search for fence in Mongo given coordinate
 8   radius = 0.26    # same as 0.5 ** 2 + 0.01
 9   @coll.find({
10     coordinates: {
11       :$near         => [coord[:lon], coord[:lat]],
12       :$maxDistance  => radius
13     }
14   }).count > 1
15 end

Of course, I’m only returning if the count is greater than zero. You could do whatever you please with the cursor. I think the cursor is nil if nothing is found in Mongo, so you could just return the result of the find operation.

Suprise!

It’s time to find out what’s at the end of the rainbow. I’ve been promising something this whole time. Well, you’re just going to have to go to the third post in the series to find out! ;-)