com.graphhopper.storage.index

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 SpatialKeyAlgo 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

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	LocationIndexTree.EdgeCheck

Nested classes/interfaces inherited from interface com.graphhopper.storage.index.LocationIndex

LocationIndex.Visitor

Constructor Summary

Constructors

Constructor and Description
LocationIndexTree(Graph g, Directory dir)

Method Summary

Modifier and Type	Method and Description
void	close()
Snap	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	getCapacity()
int	getMinResolutionInMeter()
boolean	isClosed()
boolean	loadExisting()
LocationIndex	prepareIndex()
LocationIndex	prepareIndex(EdgeFilter edgeFilter)
void	query(BBox queryBBox, LocationIndex.Visitor function) This method explores the LocationIndex with the specified Visitor.
LocationIndexTree	setMaxRegionSearch(int numTiles) Searches also neighbouring tiles until the maximum distance from the query point is reached (minResolutionInMeter*regionAround).
LocationIndexTree	setMinResolutionInMeter(int minResolutionInMeter) Minimum width in meter of one tile.
LocationIndex	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

Constructor Detail

LocationIndexTree

public LocationIndexTree(Graph g,
                         Directory dir)

Parameters:

g - the graph for which this index should do the lookup based on latitude,longitude.

Method Detail

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

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(BBox queryBBox,
                  LocationIndex.Visitor function)

Description copied from interface: LocationIndex

This method explores the LocationIndex with the specified Visitor. It visits only the stored edges (and only once) and limited by the queryBBox. Also (a few) more edges slightly outside of queryBBox could be returned that you can avoid via doing an explicit BBox check of the coordinates.

Specified by:

query in interface LocationIndex

traverseEdge

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