非表示:
キーワード:
-
要旨:
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).
