Given a set $S$ of line segments (possibly sharing endpoints) and a query point $q$, how fast can we find the closest visible endpoint from $q$? If $p$ is the closest visible endpoint to $q$, then, in this case, it means that the line segment $pq$ does not intersect with any other line segment in $S$.

I am trying to implement an efficient algorithm in CGAL. I have explored the nearest-neighbor and visibility structures from CGAL but could not conclude anything.

  • $\begingroup$ Please look for "2D Segment Voronoy Diagrams" $\endgroup$ – HEKTO Aug 21 '19 at 16:58

I only noticed after posting that my first answer does not directly address your specific question. So now my answer is in two parts.

(1) As suggested by @HEKTO, to find the closest segment, you could first compute the Voronoi diagram: CGAL 2D Segment Voronoi Diagrams. Then next you need to perform point location within the (non-rectilinear) cells of the diagram. That is also discussed, using "the segment Voronoi diagram hierarchy, a data structure suitable for fast nearest neighbor queries..."

CGAL figure.

(2) You specifically ask for the closest segment endpoint, which is not necessarily an endpoint of the closest segment:

          Point $x$ is closer to segments $1,2,3,4$ than to the closest endpoint $y$.
For this you might need to look at "visibility constrained Voronoi diagrams":

Aurenhammer, Franz, Bing Su, Y-F. Xu, and Binhai Zhu. "A note on visibility-constrained Voronoi diagrams." Discrete applied mathematics 174 (2014): 52-56. Elsevier link.

I haven't studied this paper enough to be certain it solves your problem. And perhaps there is a way to efficiently move from the closest segment to the closest segment endpoint.

| cite | improve this answer | |
  • $\begingroup$ Thank you. I was expecting something from CGAL which I can use right away. But it appears that there is none. $\endgroup$ – aghost Aug 22 '19 at 1:10

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.