3
$\begingroup$

I have a set of line segments (say 1000 of them) and a query point. I want to find the segment which is the closest in the Euclidean sense (if the point does not project on the segment I accept two options: 1) just ignore the segment - infinite distance - or 2) consider the distance to the closest endpoint). Preprocessing of the segment set is allowed.

In the case of nearest points, a 2D-tree is a good fit. Is there a good generalization to line segments ? Or another classical data structure ? (Voronoï and point-location is complex to implement, I'd prefer something more tractable, even if not perfectly efficient.)

Alternatively, I am interested by a solution of the converse problem: finding the closest point to a given query line segment.

Improve this question
$\endgroup$
1

3 Answers 3

Reset to default
0
$\begingroup$

One approach is to compute the Voronoi diagram of these line segments. Here are two papers that consider this problem:

A robust and efficient implementation for the segment Voronoi diagram. Menelaos I. Karavelas. International symposium on Voronoi diagrams in science and engineering, 2004.

VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments. Martin Held. Computational Geometry 18(2), 2001.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I mentioned that in my post. $\endgroup$
    – user16034
    May 9, 2022 at 6:41
  • 1
    $\begingroup$ @YvesDaoust, ahh. Sorry for missing that, my fault. $\endgroup$
    – D.W. ♦
    May 9, 2022 at 7:18
  • $\begingroup$ @YvesDaoust - The segment Voronoi diagram for your distance function #1 will contain only straight edges - so it'll be much simpler than for #2. However I think, diagrams which such simpler distance weren't studied yet $\endgroup$
    – HEKTO
    May 10, 2022 at 23:31
  • 2
    $\begingroup$ @YvesDaoust, I believe it is a diagram in the plane, so 2-dimensional (I'm a bit puzzled by the description as 4-dimensional). $\endgroup$
    – D.W. ♦
    May 11, 2022 at 6:47
  • 1
    $\begingroup$ Nonetheless, the resulting Voronoi diagram is a diagram in 2 dimensions. $\endgroup$
    – D.W. ♦
    May 11, 2022 at 7:04
0
$\begingroup$

I think the easiest is to put the segments into an index (quadtree, R-Tree, BVH, ...), they will typically be represented by their bounding box. Then you can use nearest neighbor search with a custom distance function that calculates the distance to the actual segment represented by the bounding box. Depending on how the index supports distance functions (do you have access to the associated data, i.e. which diagonal represents the segment?), you may need to filter the results manually.

You can also avoid a custom filter by querying for all boxes that overlap with you query point and then manually check all overlapping boxes to find the one that represents the segment closest to your point.

If your segments are very long (i.e. they are likely to overlap) you can do some preprocessing and split up long segments into shorter ones until a search point will typically overlap with only very few bounding boxes.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Yes, that's the way, thanks. But more concretely ? $\endgroup$
    – user16034
    May 9, 2022 at 6:42
  • $\begingroup$ @YvesDaoust Which part do you want to know more on? $\endgroup$
    – TilmannZ
    May 10, 2022 at 8:48
  • $\begingroup$ Which type of index, which custom distance, which bounding box, which filter, which preprocessing... $\endgroup$
    – user16034
    May 10, 2022 at 8:55
  • $\begingroup$ I think it's all in the answer already, but to summarize: Index: quadtree or R-Tree; Custom distance: a distance function that calculates the distance of your point to the segment/box; bounding box: the axis aligned bounding box around the segment/line; preprocessing: split the longer lines into shorter lines. $\endgroup$
    – TilmannZ
    May 10, 2022 at 11:55
  • $\begingroup$ Sorry but I know that all this is "feasible". What I am after is a classical solution (if one is known), or a true ad-hoc experience on this problem. $\endgroup$
    – user16034
    May 10, 2022 at 12:21
-1
$\begingroup$

Consider Morton Encoding (https://en.wikipedia.org/wiki/Z-order_curve). It's pretty easy to implement, simpler than most two-dimensional indexes, and works pretty well.

What does "closest segment" mean? Are you just looking for the single segment endpoint closest to your target point? Or do both ends of the segment matter?

Improve this answer
$\endgroup$

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.