2
$\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.

$\endgroup$
1

2 Answers 2

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.

$\endgroup$
7
  • $\begingroup$ I mentioned that in my post. $\endgroup$ May 9 at 6:41
  • 1
    $\begingroup$ @YvesDaoust, ahh. Sorry for missing that, my fault. $\endgroup$
    – D.W.
    May 9 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 at 23:31
  • $\begingroup$ @HEKTO: the Voronoi diagram is the union of the loci of points nearer to a given site than to others. When you replace points by line segments (case #1), the diagram is a 4 dimensional object, most probably complicated, and I have no idea how it could be built and what is the shape of the hypercells; after building the diagram, you need to perform an efficient segment-location in it. In the case #2, the diagram is known to be made of parabolic arcs. $\endgroup$ May 11 at 6:44
  • 1
    $\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 at 6:47
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.

$\endgroup$
7
  • $\begingroup$ Yes, that's the way, thanks. But more concretely ? $\endgroup$ May 9 at 6:42
  • $\begingroup$ @YvesDaoust Which part do you want to know more on? $\endgroup$
    – TilmannZ
    May 10 at 8:48
  • $\begingroup$ Which type of index, which custom distance, which bounding box, which filter, which preprocessing... $\endgroup$ May 10 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 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$ May 10 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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