# Best method for selecting points from a point set - path distance

having a big set of points and a polygonal path what is the best way to select a set of points that are at a certain distance or smaller from the path? Or do I need to iterate thru all points on each segment?

• Points are randomly distributed in 2D space as well as path coords.
• Path segments can vary from 10 to 100.
• There can be like 100 points that needs to be selected
• Incoming data is a vector of points for path, a vector of points to find the nearest one and a radius
• well, best method depends on the data and size of it, what is size (how big?) and the distribution? giving us more info can help. – concept3d Mar 2 '14 at 9:10
• You did not provided any information about the data structure but if you know nothing of the data structure, you need to iterate over all the points and check if they meet the criteria. How would you know if you did not iterate over each one? – AturSams Mar 2 '14 at 9:19
• Added more info. Arthur Wulf White, if I knew the the answer I didn't ask the question. I'm not saying there should be a magic method, but maybe there is a method with less iterations. – Spider Mar 2 '14 at 9:30

For the sake of simplicity, let's assume the task was really to determine which points are are close to a single point p, i.e., the distance to p should be at most r (the radius). Then if your set of points was not represented as a vector but as, e.g., a quadtree then you would be able to narrow down your search space with logarithmic cost. Since you say that the points are randomly distributed in the 2D plane, you would expect this to speed up your search noticably.
The same argument could be applied if your actual task is not finding points that are close to a single point p but to all points on a path. Here, instead of having to iterate over all points of the path, you might be able to save on processing time if the path points come in a similar datastructure (quadtree) that allows you to basically to collapse a bunch of points to a single quad.
• But maybe BBs are too crude. How about if you imagine two circles of radius r about the end points of the segment, and two circle tangents parallel to the segment on either side. That is the shape in which your points must lie. The circles could be approcimated by squares, but anyway it should be sufficient to check which quads intersect with the outline of that shape. A Bresenham-ish algorithm could make that efficient. – Thomas Mar 2 '14 at 13:50