Algorithm to find Points of Interest along a route?

Question

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?)

Answer 1

You need to find distance from polyline in lat/lon coordinates and given point and compare it with maximum distance.

It is possible to get cross-track distance (GI at the picture) from here for every route segment:

Formula:    dxt = asin( sin(δ13) ⋅ sin(θ13−θ12) ) ⋅ R
where    δ13 is (angular) distance from start point to third point
 θ13 is (initial) bearing from start point to third point
 θ12 is (initial) bearing from start point to end point
 R is the earth’s radius
JavaScript: var dXt = Math.asin(Math.sin(d13/R)*Math.sin(θ13-θ12)) * R;

as well as along-track distance (BI at the picture):

Formula:    dat = acos( cos(δ13) / cos(δxt) ) ⋅ R
where    δ13 is (angular) distance from start point to third point
 δxt is (angular) cross-track distance
 R is the earth’s radius
JavaScript: var dAt = Math.acos(Math.cos(d13/R)/Math.cos(dXt/R)) * R;

and compare along-track distance with start-end distance (if it is negative or larger, then the closest point is end of segment - BH case at the picture, here HC is the smallest distance ot BC segment)

Bearing and distance calculations are on the same page.

If you are using some geo libraries, they should contain functions for such task.

Answer 2

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.