Geomodel aims to provide a generalized solution for performing basic indexing and querying of geospatial data in non-relation environments. At the core, this solution utilizes geohash-like objects called geocells.
A geocell is a hexadecimal string that defines a two dimensional rectangular region inside the [-90,90] x [-180,180] latitude/longitude space. A geocell's 'resolution' is its length. For most practical purposes, at high resolutions, geocells can be treated as single points.
Much like geohashes (see http://en.wikipedia.org/wiki/Geohash), geocells are hierarchical, in that any prefix of a geocell is considered its ancestor, with geocell[:-1] being geocell's immediate parent cell.
To calculate the rectangle of a given geocell string, first divide the [-90,90] x [-180,180] latitude/longitude space evenly into a 4x4 grid like so:
+---+---+---+---+ (90, 180) | a | b | e | f | +---+---+---+---+ | 8 | 9 | c | d | +---+---+---+---+ | 2 | 3 | 6 | 7 | +---+---+---+---+ | 0 | 1 | 4 | 5 | (-90,-180) +---+---+---+---+
NOTE: The point (0, 0) is at the intersection of grid cells 3, 6, 9 and c. And, for example, cell 7 should be the sub-rectangle from (-45, 90) to (0, 180).
Calculate the sub-rectangle for the first character of the geocell string and re-divide this sub-rectangle into another 4x4 grid. For example, if the geocell string is '78a', we will re-divide the sub-rectangle like so:
. . . . . . +----+----+----+----+ (0, 180) | 7a | 7b | 7e | 7f | +----+----+----+----+ | 78 | 79 | 7c | 7d | +----+----+----+----+ | 72 | 73 | 76 | 77 | +----+----+----+----+ | 70 | 71 | 74 | 75 | . . (-45,90) +----+----+----+----+ . . . .
Continue to re-divide into sub-rectangles and 4x4 grids until the entire geocell string has been exhausted. The final sub-rectangle is the rectangular region for the geocell.
A geocell can be associated with a single geographic point and subsequently indexed and filtered by either conformance to a bounding box or by proximity (nearest-n) to a search center point.
The model part was mostly implemented in the other libraries to bind directly to Google App Engine. The idea here is to make it backend/db independent and use callbacks to integrate with the backend.
Add this line to your application's Gemfile:
And then execute:
Or install it yourself as:
$ gem install geomodel
Currently, only single-point entities and two types of basic geospatial queries on those entities are supported.
Representing your Locations
You'll need a class to hold a geolocation. It assumes that an "entity" has a unique "id" (specific field can be configure), a latitude/longitude combination stored in a "location" field (a Geomodel::Types::Point) and a collection of "geocells".
class Entity attr_accessor :id, :location, :geocells def to_s self.id end end
An instance of one of these entities can be instantiated as shown next. Let's say we wanted to create an entity for the Frank Lloyd Wright Iconic Desert Spire in Scottsdale, AZ (http://livebetterinscottsdale.com/2012/02/things-to-see-in-scottsdale-az-the-frank-lloyd-wright-spire/):
flw_spire = Entity.new flw_spire.id = 'Flatiron' flw_spire.location = Geomodel::Types::Point.new(33.633406, -111.916803) flw_spire.geocells = Geomodel::GeoCell.generate_geocells(flw_spire.location) puts flw_spire.geocells # 8 # 8d # 8da # 8daa # 8daab # 8daab6 # 8daab66 # 8daab666 # 8daab6668 # 8daab66684 # 8daab66684e # 8daab66684e4 # 8daab66684e4d
Bounding Box Queries
# compute a geocell for the location using a resolution of 14 cell = Geomodel::GeoCell.compute(flw_spire.location, 14) # create a bounding box for the cell bounding_box = Geomodel::GeoCell.compute_box(cell) # get a list of geocells for the given bounding box geocells = Geomodel.geocells_for_bounding_box(bounding_box) # use the bounding box geocells to do a key lookup in your database assuming that there is # a location_geocell 'column' and you can do an IN query like: result_set = my_db.query('SELECT * WHERE location_geocells IN (?)', query_geocells) # the results then can be filtered by whether they fall inside the bounding box using: matches = Geomodel.filter_result_set_by_bounding_box(bounding_box, result_set)
Proximity (nearest-n) Queries
Find nearby locations given a location (lat & lon) and a radius in meters:
# a list of places (instance of Entity or object that responds to :id, :location, :geocells) places = [place1, place2, place3, ...] # a function that can query your database. It takes as a parameter an array of geocells (strings) # that are used to filter the query (below is an in-memory implementation using the 'places' array # as our datasource) query_runner = lambda do |geocells| result = places.reject do |o| (o.geocells & geocells).length < 0 end result end # query for a maximum of 20 results, 15 miles (~24140 meters) from the Frank Lloyd Wright Spire # results are tuples (2 element arrays) with the matching entity and its distance from the location results = Geomodel.proximity_fetch(flw_spire.location, query_runner, 20, 24140) # extract the matching places places = results.map(&:first) # extract the distances distances = results.map(&:last)
A Rails 4 Demo application of using the GeoModel Library with Cassandra (http://cassandra.apache.org/) can be found at https://github.com/integrallis/geomodel-cassandra-demo and a live demo is deployed on Heroku at http://geomodel.herokuapp.com/
- Fork it
- Create your feature branch (
git checkout -b my-new-feature)
- Commit your changes (
git commit -am 'Add some feature')
- Push to the branch (
git push origin my-new-feature)
- Create new Pull Request