Boolean Operations

Introduction

A clear distinction should be made between two sorts of functions described in this chapter. Some operations perform an intersection test without computing the actual result of the intersection. Other operations perform a boolean operation (intersection, union, or difference): they explicitly compute and return the result of the boolean operation on two polygons.

Note that particular classes of polytopes are not closed under boolean operations. For instance, the union of two simple polygons is not necessarily a simple polygon, or the intersection of two triangles is not necessarily a triangle.

All functions described below are template functions. Some are parametrized only by the number type (denoted by R), others are parameterized with a traits class (denoted by Traits). Where we use polygons of type CGAL_Polygon_2 the functions are parameterized by a number type (denoted by R) and container (denoted by Container), as it is the case for CGAL_Polygon_2. For more details we refer to the description of CGAL_Polygon_2. In a boolean operations traits class some types and functions needed for the computation of boolean operations are defined. We provide a default version of the traits class for boolean operations, which we describe in detail below. So the user need not (but can if desired) provide ones own boolean operations traits class.

Note: the current version of boolean operations is robust only when a representation with exact arithmetic, for instance CGAL_Cartesian<CGAL_Rational>, is used. In nearly degenerate configurations, correct results are not guaranteed when floating point numbers are used.

Boolean Operations on Polygons

Definition

A polygon on which the boolean operations can be performed can be stored in one of the following CGAL-objects:

• CGAL_Triangle_2, a 2-dimensional triangle.
• CGAL_Iso_rectangle_2, a 2-dimensional iso-oriented rectangle.
• CGAL_Polygon_2, a 2-dimensional polygon. It must be simple, but not necessarily convex. So, non-adjacent edges do not intersect and there are no holes in the polygon. The vertices of such a polygon must be ordered in counterclockwise order.

We consider polygons as being closed and filled objects, i.e. we consider both its boundary and its interior. The edge cycle of the polygon will be referred to explicitly as the polygon boundary. For boolean operations, the distinction between the interior and the exterior of a polygon is determined by the order of its vertices.

The result of an intersection test is one of the boolean values true or false. The result of an intersection, union, or difference can be empty, a single object, or several objects. An object can be a point, a segment, a triangle, an iso-oriented rectangle, a polygon, or a polygon with one or several holes.

