1.6.8 Intersection Detection
INPUT OUTPUT
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.
Recommended Books
Related Links
UNC's Collision Detection/Proximity Query Packages
Related Problems
This page last modified on 2008-07-10
.
www.algorist.com
Computational Geometry : Algorithms and Applications
Computational Geometry in C
Computational Geometry: an introduction through randomized algorithms
Algorithms and Data Structures with applications to
graphics and geometry
Algorithms from P to NP, Vol. I: Design and Efficiency
Introduction to Algorithms
Introduction to Algorithms
Computational Geometry
