Let's say I have a list of points (in my case, point objects in a Python implementation). I then have a line segment connecting two of these points.
I want to know if there's a way to efficiently find the point from the list that is closest to the line segment. I realize I could step through all of the points and check distances individually, then select the smallest distance, but I'm eventually hoping to scale the program up to deal with perhaps millions of points. So, you know, maybe something more efficient than that?
If it helps, in terms of CCW all the points being questioned should either be to the "left"/"below" or the "right"/"above" of the line segment; I don't think my implementation will involve checking points to both sides of the segment.
The points will be point objects with (x,y) coordinates and some other junk not directly relevant to this question. The line segments are currently implemented as objects containing references to two point objects (its vertices) and its length.
As I mentioned this is part of a Python implementation. I'm trying to design a way to find a concave hull to a set of points (given some predefined parameters of how to decide whether a point not on the convex hull is on the concave hull or not). I want to find the convex hull first, then for each line segment on the convex hull find the closest point to it, make a triangle with that point, then decide if that triangle bears "deleting such that the internal point is now on the hull.
I considered putting this in Mathematics, but I don't need a distance equation - I need help with an efficient algorithm for finding points closest to a line segment. Note also that I am not looking for the closest point on a line to an input point; I'm looking for the closest point from a set to an input line segment.
Thank you all!