Nearest line-segment to a query point or conversely

Question

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.

• HEKTO: For your alternative question please see: researchgate.net/publication/…

Answer 1

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.

• user16034: I mentioned that in my post.
• D.W.: @YvesDaoust, ahh. Sorry for missing that, my fault.
• HEKTO: @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
• D.W.: @YvesDaoust, I believe it is a diagram in the plane, so 2-dimensional (I'm a bit puzzled by the description as 4-dimensional).
• D.W.: Nonetheless, the resulting Voronoi diagram is a diagram in 2 dimensions.

Answer 2

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.

• user16034: Yes, that's the way, thanks. But more concretely ?
• TilmannZ: @YvesDaoust Which part do you want to know more on?
• user16034: Which type of index, which custom distance, which bounding box, which filter, which preprocessing...
• TilmannZ: 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.
• user16034: 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.

Answer 3

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?