Looking for an efficient algorithm quickly find the nearest line (defined by perpendicular distance) to an arbitrary point

Question

I have a large set of lines in 2D with a known start point and end point, and would like to find the nearest (defined by perpendicular distance) of those edges (or the extension of those edges past their start and end points) to an arbitrary point.

The best I have done so far is to generate a set of sample points along each line and use a KD-tree to solve the nearest neighbor problem for the points - i.e. find the nearest line sample point to the query point. But this is inaccurate and needs a large number of samples for long lines.

I did see this: Algorithm for nearest edge detection with respect to a point (in all directions)

but it relied on a sweep method and a small number of lines of finite length.

Answer 1

All your lines define a planar subdivision, where each polygonal region is bounded by a finite number of line segments or rays. So, at first you need to find a (probably infinite) region, containing a query point, and then you'll be able to select its boundary line with minimum distance from this point.

There are many ways to preprocess a planar subdivision in order to solve the Point location problem with logarithmic time complexity. Some hierarchical data structure is typically devised, which can be traversed for any query point, and it's proved, that the length of the traverse path is limited by $O(log(N))$, where $N$ is the number of regions. As @Pseudonym mentioned in comments, you can also use Binary space partitioning (BSP) to build a BSP tree - it's also a hierarchical data structure (binary tree), which will allow you to efficiently find a region, containing a query point. It looks like your problem suits well for this BSP approach.

Sorry to say, you can get regions with $O(n)$ boundary segments/rays, where $n$ is the number of lines. To overcome this difficulty you can further subdivide each region into Voronoi diagram, generalized for its boundary segments and rays. It's easy to see that the total number of such refined regions will be limited by $O(n^2)$, which still gives you logarithmic time complexity for the nearest line search. However in average case these regions with many boundary segments/rays will make up a small fraction of all regions - so in average you still will be able to quickly select the closest boundary segment/ray just by looping over the region boundary.

---

If you want to know more about general properties of the geometric structure you're working with - it makes sense to read this Wiki page.

Answer 2

I may have misunderstood your goal - do you assume the edges continue on in both directions even though they are defined by 2 specific points along them? I assume so because you say that the distance is defined by perpendicular distance. In which case how about this -
1. For each line segment, calculate the angle.
2. Draw an imaginary line that goes through your arbitrary point at an angle that is perpendicular to the line segment.
3. Find the point of intersection between the line segment and the new imaginary line, find the distance between that point and your arbitrary point. Keep the lowest distance.
If the lines are not infinitely long then when you check the distance, check min(distance to start point, distance to end point).