Geofencing (part 2) Blog Post

det.rb

# Get the determinant of a line and a point. This is conceptually
# represented by the following:
# 
# point = (a,b)
# line  = [(x1, y1), (x2, y2)], such that y2 > y1
# 
# matrix:
# | (x2 - x1)    (a-x1) |
# | (y2 - y1)    (b-y1) |
# 
# determinent: 
#   (x2 - x1)*(b-y1)  -  (y2-y1)*(a-x1)
# 
# 
# Assertions:
#   determinent > 0  <->  point lies to left of line
#   determinent = 0  <->  point lies on the line
#   determinent < 0  <->  pont lies to right of line
#
# Line:  [[x1,y1],[x2,y2]]
# Point: [a,b]
def self.det(line, point)
  x1 = line.first.first
  y1 = line.first.last

  x2 = line.last.first
  y2 = line.last.last

  a = point.first
  b = point.last

  (x2 - x1)*(b-y1)  -  (y2-y1)*(a-x1)
end



# Process each grid-item for each intersecting line
estimated_polygon = []
intersecting_lines.each do |line|
  sub_grid.each do |grid_item|
    if det(line, grid_item) > 0
      if estimated_polygon.include?(grid_item)
        estimated_polygon.delete(grid_item)
      else
        estimated_polygon << grid_item
      end
    end
  end
end

estimated-fence-format.rb

[
  [:lon, :lat],
  [:lon, :lat],
  ...
]

get-horizontals.rb

# The horizontal sections generated are the spaces in-between each
# pair of contiguous horizontal lines (derived from the latitude
# value).
#
# Horizontal sections in format of:
# [
#   [<latN>, <lat1>],
#   [<lat1>, <lat2>],
#   ..., 
#   [<latN-1>, <latN>]
# ]
def get_horizontals(coords)
  #get all individual horizontals
  h1 = coords.inject([]) do |arr, (lon, lat)|
    arr << lat unless arr.include? lat
    arr
  end

  #wrap those individuals up into cyclic pairs
  h1.sort!
  h2 = h1.dup
  h1.pop
  h2.shift
  h1.zip(h2)
end

get-intersecting-lines.rb

# Given a horizonal (two lat points) and the set of lines that constitute
# our polygon, determine what lines intersect the space created by the
# horizontal (or horizontal sub-section if you prefer to think of it that
# way)
# 
# 
# ---*------------------------------------------------
#     \
#      \  - intersecting line           [horizontal section]
#       \
# -------*--------------------------------------------
#        |
#        |
#        |   
#        ... 
# 
# 
# h  = horizontal
# ls = lines
def intersecting_lines(h, ls) 
  ls.select do |l| 
    l.first.last <= h.first && l.last.last >= h.last
  end 
end



# The "lines" is the set of all lines for the polygon.
lines = coords.zip(coords.dup.rotate(-1))
lines.map! {|l| l.sort! {|a,b| a.last <=> b.last } }

# Assuming that we already have our horizontals
horizontals.each do |horizontal|
  intersects = intersecting_lines(horizontal, lines)
  # ... more processing ...
end

get-sub-grids.rb

horizontals = get_horizontals(coords)

horizontals.each do |horizontal|
  sub_grid = grid.select do |g|
    g.last.between?(horizontal.first, horizontal.last)
  end

  # ... some more processing...
end

grid-generation.rb

# Assuming that the coordinates for the polygon adhere to the
# format of:
# [
#   [:lon, :lat],
#   [:lon, :lat],
#   ...
# ]
#
# We can use the following methods:



# Method to get the min and max values for the polygon (plus
# some padding) that the grid can be generated within
def get_bounding_box(coords)
  # get max and min coords
  max = coords.inject({lat:0, lon:0}) do |max, c|
    max[:lon] = c[0] if c[0] > max[:lon]
    max[:lat] = c[1] if c[1] > max[:lat]
    max
  end
  min = coords.inject({lat:MAX_LAT, lon:MAX_LON}) do |min, c|
    min[:lon] = c[0] if c[0] < min[:lon]
    min[:lat] = c[1] if c[1] < min[:lat]
    min
  end
  # add a little padding to the max and min
  max.each {|k, v| max[k] += 1 }
  min.each {|k, v| min[k] -= 1 }

  {min: min, max: max}
end


# We need to create a conceptual grid in which to do our estimation
# against. We're actually going to represent our grid-blocks by their
# centerpoint. Ex:
# 
#  _______
# |       |
# |   +   |  -- Box and center-point
# |_______|
# 
# We're representing our blocks as points because that's how we're
# going store and index our fence in Mongo when it's all said and
# done.
# 
# Note: In real-life, we might want to adjust the size of the grid-block
#       based on how large the geofence is, how granular your estimation
#       will be, etc. For this example, we're going to use a fixed size
#       grid block of  0.5 x 0.5
def generate_grid(bounds)
  lon_range = bounds[:min][:lon]...bounds[:max][:lon]
  lat_range = bounds[:min][:lat]...bounds[:max][:lat]

  grid = []
  lon_range.each do |lon|
    lat_range.each do |lat|
      grid << [lon + 0.25, lat + 0.25]
      grid << [lon + 0.25, lat + 0.75]
      grid << [lon + 0.75, lat + 0.25]
      grid << [lon + 0.75, lat + 0.75]
    end
  end

  grid
end



# And they would be called like so:
bounds = get_bounding_box(coords)
grid = generate_grid(bounds)

mongo-document.js

{
  _id: ObjectId(),
  coordinates: [
    { lon: x, lat: y },
    { lon: x, lat: y },
    ...
  ]
}

query-mongo.rb

# Coord is of format:
# {
#   lon: x,
#   lat: y
# }
def within_fence?(coord)
  # search for fence in Mongo given coordinate
  radius = 0.26    # same as 0.5 ** 2 + 0.01
  @coll.find({
    coordinates: {
      :$near         => [coord[:lon], coord[:lat]],
      :$maxDistance  => radius
    }
  }).count > 1
end

store-and-index.rb

# Fence Document in Mongo looks like:
# {
#   _id: ObjectId(),#   coordinates: [
#     { lon: x, lat: y },
#     ...
#   ]
# }
def store_fence(fence)
  # TODO test mongo driver
  # convert fence from array to format above
  mongo_fence = []
  fence.each do |coord|
    mongo_fence << {
      lon: coord[0],
      lat: coord[1]
    }
  end
  # store fence in Mongo
  @coll.insert( { coordinates: mongo_fence } )
  # ensure the index is applied
  @coll.ensure_index([[:coordinates, Mongo::GEO2D]])
end