 |
 |
|
|
Input Description: A set \(S\) of lines and line segments \(l_1,...,l_n\), or a pair of polygons or polyhedra \(P_1\) and \(P_2\).
Problem: Which pairs of line segments intersect each other? What is the intersection of \(P_1\) and \(P_2\)?
Excerpt from The Algorithm Design Manual: Intersection detection is a fundamental geometric primitive that arises in many applications. Picture a virtual-reality simulation of an architectural model for a building. The illusion of reality vanishes the instant the virtual person walks through a virtual wall. To enforce such physical constraints, any such intersection between polyhedral models must be immediately detected and the operator notified or constrained.
Another application of intersection detection is design rule checking for VLSI layouts. A minor design mistake resulting in two crossing metal strips can short out the chip, but such errors can be detected before fabrication using programs to find all intersections between line segments.
Computational Geometry : Algorithms and Applications by Mark De Berg, Marc Van Kreveld, Mark Overmars, and O. Schwartskopf
Computational Geometry in C by Joseph O'Rourke
Computational Geometry: an introduction through randomized algorithms by K. Mulmuley
Algorithms and Data Structures with applications to graphics and geometry by J. Nievergelt and K. Hinrichs
Algorithms from P to NP, Vol. I: Design and Efficiency by B. Moret and H. Shapiro
Introduction to Algorithms by T. Cormen and C. Leiserson and R. Rivest and C. Stein
Computational Geometry by F. Preparata and M. Shamos
