GraphHopper.com | Forum | GitHub | Maps | Blog

Is there document describe the scenario LocationIndexTree especially InMemConstructionIndex?


#1

Try to find document which describe the structure and strategy of LocationIndexTree and InMemConstructionIndex on GitHub , seem there is no that or in corner i didn’t track .


#2

The idea is a QuadTree but it can have more than 4 cells per depth/level to increase branching and decrease the maximum depth, this maximum depth is identical for all branches (IF there are roads at al in this cell). To feed not just points but lines (one edge consists of multiple lines), we use a Bresenham line and store one node of the edge into every cell determined by Bresenham.

The InMemConstructionIndex is using normal Java references to build the tree, the final storage uses integer values for the references stored in a DataAccess to make this more compact and likely also faster (a DataAccess is a big array storable on disc) but once created no more changes are possible which is ok for road networks.


#3

Thanks for quick reply , i noticed it is a QuadTree , just read carefully :slight_smile: