Finding Nearest Node or Road

Spatial Indexes

For each node in the graph, a spatial index is created using the STRtree object (from JTS imported by GeoTools). This allows faster querying of nodes in the vicinity of the source and destination latitude and longitude.

The same code is used to find roads close to a bus stop to determine the speed of a bus.

Querying the Spatial Index

The JTS query function requires an envelope - a distance to search for. Using approximate metric equivalents of latitude and longitude, a 0.0005 degree (50m) envelope is used to query all elements within a 0.0005 degree radius. Each line is then iterated to find the closest element. However, if the number of elements found is not sufficient (in this case 0), the search envelope is increased by 0.0001 (10m) until an element can be found.