Search code examples
algorithmroutesgeolocation

Algorithm to find Points of Interest along a route?

Given a route between a start point and an end point, how to find efficiently Points of Interest (POIs) (given by their long / lat coordinates) along this route, at a maximum distance D_max?

A naive approach would be to move a circle of radius D_max along this route, and look for POIs inside this circle; but if circles don't overlap we may forget POIs, and if they overlap, we will find same POI several times, so it is not efficient.

What would be a better approach?

(Note: I don't know if SO is the best place for this question, or if I should post it on CS, or Software Engineering, or elsewhere?)

Solution

  • Assuming you have your POI points indexed in some space partitioning data structure as a k-d tree or a quadtree, implementing a find-points-near-polyline algorithm shouldn't be too difficult.

    1. From the polyline obtain the set of segments conforming it.
    2. Descend recursively into your space partitioning data strucure filtering at every level the set of segments by the distance to the space partition enclosing box.
    3. Once you reach a final node, use brute force to check the distance between the remaining vectors in the set at that point and the POI in the partition.