Many geometric applications require boolean operations on objects that can be represented as planar maps. CGAL provides a package for handling planar maps. The function described in the following computes the overlay of two such planar maps and associates to each of the elements of the resulting map a color, so that boolean operations can be performed by simply extracting the elements with specific colors.
The definition of a planar map used in CGAL is extremely general. Thus, a planar map is just a subdivision of the plane induced by a a collection of curves. This means that the curve is the basic component of a planar map - not the vertices or faces. In this definition, a face is a connected component of the plane that does not contain any vertex or edge; each face is considered an open set, i.e., it does not contain its boundary. The boundary of a face is comprised of one or several disjoint cicles of edges; one of these cycles is external. A hole in a face is defined by an inner cycle of edges. Each planar map has an unbounded face.
The overlay of two planar maps is defined as in [FH95]: it consists of all non-empty sets , with a component of the first planar map and a component of the second. Basically, in order to compute the overlay, one has to compute the set where is an edge of any map, and is a face of the other map. Going further, this set is practically determined by edge intersections. Once the edges of the overlay are computed, they are inserted in the new planar map.
Another approach for computing the overlay of two planar maps is described in [FH95]. This approach makes use of a very special structure - the quad view data structure - and requires a preprocessing step to build trapezoidations out of each map, and a postprocessing step to extract the planar map from a trapezoidation. Although very fast, their algorithm demands that the planar maps are in general positions: they are not allowed to have vertical edges, or common vertices, and their edges cannot overlap. This is why we compute the overlay with a slower, but robust algorithm. It will be easily updated once new algorithms are developped in CGAL (like, for instance, a general algorithm for intersecting line segments in the plane).
The function described below is a template function. It is parameterized by the traits class of the initial planar maps (denoted by Traits). For details about the requirements of such a traits class we refer to the descrition of CGAL_Planar_map_2. We also provide a default version of the DCEL (doubly-connected edge list) class for boolean operations, which we describe in detail.
A planar map can be stored in the CGAL_Planar_map_2 object. Its elements can be represented using exact arithmetic or floating point arithmetic. For each representation, the CGAL package of planar map provides a traits class.
In order to construct a map suitable for boolean operations, a strategy would be to associate to each element a color. When two planar maps having different colors are overlaid, the elements of the resulting map will eventually have colors that come from both maps.
We extended the classes for basic elements of planar maps (vertex, halfedge, face) to contain members data that store color informations.
In the current implementation of the overlay algorithm, we work with initially uncolored maps and colored overlay. Thus, we implicitly associate RED to all the elements of the first map except the unbounded face, and BLACK to all the elements of the second map except the unbounded face. Only the unbounded face is NO_COLOR-ed: we do not consider the case when the holes must also be NO_COLOR-ed, because the notion of a hole in the current planar map is very general, and it did not coincide with the notion of a hole in planar maps taken from geographic systems, for example.
Our implementation collects the edges of the overlay by intersecting each edge of the first planar map with each edge of the second. The resulting edges have associated a structure containing relevant information about their own colors and the colors of the adjacent faces. This additional information is necessary in order to compute the color of each face. After the overlay planar map is built from the edges, its faces are successively colored using the information stored in the edges.
The planar map for boolean operations is just a regular planar map, parameterized with the DCEL for boolen operations and with a traits class. The Dcel for boolean operations elements stores some information needed for the computation of the overlay.
The requirements from a Dcel class of a planar map for boolean operations are identical to those required from a Dcel class of a normal planar map. In addition, the Vertex, Halfedge and Face classes have associated the color information as described in the following:
The types Info_vertex and Info_face are defined as CGAL_Pm_ovl_color, which is an enumeration:
| |||
The type Info_edge is defined as CGAL_Pm_ovl_three_colors, which is a structure:
| |||
The new DCEL class is:
CGAL_Pm_bops_default_dcelTraits_class
#include <CGAL/Pm_overlay_for_bops.h>
If the initial planar maps were defined like:
|
| ||
|
|
||
|
| ||
|
|
||
the overlay must be defined of type:
|
| ||
|
|
||
|
| ||||||
| ||||||
| computes the overlay of pm1 and pm2 in pm_out; returns true if pm_out is a valid planar map. | ||||||
#include <CGAL/Homogeneous.h>
#include <CGAL/Pm_segment_exact_traits.h>
#include <iostream.h>
#include <CGAL/Pm_overlay_for_bops.h>
typedef double Basetype;
typedef CGAL_Homogeneous<Basetype> Rep_class;
typedef CGAL_Pm_segment_exact_traits<Rep_class> Pmtraits;
typedef Pmtraits::Point Point;
typedef Pmtraits::X_curve Curve;
typedef CGAL_Pm_default_dcel<Pmtraits> Pmdcel;
typedef CGAL_Planar_map_2<Pmdcel, Pmtraits> Planar_map;
typedef CGAL_Pm_bops_default_dcel<Pmtraits> Bops_dcel;
typedef CGAL_Planar_map_2<Bops_dcel, Pmtraits> Bops_planar_map;
int main()
{
Planar_map pm1;
Planar_map pm2;
Bops_planar_map pm3;
Point A[3];
A[0] = Point(0, 0, 1);
A[1] = Point(4, 0, 1);
A[2] = Point(0, 4, 1);
pm1.insert(Curve(A[0], A[1]));
pm1.insert(Curve(A[1], A[2]));
pm1.insert(Curve(A[2], A[0]));
A[0] = Point(1, 1, 1);
A[1] = Point(4, 2, 1);
A[2] = Point(2, 4, 1);
pm2.insert(Curve(A[0], A[1]));
pm2.insert(Curve(A[1], A[2]));
pm2.insert(Curve(A[2], A[0]));
CGAL_Pm_overlay_for_bops<Pmtraits>(pm1, pm2, pm3);
if (pm3.is_valid()){
Bops_planar_map::Halfedge_iterator hi;
Bops_planar_map::Vertex_iterator vi;
Bops_planar_map::Face_iterator fi;
cout << "Successfully computed the overlay:\n\n";
cout << "Vertices" << endl;
for (vi=pm3.vertices_begin(); vi!=pm3.vertices_end(); ++vi){
cout << "(" << (*vi).point() << ")" ;
switch((int)(*vi).info()){
case 1: cout << " - Red" << endl;
break;
case 2: cout << " - Black" << endl;
break;
case 3: cout << " - Red and Black" << endl;
}
}
cout << "------------------" << endl;
cout << "Edges " << endl;
for (hi=pm3.halfedges_begin(); hi!=pm3.halfedges_end(); ++hi){
if ((*hi).source()->point().x()< (*hi).target()->point().x() ||
(*hi).source()->point().x()==(*hi).target()->point().x() &&
(*hi).source()->point().y()< (*hi).target()->point().y()){
cout << "(" << (*hi).source()->point() << ") - (" << (*hi).target()->point() << ")";
switch((int)(*hi).info().edge_color){
case 1: cout << " - Red" << endl;
break;
case 2: cout << " - Black" << endl;
break;
case 3: cout << " - Red and Black" << endl;
}
}
}
cout << "------------------" << endl;
cout << "Faces " << endl;
Bops_planar_map::Halfedge_handle he, he_next;
for (fi=pm3.faces_begin(); fi!=pm3.faces_end(); ++fi){
if (!(*fi).is_unbounded()){
he = (*fi).halfedge_on_outer_ccb();
he_next = he;
do{
cout << "(" << (*he_next).source()->point() << ") -";
he_next = (*he_next).next_halfedge();
} while (he!=he_next);
switch((int)(*fi).info()){
case 0: cout << " No color" << endl;
break;
case 1: cout << " Red" << endl;
break;
case 2: cout << " Black" << endl;
break;
case 3: cout << " Red and Black" << endl;
}
}
else
cout << "Unbounded face - No color" << endl;
}
}
else {
Bops_planar_map::Halfedge_handle he, he_next;
for (fi=pm3.faces_begin(); fi!=pm3.faces_end(); ++fi){
if (!(*fi).is_unbounded()){
he = (*fi).halfedge_on_outer_ccb();
he_next = he;
do{
cout << "(" << (*he_next).source()->point() << ") -";
he_next = (*he_next).next_halfedge();
} while (he!=he_next);
switch((int)(*fi).info()){
case 0: cout << " No color" << endl;
break;
case 1: cout << " Red" << endl;
break;
case 2: cout << " Black" << endl;
break;
case 3: cout << " Red and Black" << endl;
}
}
else
cout << "Unbounded face - No color" << endl;
}
}
else {
cout << "The overlay is not a valid planar map!\n";
return -1;
}
return 0;
}