=ADD=
=reftype=
14
=number=
98-03
=url=
ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1998/98-03.ps.gz
=year=
1998
=month=
04
=author=
Freiseisen; Wolfgang
=title=
Colored DCEL for Boolean Operations in 2D
=abstract=
Finding the intersection, union, or difference of two simple polygons
are well known problems in computational geometry. In this paper,
new algorithms and their implementation solving these problems are
presented.
Assuming that line segment intersection is done already, the common main
idea is
to build up a colored doubly connected edge list (DCEL),
independently of the actual operation. Colors indicate the relationship
between polygons and elements, i.e. every element covered by a polygon
will get
its color. In order to perform
the respective boolean operation the DCEL is traversed for elements with
a certain color.
 
It will be shown that the
 DCEL can be constructed in $O(n \log(n))$ time and using this
constructed
 DCEL the boolean operations need $O(n)$ time.
 
The given implementation, which is part of the \cgal\footnote{
Computational Geometry Algorithms Library}
library, is parameterized with traits classes that define geometric
predicates, number types, and representation classes. This approach
makes it easy to adapt the algorithms to other geometric types and
predicates.
=sponsor=
ESPRIT IV LTR Project No. 21957 (CGAL) of the European Union