max planck institut
informatik
informatik
MPI-I-2000-1-005. December 2000, 16 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry
Abstract in LaTeX format:
Many geometric algorithms that are usually formulated for points and
segments generalize easily to inputs also containing rays and lines.
The sweep algorithm for segment intersection is a prototypical
example. Implementations of such algorithms do, in general, not
extend easily. For example, segment endpoints cause events in sweep
line algorithms, but lines have no endpoints. We describe a general
technique, which we call infimaximal frames, for extending
implementations to inputs also containing rays and lines. The
technique can also be used to extend implementations of planar
subdivisions to subdivisions with many unbounded faces. We have used
the technique successfully in generalizing a sweep algorithm designed
for segments to rays and lines and also in an implementation of planar
Nef polyhedra.
Our implementation is based on concepts of generic programming in C++
and the geometric data types provided by the C++ Computational
Geometry Algorithms Library (CGAL).
Acknowledgement:
References to related material:
| To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |
|---|---|
| 158 KBytes; 143 KBytes | |
| Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView | |
BibTeX