Lines Through Segments
|Four lines (drawn in green) that intersect four line segments
(drawn in blue with a halftone pattern).
Given a set S of n line segments in three-dimensional space, finding all the lines that simultaneously intersect quadruples of segments in S is a fundamental problem that arises in a variety of domains including computer graphics, computer vision, robotics and automation, to mention a few. We refer to this problem as the lines-through-segments problem, or LTS for short. We present an efficient output-sensitive algorithm and its exact implementation to solve the LTS problem. Since we do not assume general position, we compute all lines that intersect at least four segments in S. The algorithm properly handles all degenerate cases. For example, a line segment may degenerate to a point, several segments may be coplanar, parallel, concurrent, collinear, or they can even overlap. We provide a detailed analysis of all the (degenerate) cases that can arise. To the best of our knowledge this is the first algorithm (and implementation) for the LTS problem that is (i) output sensitive and (ii) handles all degenerate cases. The algorithm runs in O((n3 + I)log n) time, and requires O(n + I) working space, where I is the output size; I is bounded by O(n4). We use CGAL arrangements and in particular its support for arrangements of rectangular hyperbolas with vertical and horizontal asymptotes in the plane and for arrangements of geodesic arcs on a sphere to efficiently compute the intersecting lines in an exact manner. The efficiency of our implementation stems in part from careful crafting of the algebraic tools needed in the computation. We also report on the performance of our algorithm and its implementation compared to others.
- Efi Fogel, Michael Hemmer, Dan Halperin, and Asaf Porat
Lines Through Segments in Three-Dimensional Space
Manuscript extended abstract [pdf] [bibtex]
Efi Fogel, Michael Hemmer, Dan Halperin, and Asaf Porat
Lines Through Segments in 3D Space
In Abstracts of 28th European Workshop on Computational Geometry (EuroCG), pages x-y, 2012 [pdf] [bibtex]
In Proceedings of the 20th Annual European Symposium on Algorithms (ESA), pages 455-466, Ljubljana, Slovenia, 2012 [link] [bibtex]
- Asaf Porat
Lines Tangent to Four Polytopes in 3
M.Sc. Thesis, 2012 [pdf] [bibtex]
- The source code of the LTS program as well as the input examples for the experiments can be obtained from here.