SpatialMap

:warning: This is still a bit of a work in progress.

Storage mechanism for geospatial features that is optimized for fast intersections checks with other geometries. Computational cost for geometries are roughly constant in sparse maps, but this comes at the cost of very expensive addition and mutation of features in the map.

On creation, a SpatialMap creates a hash function for locations that effectively divides the world in to an orthogonal grid of some standard size. Points that occupy the same grid cells will return the same hash result. When a feature is added to the map, its envelope is determined and the hashes for all points within that envelope are computed. A map is maintained from hash result to list of features.

When a query is performed, the hash result of the query is calculated which allows for very fast lookup. Finally, an intersection check is performed against original geometry of each feature. The set of features returned are those that definitely intersect the query geometry.

Performance Consideration

In general, querying for features that intersect a point is a roughly linear operation whereas adding or modifying features on a SpatialMap is vastly magnitude more expensive.

Tuning of the performance is done via the size of grid into which the world is divided:

• When the grid cells are smaller, there are generally fewer features within that cell and the intersection check becomes faster. Larger grid cells contain more features and therefore have more work to be done during the final step above (they have more false-positive results in the initial hash lookup).

• At the same time, features must be added to all cells that they hash to, which means the work performed when adding features increases as grid size decreases.

With this in mind, the most appropriate use case for this method of geospatial storage is when all the features are known at start-up and are not expected to change. A large amount of time can be dedicated to populating the map at startup while lookups will be extremely fast during runtime.

Storage Type

This library supports two types of storage for the underlying spatial hash map: :local and :ets.

• Local - The underlying map is stored on the SpatialMap. This is suitable when a single process will be responsible for both loading and answering queries. There might be methods where a SpatialMap can be created and then copied to multiple processes, but there may be additional memory overhead.

• ETS - The underlying map and feature information is stored in an ETS table. This is suitable for access from multiple processes and potentially allows for more scalability, especially when changes to the map might be necessary.

Installation

The package can be installed by adding spatial_map to your list of dependencies in mix.exs:

def deps do
  [
    {:spatial_map, "~> 0.1.0"}
  ]
end

Docs can be found at: https://hexdocs.pm/spatial_map.

Usage

map = SpatialMap.new()
map = SpatialMap.new(grid: [{0, 100, 0.1}, {0, 100, 0.1}], storage_type: :ets)

{map, ref} = SpatialMap.put_feature(map, %Geo.Polygon{...}, %{foo: bar})
intersections = SpatialMap.query(map, %Geo.LineString{...})