Which algorithm can efficiently find a set of points within a certain distance of a path?

Question

Given a set of points s (a set of x,y coordinates) and a path that is made up of line segments joining a set of points l, describe an efficient algorithm that can be used to find a subset of points from s that are within the specified distance d of the path l.

A practical application of this may be to find a list of restaurants within 10 miles anywhere along a road trip path between cites.

For example, in the following diagram, the points in green would be included in the search results.

Solutions would be preferred in C#, but bonus points may be given for a SQL based approach :-)

Answer 1

I also thought about this some time ago. I think, efficient is misleading. Just testing all line segments for each point is good enough. It is very cheap to calculate the distance. If there are many points, you can also think about refining the strategy which points to choose using a level-set approach. i.e.

• go along the line, step width 2x the distance you want to check (more or less?) and create artificial points that are "near".
• itereate: pick new points around points that are "near" (don't calculate an eucledian distance, just a 1-norm and simply test the x and y coordinates) - then test their distance (you can even inherit the specific line segment from the artifical points to the found "near" points and select that one first for testing, but broaden the search, since there could be twists!)

that's maybe not complete, but should be fast and avoids checking points far away and quite ok.