Package com.graphhopper.storage.index
Class LocationIndexTree
java.lang.Object
com.graphhopper.storage.index.LocationIndexTree
- All Implemented Interfaces:
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:
- To reduce overall size it can use 16 instead of just 4 cell if required
- 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.
- To further reduce size this Quadtree avoids storing the bounding box of every cell and calculates this per request instead.
- 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.
- 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
-
Nested Class Summary
Nested ClassesNested classes/interfaces inherited from interface com.graphhopper.storage.index.LocationIndex
LocationIndex.TileFilter, LocationIndex.Visitor
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoid
close()
findClosest
(double queryLat, double queryLon, EdgeFilter edgeFilter) 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.void
flush()
long
int
boolean
isClosed()
boolean
prepareIndex
(EdgeFilter edgeFilter) void
query
(LocationIndex.TileFilter tileFilter, LocationIndex.Visitor function) setMaxRegionSearch
(int numTiles) Searches also neighbouring tiles until the maximum distance from the query point is reached (minResolutionInMeter*regionAround).setMinResolutionInMeter
(int minResolutionInMeter) Minimum width in meter of one tile.setResolution
(int minResolutionInMeter) void
traverseEdge
(double queryLat, double queryLon, EdgeIteratorState currEdge, LocationIndexTree.EdgeCheck edgeCheck) Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface com.graphhopper.storage.index.LocationIndex
query
-
Constructor Details
-
LocationIndexTree
- Parameters:
g
- the graph for which this index should do the lookup based on latitude,longitude.
-
-
Method Details
-
getMinResolutionInMeter
public int getMinResolutionInMeter() -
setMinResolutionInMeter
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
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
-
loadExisting
public boolean loadExisting() -
flush
public void flush() -
prepareIndex
-
prepareIndex
-
close
public void close()- Specified by:
close
in interfaceLocationIndex
-
isClosed
public boolean isClosed() -
getCapacity
public long getCapacity() -
findClosest
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 interfaceLocationIndex
- 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
- Specified by:
query
in interfaceLocationIndex
-
traverseEdge
public void traverseEdge(double queryLat, double queryLon, EdgeIteratorState currEdge, LocationIndexTree.EdgeCheck edgeCheck)
-