Class LocationIndexTree

java.lang.Object
com.graphhopper.storage.index.LocationIndexTree
All Implemented Interfaces:
LocationIndex

public class LocationIndexTree extends Object implements LocationIndex
This class implements a Quadtree to get the closest node or edge from GPS coordinates. The following properties are different to an ordinary implementation:
  1. To reduce overall size it can use 16 instead of just 4 cell if required
  2. Still all leafs are at the same depth, otherwise it is too complicated to calculate the Bresenham line for different resolutions, especially if a leaf node could be split into a tree-node and resolution changes.
  3. To further reduce size this Quadtree avoids storing the bounding box of every cell and calculates this per request instead.
  4. To simplify this querying and avoid a slow down for the most frequent queries ala "lat,lon" it encodes the point into a spatial key and can the use the resulting raw bits as cell index to recurse into the subtrees. E.g. if there are 3 layers with 16, 4 and 4 cells each, then the spatial key has three parts: 4 bits for the cellIndex into the 16 cells, 2 bits for the next layer and 2 bits for the last layer.
  5. An array structure (DataAccess) is internally used and stores the offset to the next cell. E.g. in case of 4 cells, the offset is 0,1,2 or 3. Except when the leaf-depth is reached, then the value is the number of node IDs stored in the cell or, if negative, just a single node ID.
Author:
Peter Karich
  • Constructor Details

    • LocationIndexTree

      public LocationIndexTree(Graph g, Directory dir)
      Parameters:
      g - the graph for which this index should do the lookup based on latitude,longitude.
  • Method Details

    • getMinResolutionInMeter

      public int getMinResolutionInMeter()
    • setMinResolutionInMeter

      public LocationIndexTree setMinResolutionInMeter(int minResolutionInMeter)
      Minimum width in meter of one tile. Decrease this if you need faster queries, but keep in mind that then queries with different coordinates are more likely to fail.
    • setMaxRegionSearch

      public LocationIndexTree setMaxRegionSearch(int numTiles)
      Searches also neighbouring tiles until the maximum distance from the query point is reached (minResolutionInMeter*regionAround). Set to 1 to only search one tile. Good if you have strict performance requirements and want the search to terminate early, and you can tolerate that edges that may be in neighboring tiles are not found. Default is 4, which means approximately that a square of three tiles upwards, downwards, leftwards and rightwards from the tile the query tile is in is searched.
    • setResolution

      public LocationIndex setResolution(int minResolutionInMeter)
    • loadExisting

      public boolean loadExisting()
    • flush

      public void flush()
    • prepareIndex

      public LocationIndex prepareIndex()
    • prepareIndex

      public LocationIndex prepareIndex(EdgeFilter edgeFilter)
    • close

      public void close()
      Specified by:
      close in interface LocationIndex
    • isClosed

      public boolean isClosed()
    • getCapacity

      public long getCapacity()
    • findClosest

      public Snap findClosest(double queryLat, double queryLon, EdgeFilter edgeFilter)
      Description copied from interface: LocationIndex
      This method returns the closest Snap for the specified location (lat, lon) and only if the filter accepts the edge as valid candidate (e.g. filtering away car-only results for bike search)

      Specified by:
      findClosest in interface LocationIndex
      Parameters:
      edgeFilter - if a graph supports multiple vehicles we have to make sure that the entry node into the graph is accessible from a selected vehicle. E.g. if you have a FOOT-query do:
      AccessFilter.allEdges(footFlagEncoder);
      Returns:
      An object containing the closest node and edge for the specified location. The node id has at least one edge which is accepted by the specified edgeFilter. If nothing is found the method Snap.isValid will return false.
    • query

      public void query(LocationIndex.TileFilter tileFilter, LocationIndex.Visitor function)
      Specified by:
      query in interface LocationIndex
    • traverseEdge

      public void traverseEdge(double queryLat, double queryLon, EdgeIteratorState currEdge, LocationIndexTree.EdgeCheck edgeCheck)