There, where the result cannot be more than one object (in the case of the intersection of two triangles, and the intersection of two iso-rectangles), the corresponding function returns an iterator of a possibly empty container. In all other cases the functions return an iterator referring to a sequence of objects. Note that whenever we refer to a `sequence' of objects we actually mean a collection of objects independent of the way in which they are stored. The user can define the type of sequence in which the output will be stored through the template parameter OutputIterator, see below for further details.

Vertices of input polygons must be ordered counterclockwise. Vertices of output polygons are ordered counterclockwise. However, vertices of polygons representing holes (as part of the output) are ordered clockwise. For instance, if the result of a boolean operation is a polygon with some holes, then this result will be represented as a sequence of polygons, where the first one representing the outer boundary of the contour is ordered counterclockwise and the following ones representing the inner contours (holes) are ordered clockwise.

For two simple polygons $A$ and $B$, the following operations are defined:

[Intersection test] of two polygons (CGAL_do_intersect(A,B)). This checks if the two polygons $A$ and $B$ do intersect, without computing the intersection area. It returns true if the polygons $A$ and $B$ do intersect, otherwise false will be returned.

[Intersection] of two polygons (CGAL_intersection(A,B)). It performs the operation $C:=A\; \backslash cap\; B$ and returns the result $C$ as a maybe empty sequence of objects (CGAL_Object), i.e. a sequence containing objects of type CGAL_Point_2, CGAL_Segment_2, and CGAL_Polygon_2. When $A$ and $B$ are both triangles (CGAL_Triangle_2) or when $A$ and $B$ are both iso-oriented rectangles (CGAL_Iso_rectangle) the result can only be empty or a single object CGAL_Object rather than a sequence of objects.

[Union] of two polygons ( CGAL_union(A,B)). It performs the operation $C:=A\; \backslash cup\; B$ and returns the result $C$ as a maybe empty sequence of objects (CGAL_Object), i.e. a sequence containing objects of type CGAL_Polygon_2. The first polygon gives the counterclockwise-ordered outer boundary of the contour of the union and the following polygons (if existing) define the inner clockwise-ordered contours (the holes). If $A\; \backslash cap\; B$ is exactly one point (a vertex of at least one of the two input polygons), the union returns one non-simple polygon. If $A\; \backslash cap\; B$ is empty, then a sequence will be returned consisting of $A$ and $B$ both represented as polygons with counterclockwise ordered contour.

[Difference] of two polygons (CGAL_difference(A,B)). This performs the operation $C:=A\; \backslash setminus\; interior(B)$ and returns the result $C$ as a maybe empty sequence of objects (CGAL_Object), i.e. a sequence containing objects of type CGAL_Point_2, CGAL_Segment_2, and CGAL_Polygon_2. If $A\; \backslash cap\; B$ is empty then $A$ will be returned. If $A\; \backslash cap\; B\; =\; A$ (i.e. $A\; \backslash subseteq\; B$), then the empty sequence will be returned. If $A\; \backslash cap\; B\; =\; B$ (i.e. $B\; \backslash subseteq\; A$, that means $B$ is a hole of $A$), then a sequence containing (two) objects $(A,B)$ of type CGAL_Polygon_2 will be returned, where the second one represents a hole and has clockwise order.

Parameters

A value for the template parameter R instantiates the representation type in which the input objects are defined and the boolean operations are computed.

The template parameter Container occurs where polygons (CGAL_Polygon_2) are used as input. The value for template parameter Container instatiates the type of the container in which the vertices of the polygon are stored.

Some operations have template parameter InputIterator. A value for the template parameter InputIterator is an iterator to the container in which the input polygon is stored. A value could be an STL list or LEDA list iterator, for example.

Also the output sometimes is stored in a sequence. A value for the template parameter OutputIterator instantiates an iterator to a container in which the output will be returned and defines the type of such container. A value could again be an STL list or LEDA list iterator, for example.

A value for the template parameter Traits is a boolean operations traits class. We provide the user a default boolean operations traits class for convenience, but the user can define own traits classes as well. For more details about boolean operations traits classes look at the table below, and in the section on the default traits class ().

Types

The number type R must be instantiated by the user, for instance as CGAL_Cartesian<CGAL_Rational>.

The container type Container for a polygon. The user must pre-instantiate this, for instance by list<CGAL_Point_2<CGAL_Cartesian<CGAL_Rational> > >.

The type of the iterator pointing to the container in which the input is stored: InputIterator. The user must pre-instantiate this for instance by list<CGAL_Point_2<CGAL_Cartesian<CGAL_Rational> > >::Iterator.

The type of the iterator pointing to the container in which the output is stored: OutputIterator. The user must pre-instantiate this for instance by list<CGAL_Point_2<CGAL_Cartesian<CGAL_Rational> > >::Iterator.

In the table below we describe the types which are defined in a boolean operations traits class. Such a traits class contains the most important type definitions used in the algorithms. These types can be changed by the user, if needed. In the first column of the table the types present in a boolean operations traits class are listed. In the second column a brief description of the respective types is given, and in the third column the default value for each of the types in given as they are defined in the standard boolean operations traits class. For more details on the standard boolean operations traits class we refer to Section . \begincenter

\hline type	description	standard
\hline \hline Traits::R	Representation class	CGAL_Cartesian<CGAL_Rational>
\hline Traits::Point	2D point	CGAL_Point_2<Traits::R> >
\hline Traits::Segment	2D segment	CGAL_Segment_2<Traits::R> >
\hline Traits::Triangle	2D triangle	CGAL_Triangle_2<Traits::R >
\hline Traits::Iso_rectangle	2D iso-oriented rectangle	CGAL_Iso_rectangle_2<Traits::R >
\hline Traits::Container	polygon container type	list<CGAL_Point_2<Traits::R> >
\hline Traits::Polygon	2D polygon	CGAL_Polygon_2<Traits::R, Traits::Container >
\hline \hline

\endcenter

Operations

template <R>
bool	CGAL_do_intersect ( CGAL_Triangle_2<R> A, CGAL_Triangle_2<R> B)
		returns true if the triangles $A$ and $B$ do intersect.

template <R>
bool	CGAL_do_intersect ( CGAL_Iso_rectangle_2<R> A, CGAL_Iso_rectangle_2<R> B)
		returns true if the iso-oriented rectangles $A$ and $B$ do intersect.

template <R, Container>
bool	CGAL_do_intersect ( CGAL_Polygon_2<R,Container> A, CGAL_Polygon_2<R,Container> B)
		returns true if the polygons $A$ and $B$ do intersect. Precondition: $A$ and $B$ are simple polygons, their vertices are in counterclockwise order.

template <InputIterator, Traits>
bool	CGAL_do_intersect ( InputIterator Afirst, InputIterator Alast, InputIterator Bfirst, InputIterator Blast, Traits &)
		with polygon A of type Traits::Polygon defined by the vertices of type Traits::Point in the range $[Afirst,Alast)$ and for polygon B of type Traits::Polygon defined by the vertices of type Traits::Point in the range $[Bfirst,Blast)$. It returns true if the polygons $A$ and $B$ do intersect. Precondition: $A$ and $B$ are simple polygons, their vertices are in counterclockwise order.

template <R, OutputIterator>
OutputIterator	CGAL_intersection ( CGAL_Triangle_2<R> A, CGAL_Triangle_2<R> B, OutputIterator object_it)
		computes the intersection of two triangles and places the resulting object of type CGAL_Object in a container of the type corresponding to the output iterator (OutputIterator) object_it which points to the resulting object. The function returns an output iterator (of type OutputIterator) pointing to the position beyond the end of the container. The resulting object is either a point (CGAL_Point_2), or a segment ( CGAL_Segment_2), or a triangle (CGAL_Triangle_2), or a convex polygon (CGAL_Polygon_2 with is_convex() == true). In case of an empty intersection, no object is put into the container.

template <R, OutputIterator>
OutputIterator	CGAL_intersection ( CGAL_Iso_rectangle_2<R> A, CGAL_Iso_rectangle_2<R> B, OutputIterator object_it)
		computes the intersection of two iso-oriented rectangles and places the resulting object of type CGAL_Object in a container of the type corresponding to the output iterator ( OutputIterator) object_it which points to the resulting object. The function returns an output iterator (of type OutputIterator) pointing to the position beyond the end of the container. The resulting object is either a point ( CGAL_Point_2), or a segment (CGAL_Segment_2), or a triangle (CGAL_Triangle_2), or a convex polygon ( CGAL_Polygon_2 with is_convex() == true). In case of an empty intersection, no object is put into the container.

template <R, Container, OutputIterator>
OutputIterator	CGAL_intersection ( CGAL_Polygon_2<R,Container> A, CGAL_Polygon_2<R,Container> B, OutputIterator list_of_objects_it)
		computes the intersection of two simple polygons and places all resulting objects as a sequence of objects of type CGAL_Object in a container of the type corresponding to the type of output iterator list_of_objects_it ( OutputIterator) which points to the first object in the sequence. The function returns an output iterator ( OutputIterator) pointing to the position beyond the end of the sequence. In case of an empty intersection, no objects are put into the sequence. Precondition: $A$ and $B$ simple polygons, their vertices are in counterclockwise order.

template <InputIterator, OutputIterator, Traits>
OutputIterator	CGAL_intersection ( InputIterator Afirst, InputIterator Alast, InputIterator Bfirst, InputIterator Blast, Traits &, OutputIterator list_of_objects_it)
		with polygon A of type Traits::Polygon defined by the vertices of type Traits::Point in the range $[Afirst,Alast)$ and with polygon B of type Traits::Polygon defined by the vertices of type Traits::Point in the range $[Bfirst,Blast)$. Computes the intersection of two simple polygons and places all resulting objects as a sequence of objects of type CGAL_Object in a container of the type corresponding to the type of output iterator list_of_objects_it ( OutputIterator), which points to the first object in the sequence. The function returns an output iterator ( OutputIterator) pointing to the position beyond the end of the sequence. In case of an empty intersection, no objects are put into the sequence. If an object in the sequence to which the output iterator refers is a polygon, then this polygon is of type Traits::Polygon with vertices of type Traits::Point and container Traits::Container. Precondition: $A$ and $B$ are simple polygons, their vertices are in counterclockwise order.

template <R, OutputIterator>
OutputIterator	CGAL_union ( CGAL_Triangle_2<R> A, CGAL_Triangle_2<R> B, OutputIterator list_of_objects_it)
		computes the union of two triangles and places all resulting objects as a sequence of objects of type CGAL_Object in a container of the type corresponding to the type of output iterator list_of_objects_it (OutputIterator), which points to the first object in the sequence. The function returns an output iterator (OutputIterator) pointing to the position beyond the end of the sequence. The sequence may contain a triangle ( CGAL_Triangle_2), a simple polygon (CGAL_Polygon_2), or two triangles (CGAL_Polygon_2, when $A\; \backslash cap\; B$ is empty).

template <R, OutputIterator>
OutputIterator	CGAL_union ( CGAL_Iso_rectangle_2<R> A, CGAL_Iso_rectangle_2<R> B, OutputIterator list_of_objects_it)
		computes the union of two iso-oriented rectangles and places all resulting objects as a sequence of objects of type CGAL_Object in a container of the type corresponding to the type of output iterator list_of_objects_it ( OutputIterator), which points to the first object in the sequence. The function returns an output iterator ( OutputIterator) pointing to the position beyond the end of the sequence. The sequence may contain an iso-oriented rectangle ( CGAL_Iso_rectangle_2), a simple polygon ( CGAL_Polygon_2), or two iso-oriented rectangles ( CGAL_Iso_rectangle_2, when $A\; \backslash cap\; B$ is empty).

template <R, Container, OutputIterator>
OutputIterator	CGAL_union ( CGAL_Polygon_2<R,Container> A, CGAL_Polygon_2<R,Container> B, OutputIterator list_of_objects_it)
		computes the union of two simple polygons and places all resulting objects as a sequence of objects of type CGAL_Object in a container of the type corresponding to the type of output iterator list_of_objects_it (OutputIterator), which points to the first object in the sequence. The function returns an output iterator (OutputIterator) pointing to the position beyond the end of the sequence. Precondition: $A$ and $B$ are simple polygons, their vertices are in counterclockwise order.

template <InputIterator, OutputIterator, Traits>
OutputIterator	CGAL_union ( InputIterator Afirst, InputIterator Alast, InputIterator Bfirst, InputIterator Blast, Traits &, OutputIterator list_of_objects_it)
		with polygon A of type Traits::Polygon defined by the vertices of type Traits::Point in the range $[Afirst,Alast)$ and with polygon B of type Traits::Polygon defined by the vertices of type Traits::Point in the range $[Bfirst,Blast)$. Computes the union of two simple polygons ($A\; \backslash cup\; B$) and places all resulting objects as a sequence of objects of type CGAL_Object in a container of the type corresponding to the type of output iterator list_of_objects_it ( OutputIterator), which points to the first object in the sequence. It returns an output iterator (OutputIterator) pointing to position beyond the end of the sequence. If an object in the sequence to which the output iterator refers is a polygon, then this polygon is of type Traits::Polygon with vertices of type Traits::Point and container of type Traits::Container. Precondition: $A$ and $B$ are simple polygons, their vertices are in counterclockwise order.

template <R, OutputIterator>
OutputIterator	CGAL_difference ( CGAL_Triangle_2<R> A, CGAL_Triangle_2<R> B, OutputIterator list_of_objects_it)
		Computes the difference ($A\; \backslash setminus\; B$) of two triangles and places all resulting objects as a sequence of objects of type CGAL_Object in a container of the type corresponding to the type of output iterator list_of_objects_it ( OutputIterator), which points to the first object in the sequence. It returns an output iterator (OutputIterator) pointing to the position beyond the end of the sequence. Each object in the sequence is either a triangle (CGAL_Triangle_2 ), or a simple polygon (CGAL_Polygon_2). If $B\; \backslash subseteq\; A$, no object will be put into the container.

template <R, OutputIterator>
OutputIterator	CGAL_difference ( CGAL_Iso_rectangle_2<R> A, CGAL_Iso_rectangle_2<R> B, OutputIterator list_of_objects_it)
		computes the difference ($A\; \backslash setminus\; B$) of two iso-oriented rectangles, and places the resulting objects of type CGAL_Object in a container of the type corresponding to the type of output iterator list_of_objects_it ( OutputIterator), which points to the first object in the sequence. The function returns an output iterator ( OutputIterator) pointing to the position beyond the end of the sequence. Each object is either a simple polygon ( CGAL_Polygon_2) or an iso-oriented rectangle ( CGAL_Iso_rectangle_2). If $B\; \backslash subseteq\; A$, no object will be put into the output container.

template <R, Container, OutputIterator>
OutputIterator	CGAL_difference ( CGAL_Polygon_2<R,Container> A, CGAL_Polygon_2<R,Container> B, OutputIterator list_of_objects_it)
		computes the difference of two simple polygons ($A\; \backslash setminus\; B$) and places the resulting object of type CGAL_Object in a container of type corresponding to the type of output iterator list_of_objects_it ( OutputIterator), which points to the first object in the sequence. The function returns an output iterator ( OutputIterator) pointing to the position beyond the end of the sequence. The difference can be empty, in which case no object will be put in the container. Precondition: $A$ and $B$ are simple polygons, their vertices are in counterclockwise order.

template <InputIterator, OutputIterator, Traits>
OutputIterator	CGAL_difference ( InputIterator Afirst, InputIterator Alast, InputIterator Bfirst, InputIterator Blast, Traits &, OutputIterator list_of_objects_it)
		with polygon A of type Traits::Polygon defined by the vertices of type Traits::Point in the range $[Afirst,Alast)$ and with polygon B of type Traits::Polygon defined by the vertices of type Traits::Point in the range $[Bfirst,Blast)$. Computes the difference of two simple polygons ($A\; \backslash setminus\; B$) and places all resulting objects of type CGAL_Object in a container of the type corresponding to the type of output iterator list_of_objects_it ( OutputIterator), which points to the first object in the sequence. The function returns an output iterator ( OutputIterator) pointing to the position beyond the end of the sequence. The difference can be empty in which case no object will be put in the container. If an object in the sequence to which the output iterator refers is a polygon, then this polygon is of type Traits::Polygon with vertices of type Traits::Point and container of type Traits::Container . Precondition: $A$ and $B$ are simple polygons, their vertices are in counterclockwise order.

Example

1. To use the predefined boolean operations traits class Traits, include the file bops_standard_traits.h. For details see Section .

2. Instantiation of Polygons (triangles, iso oriented rectangles, simple polygons). Do not forget to include list.h of the STL library.

3. Performing the boolean operation:

     CGAL_intersection(A.begin(), A.end(), B.begin(), B.end(), trcls, bopsOutIt);
   

4. Taking the result of the operation:

   The result consists of a sequence of points, segments, and simple polygons. Hence, the user has to check what type of element has to be performed for further computations.

A full example (note: here the non-exact number type CGAL_Quotient<int> is used):

#ifdef __GNUC__
#include <typeinfo>
#endif
#include <iostream.h>

#include <CGAL/Homogeneous.h>
#include <CGAL/Cartesian.h>
#include <CGAL/basic.h>

#include <list.h>
#include <CGAL/boolean_operations_2.h>


typedef CGAL_Quotient<int> TestNum;
//typedef CGAL_Cartesian<TestNum>              R_type;
typedef CGAL_Homogeneous<TestNum>              R_type;
typedef CGAL_Point_2<R_type>                     Point_2;
typedef CGAL_Segment_2<R_type>                  Segment_2;
typedef list< Point_2 >                            Container;
typedef CGAL_Polygon_2< R_type, Container >  Polygon_2;


typedef vector<Point_2>                           Input_container;

int example_intersection(
  const Input_container& container_A,
  const Input_container& container_B
) {
  /* possible results */
  Point_2   point;
  Segment_2 segment;
  Polygon_2 polygon;

  /* instantiate Polygon A and B with containers */
  Polygon_2 A(container_A.begin(), container_A.end());
  Polygon_2 B(container_B.begin(), container_B.end());

  /* declaration of the result container */
  list<CGAL_Object> result;

  /* performing intersection of A and B */
  CGAL_intersection(A, B, back_inserter(result));
  
  /* print out the result */
  cout << "size=" << result.size() << endl;

  /* declaration of an iterator on the result container */
  list<CGAL_Object>::const_iterator it;
  for( it= result.begin(); it != result.end(); it++) {
    if( CGAL_assign( polygon, *it) ) {
      cout << polygon << endl;               /* polygon detected */
    }
    else if( CGAL_assign( segment, *it) ) {
      cout << segment << endl;               /* segment detected */
    }
    else if( CGAL_assign( point, *it) )  {  
      cout << point << endl;                     /* point detected */
    }
    else {
      cout << "undefined object " << endl;   /* nothing detected */
    }
  }
  
  /* return size of result */
  return result.size();
}



int main(void)
{
  Input_container container_A(6), container_B(4);

  container_A[0]= Point_2(2,4);
  container_A[1]= Point_2(0,3);
  container_A[2]= Point_2(1,1);
  container_A[3]= Point_2(2,3);
  container_A[4]= Point_2(3,1);
  container_A[5]= Point_2(4,3);
  container_B[0]= Point_2(0,2);
  container_B[1]= Point_2(0,0);
  container_B[2]= Point_2(5,0);
  container_B[3]= Point_2(5,2);

  example_intersection( container_A, container_B);
  return 0;
}

A full example for more advanced use:

#include <CGAL/bops_standard_traits_2.h>

typedef CGAL_Rational aNT;
typedef CGAL_Cartesian<aNT> anR;
typedef bops_standard_traits_2<anR> TraitsCls;

TraitsCls::Point point;
TraitsCls::Segment segment;
TraitsCls::Polygon polygon;
CGAL_Object obj;
TraitsCls trcls;

Polygon A, B;
// instantiate A and B:
// ..

// apply a boolean operation:
list<CGAL_Object> B_ops_result; 
insert_iterator< list<CGAL_Object> > 
                               bopsOutIt(B_ops_result,B_ops_result.begin());

CGAL_intersection(A.begin(), A.end(), B.begin(), B.end(), trcls, bopsOutIt);

// do something with the result:
// ..

From this example can be seen how a boolean operation could be applied in a safe and practical way.

Implementation

The memory consumption is $O(n)$ (where $n$ is the whole number of vertices of the input polygons). The time complexity is $O(n2)$ for simple polygons, and $O(1)$ for triangles and iso-oriented rectangles.

Note: As mentioned above, the result is sometimes returned as iterators pointing to a list<CGAL_Object>, where list is a STL list container, which implements a double connected list (include file: list.h).

Predefined Boolean Operations Traits Class

Since all geometric objects on which boolean operations act are parameterized with a template for the number type, also the predefined boolean operations traits class is a template class with a parameter for the number type _R. The predefined boolean operations traits class is called bops_standard_traits_2<_R>.

Types

typedef _R R;
The number type over which the computations are performed.

typedef CGAL_Point_2<R> Point;
The type of points representing the vertices of triangles, iso-oriented rectangles, polygons, and of the types point and segment which occur as possible types of the result of boolean operations.

typedef list<Point> Container;
The container in which points of type Point are stored for further use in the polygons on which boolean operations are to be performed.

typedef CGAL_Segment_2<R> Segment;
The type of return values representing a line segment.

typedef CGAL_Triangle_2<R> Triangle;
The type of triangles on which boolean operations can be performed.

typedef CGAL_Iso_rectangle_2<R> Iso_rectangle;
The type of iso-oriented rectangles on which boolean operations can be performed.

typedef CGAL_Polygon_2<R, Container > Polygon;
The type of polygons on which boolean operations can be performed.

typedef CGAL_Direction_2<R> Direction;
A type used internally in the computation of boolean operations.