CGAL 4.13  2D Regularized Boolean SetOperations

#include <CGAL/General_polygon_set_2.h>
An object of the General_polygon_set_2
classtemplate represents a point set in the plane bounded by \( x\) monotone curves.
Points in the set lie on the boundary or on the positive side of the curves. This class template provides methods to apply regularized Boolean setoperations and few other utility methods. An Arrangement_2
data structure is internally used to represent the point set. The arrangement is represented as a doublyconnected edgelist (Dcel).
The Traits
templateparameter should be instantiated with a model of the concept GeneralPolygonSetTraits_2
. The traits class defines the types of points, \( x\)monotone curves, general polygons, and general polygons with holes, that is Traits::Point_2
, Traits::X_monotone_curve_2
, Traits::Polygon_2
, and Traits::Polygon_with_holes_2
, respectively. Traits::Point_2
must be the type of the endpoints of Traits::X_monotone_curve_2
, and Traits::X_monotone_curve_2
must be the type of the curves that comprise the boundaries of the general polygons. The traits class supports geometric operations on the types above. We sometimes use the term polygon instead of general polygon for simplicity hereafter.
The template parameter Dcel
should be instantiated with a model of the concept GeneralPolygonSetDcel
. It is instantiated by default with the type Gps_default_dcel<Traits>
. You can override this default, with a different Dcel class, typically an extension of the Gps_default_dcel
class template. Overriding the default is necessary only if you intend to obtain the underlying internal arrangement and process it further.
The input and output of the Boolean setoperations methods consist of one or more general polygons, some of which may have holes. In particular, these methods operate on pairs of objects of type General_polygon_set_2
, or directly on objects of type Traits::Polygon_2
or Traits::Polygon_with_holes_2
. An object of type Traits::Polygon_2
is a valid operand, only if it is simple and its boundary is oriented counterclockwise. An object of type Traits::Polygon_with_holes_2
is valid, only if its outer boundary bounds a relatively simple general polygon oriented counterclockwise, and each one of its holes is a simple polygon oriented clockwise. The holes are pairwise disjoint, except perhaps at the vertices, and are contained in the polygon bounded by the outer boundary. The outer boundary and the holes are also pairwise disjoint, except perhaps at the vertices.
Types  
typedef unspecified_type  Traits_2 
the traits class in use.  
typedef unspecified_type  Polygon_2 
the general polygon type. More...  
typedef unspecified_type  Polygon_with_holes_2 
the general polygon with holes type. More...  
typedef unspecified_type  Size 
number of polygons with holes size type.  
typedef unspecified_type  Arrangement_2 
the arrangement type used internally.  
Creation  
General_polygon_set_2 ()  
constructs an empty set of polygons gps represented by an empty arrangement.  
General_polygon_set_2 (const Self &other)  
copy constructor.  
General_polygon_set_2 (Traits &traits)  
constructs an empty set of polygons gps that uses the given traits instance for performing the geometric operations.  
General_polygon_set_2 (const Polygon_2 &pgn)  
constructs a set of polygons gps that consists of the single polygon pgn .  
General_polygon_set_2 (const Polygon_with_holes_2 &pgn_with_holes)  
constructs a set of polygons gps that consists of the single polygon with holes pgn_with_holes .  
Access Functions  
template<class OutputIterator >  
OutputIterator  polygons_with_holes (OutputIterator out) 
obtains the polygons with holes represented by gps .  
Size  number_of_polygons_with_holes () const 
returns the total number of general polygons represented by gps .  
bool  is_empty () const 
returns true if gps represents an empty set.  
bool  is_plane () const 
returns true if gps represents the entire plane.  
Traits &  traits () const 
obtains an instance of the traits. More...  
const Arrangement_2 &  arrangement () const 
obtains the arrangement data structure that internally represents the generalpolygon set.  
Modifiers  
void  clear () 
clears gps .  
void  insert (Polygon_2 &pgn) 
inserts pgn into gps . More...  
void  insert (Polygon_with_holes_2 &pgn_with_holes) 
inserts pgn_with_holes into gps . More...  
template<class InputIterator >  
void  insert (InputIterator begin, InputIterator end) 
inserts the range of polygons (or polygons with holes) into gps . More...  
template<class InputIterator1 , class InputIterator2 >  
void  insert (InputIterator1 pgn_begin, InputIterator1 pgn_end, InputIterator2 pgn_with_holes_begin, InputIterator2 pgn_with_holes_end) 
inserts the two ranges of polygons and polygons with holes into gps . More...  
void  complement () 
computes the complement of gps .  
void  complement (const Polygon_set_2 &other) 
computes the complement of other . More...  
Univariate Operations  
In the following univariate and bivariate methods the result is placed in  
void  intersection (const General_polygon_set_2 &other) 
computes the intersection of gps and other .  
void  intersection (const Polygon_2 &pgn) 
computes the intersection of gps and pgn .  
void  intersection (const Polygon_with_holes_2 &pgn) 
computes the intersection of gps and pgn .  
template<class InputIterator >  
void  intersection (InputIterator begin, InputIterator end) 
computes the intersection of a collection of point sets. More...  
template<class InputIterator1 , class InputIterator2 >  
void  intersection (InputIterator1 pgn_begin, InputIterator1 pgn_end, InputIterator2 pgn_with_holes_begin, InputIterator2 pgn_with_holes_end) 
computes the intersection of a collection of point sets. More...  
void  join (const General_polygon_set_2 &other) 
computes the union of gps and other .  
void  join (const Polygon_2 &pgn) 
computes the union of gps and pgn .  
void  join (const Polygon_with_holes_2 &pgn) 
computes the union of gps and pgn .  
template<class InputIterator >  
void  join (InputIterator begin, InputIterator end) 
computes the union of the polygons (or polygons with holes) in the given range and the point set represented by gps . More...  
template<class InputIterator1 , class InputIterator2 >  
void  join (InputIterator1 pgn_begin, InputIterator1 pgn_end, InputIterator2 pgn_with_holes_begin, InputIterator2 pgn_with_holes_end) 
computes the union of the polygons and polygons with holes in the given two ranges and the point set represented by gps .  
void  difference (const General_polygon_set_2 &other) 
computes the difference between gps and other .  
void  difference (const Polygon_2 &pgn) 
computes the difference between gps and pgn .  
void  difference (const Polygon_with_holes_2 &pgn) 
computes the difference between gps and pgn .  
void  symmetric_difference (const General_polygon_set_2 &other) 
computes the symmetric difference between gps and other .  
void  symmetric_difference (const Polygon_2 &pgn) 
computes the symmetric difference between gps and pgn .  
void  symmetric_difference (const Polygon_with_holes_2 &pgn) 
computes the symmetric difference between gps and pgn .  
template<class InputIterator >  
void  symmetric_difference (InputIterator begin, InputIterator end) 
computes the symmetric difference (xor) of a collection of point sets. More...  
template<class InputIterator1 , class InputIterator2 >  
void  symmetric_difference (InputIterator1 pgn_begin, InputIterator1 pgn_end, InputIterator2 pgn_with_holes_begin, InputIterator2 pgn_with_holes_end) 
computes the symmetric difference (xor) of a collection of point sets. More...  
Bivariate Operations  
The following bivariate function replace  
void  intersection (const General_polygon_set_2 &gps1, const General_polygon_set_2 &gps2) 
computes the intersection of gps1 and gps2 .  
void  join (const General_polygon_set_2 &gps1, const General_polygon_set_2 &gps2) 
computes the union of gps1 and gps2 .  
void  difference (const General_polygon_set_2 &gps1, const General_polygon_set_2 &gps2) 
computes the difference between gps1 and gps2 .  
void  symmetric_difference (const General_polygon_set_2 &gps1, const General_polygon_set_2 &gps2) 
computes the symmetric difference between gps1 and gps2 .  
Query Functions  
bool  do_intersect (const General_polygon_set_2 &other) 
returns true if gps and other intersect in their interior, and false otherwise.  
bool  do_intersect (const Polygon_2 &pgn) 
returns true if gps and pgn intersect in their interior, and false otherwise.  
bool  do_intersect (const Polygon_with_holes_2 &pgn) 
returns true if gps and pgn intersect in their interior, and false otherwise.  
template<class InputIterator >  
void  do_intersect (InputIterator begin, InputIterator end) 
returns true if the interior of the point sets in a collection intersect, and false otherwise. More...  
template<class InputIterator1 , class InputIterator2 >  
void  do_intersect (InputIterator1 pgn_begin, InputIterator1 pgn_end, InputIterator2 pgn_with_holes_begin, InputIterator2 pgn_with_holes_end) 
returns true if the interior of the point sets in a collection intersect, and false otherwise. More...  
bool  locate (const Point_2 &p, Polygon_with_holes_2 &pgn) 
obtains a polygon with holes that contains the query point p , if exists, through pgn , and returns true . More...  
Oriented_side  oriented_side (const Point_2 &q) 
returns either the constant ON_ORIENTED_BOUNDARY , ON_POSITIVE_SIDE , or ON_NEGATIVE_SIDE , iff p lies on the boundary, properly on the positive side, or properly on the negative side of gps respectively.  
Oriented_side  oriented_side (const General_polygon_set_2 &other) 
returns either the constant ON_NEGATIVE_SIDE , ON_ORIENTED_BOUNDARY , or ON_POSITIVE_SIDE , iff other and gps are completely disjoint, in contact, or intersect in their interior, respectively.  
Oriented_side  oriented_side (const Polygon_2 &pgn) 
returns either the constant ON_NEGATIVE_SIDE , ON_ORIENTED_BOUNDARY , or ON_POSITIVE_SIDE , iff pgn and gps are completely disjoint, in contact, or intersect in their interior, respectively.  
Oriented_side  oriented_side (const Polygon_with_holes_2 &pgn) 
returns either the constant ON_NEGATIVE_SIDE , ON_ORIENTED_BOUNDARY , or ON_POSITIVE_SIDE , iff pgn and gps are completely disjoint, in contact, or intersect in their interior, respectively.  
Miscellaneous  
bool  is_valid () const 
returns true if gps represents a valid point set.  
typedef unspecified_type CGAL::General_polygon_set_2< Traits, Dcel >::Polygon_2 
the general polygon type.
Must model the GpsTraitsGeneralPolygon_2
concept.
typedef unspecified_type CGAL::General_polygon_set_2< Traits, Dcel >::Polygon_with_holes_2 
the general polygon with holes type.
Must model the GpsTraitsGeneralPolygonWithHoles_2
concept.
void CGAL::General_polygon_set_2< Traits, Dcel >::complement  (  const Polygon_set_2 &  other  ) 
computes the complement of other
.
gps
is overridden by the result.
void CGAL::General_polygon_set_2< Traits, Dcel >::do_intersect  (  InputIterator  begin, 
InputIterator  end  
) 
returns true
if the interior of the point sets in a collection intersect, and false
otherwise.
The collection consists of the polygons (or polygons with holes) in the given range and the point set represented by gps
. (The value type of the input iterator is used to distinguish between the two options.)
void CGAL::General_polygon_set_2< Traits, Dcel >::do_intersect  (  InputIterator1  pgn_begin, 
InputIterator1  pgn_end,  
InputIterator2  pgn_with_holes_begin,  
InputIterator2  pgn_with_holes_end  
) 
returns true
if the interior of the point sets in a collection intersect, and false
otherwise.
The collection consists of the polygons and polygons with holes in the given two ranges and the point set represented by gps
.
void CGAL::General_polygon_set_2< Traits, Dcel >::insert  (  Polygon_2 &  pgn  ) 
inserts pgn
into gps
.
pgn
and the point set represented by gps
are disjoint. This precondition enables the use of very efficient insertion methods. Use the respective overloaded method that inserts a polygon of type Polygon_with_holes_2
, if only a relaxed precondition can be guaranteed. If even the relaxed precondition cannot be guaranteed, use the join
method. void CGAL::General_polygon_set_2< Traits, Dcel >::insert  (  Polygon_with_holes_2 &  pgn_with_holes  ) 
inserts pgn_with_holes
into gps
.
pgn_with_holes
does not intersect with the point set represented by gps
, except maybe at the vertices. If this relaxed precondition cannot be guaranteed, use the join
method. void CGAL::General_polygon_set_2< Traits, Dcel >::insert  (  InputIterator  begin, 
InputIterator  end  
) 
inserts the range of polygons (or polygons with holes) into gps
.
(The value type of the input iterator is used to distinguish between the two.)
Polygon_with_holes_2
, then these polygons and the point set represented by gps
are pairwise disjoint, except maybe at the vertices. If the given range contains objects of type Polygon_2
, then these polygons and the point set represented by gps
are pairwise disjoint without any exceptions. void CGAL::General_polygon_set_2< Traits, Dcel >::insert  (  InputIterator1  pgn_begin, 
InputIterator1  pgn_end,  
InputIterator2  pgn_with_holes_begin,  
InputIterator2  pgn_with_holes_end  
) 
inserts the two ranges of polygons and polygons with holes into gps
.
gps
are pairwise disjoint, except maybe at the vertices void CGAL::General_polygon_set_2< Traits, Dcel >::intersection  (  InputIterator  begin, 
InputIterator  end  
) 
computes the intersection of a collection of point sets.
The collection consists of the polygons (or polygons with holes) in the given range and the point set represented by gps
. (The value type of the input iterator is used to distinguish between the two options.)
void CGAL::General_polygon_set_2< Traits, Dcel >::intersection  (  InputIterator1  pgn_begin, 
InputIterator1  pgn_end,  
InputIterator2  pgn_with_holes_begin,  
InputIterator2  pgn_with_holes_end  
) 
computes the intersection of a collection of point sets.
The collection consists of the polygons and polygons with holes in the given two ranges and the point set represented by gps
.
void CGAL::General_polygon_set_2< Traits, Dcel >::join  (  InputIterator  begin, 
InputIterator  end  
) 
computes the union of the polygons (or polygons with holes) in the given range and the point set represented by gps
.
(The value type of the input iterator is used to distinguish between the two options.)
bool CGAL::General_polygon_set_2< Traits, Dcel >::locate  (  const Point_2 &  p, 
Polygon_with_holes_2 &  pgn  
) 
obtains a polygon with holes that contains the query point p
, if exists, through pgn
, and returns true
.
Otherwise, returns false
.
void CGAL::General_polygon_set_2< Traits, Dcel >::symmetric_difference  (  InputIterator  begin, 
InputIterator  end  
) 
computes the symmetric difference (xor) of a collection of point sets.
The collection consists of the polygons (or polygons with holes) in the given range and the point set represented by gps
. (The value type of the input iterator is used to distinguish between the two options.)
void CGAL::General_polygon_set_2< Traits, Dcel >::symmetric_difference  (  InputIterator1  pgn_begin, 
InputIterator1  pgn_end,  
InputIterator2  pgn_with_holes_begin,  
InputIterator2  pgn_with_holes_end  
) 
computes the symmetric difference (xor) of a collection of point sets.
The collection consists of the polygons and polygons with holes in the given two ranges and the point set represented by gps
.
Traits& CGAL::General_polygon_set_2< Traits, Dcel >::traits  (  )  const 
obtains an instance of the traits.
If the traits was passed as a parameter to the constructor of gps
, it is returned. Otherwise, a newly created instance is returned.