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

More Info:

• 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

## 1 Answer

If the incoming points are indeed represented as a vector then you have to touch every single one of them, or else you wouldn't be able to tell if it is within radius distance. But, you might be able to speed up your computation if you have control over the data structure used to represent your point set.

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.

• Thanks, I understood the point-point quadtree optimization, but in case of segments the segment ends might be at very big distance generating many possible minimal distances on points projected on them, so I'm not sure I understood how I should partition the line, or should I divide it into smaller segments at quadtree separation and keep a track of the original segment index? – Spider Mar 2 '14 at 13:21
• Or if line segments will be small, I can build a bounding box and calculate the points quadtree overlap by increasing the box with needed radius? – Spider Mar 2 '14 at 13:24
• The latter (bounding boxes) was also my first intuition. – Thomas Mar 2 '14 at 13:42
• 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