2
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ The distance of a point to a line given by two points on that line is a simple formula from linear algebra. So an exact O(n) algorithm is to compute that formula for each line in turn and take the minimum outcome. If you need to repeat this for many different points on the same set of lines, you can be faster than O(n) by preprocessing. That is the problem HEKTO is addressing. $\endgroup$
    – reinierpost
    May 12, 2020 at 19:19

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Binary space partitioning. $\endgroup$
    – Pseudonym ♦
    May 12, 2020 at 5:27
  • $\begingroup$ Thank you for responding. This class of algorithms is new to me. I read an overview at en.wikipedia.org/wiki/Point_location. My problem domain is a little different that a closed polygon described there. My lines tend to fall in collinear groups, meaning that clusters of line are almost collinear. Will this class of algorithm work well in my case? And could you point me to descriptions/implementations? $\endgroup$
    – mmsood
    May 12, 2020 at 5:42
  • $\begingroup$ @mmsood - I did some additions... As for collinear groups - it looks like the BSP approach will work for this case, you just hierarchically split your line set along these collinear lines. As for implementations - if your working language is C++, then please look at the CGAL library. $\endgroup$
    – HEKTO
    May 12, 2020 at 18:38
  • $\begingroup$ @HEKTO Thank you. I believe I have enough info to proceed. I accepted your answer. $\endgroup$
    – mmsood
    May 13, 2020 at 3:46
0
$\begingroup$

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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for responding. The lines are of infinite length for this problem and I have edited the question to reflect that. The algorithm you describe will work but in linear in the number of lines for any given point. I was hoping to find a log(N) algorithm, similar to KD-trees for point problems. $\endgroup$
    – mmsood
    May 11, 2020 at 21:37
  • $\begingroup$ I see, have you checked out stackoverflow.com/questions/24461631/… ? $\endgroup$
    – GS1
    May 12, 2020 at 6:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.