CGAL 5.4 - 2D Straight Skeleton and Polygon Offsetting

The following functions are used to construct the inward or outward offsets of a polygon.

Kernel Choices

Up to three different kernels can be used in the offset construction process:

When the kernel differs, CGAL::Cartesian_converter is used to convert from one kernel to the other.

By default, SsK and OfK are chosen as CGAL::Exact_predicates_inexact_constructions_kernel as a compromise between speed and robustness. See also Section Create Offset Polygons from a Polygon (With or Without Holes).

Polygon Return Type

There are two classes of offset construction functions: those that simply return all the offset polygons, and those that also create an arrangement of the polygons to create a polygon with holes. The latter contain _with_holes in the name.

The return type of the offset construction function is thus dediced by whether or not it is a simple polygon or a polygon with holes, and on the dictated output kernel (see Section Kernel Choices). Thus, for an input polygon type InKPolygon in an offset construction that does not arrange polygons (e.g. create_interior_skeleton_and_offset_polygons_2()):

Similarly, if the return type is a polygon with holes (e.g. create_interior_skeleton_and_offset_polygons_with_holes_2(), a similar dispatch exists:

Functions

template<class K , class InputPolygonPtrIterator , class OutputPolygonWithHolesPtrIterator >
bool CGAL::arrange_offset_polygons_2 (InputPolygonPtrIterator begin, InputPolygonPtrIterator end, OutputPolygonWithHolesPtrIterator out, const K &k)
 The function arrange_offset_polygons_2() arranges the sequence of 2D polygons obtained by create_offset_polygons_2() into 2D polygons with holes by determining geometric parent-hole relationships using a simple algorithm based on the particular characteristics of offset polygons. More...
 
template<class InputIterator , class Traits >
boost::optional< typename Traits::FT > CGAL::compute_outer_frame_margin (InputIterator first, InputIterator beyond, typename Traits::FT offset, const Traits &traits=Default_traits)
 computes the separation required between a polygon and the outer frame used to obtain an exterior skeleton suitable for the computation of outer offset polygons at a given distance. More...
 
template<class OfKPolygon , class FT , class StraightSkeleton , class OfK >
std::vector< boost::shared_ptr< OfKPolygon > > CGAL::create_offset_polygons_2 (FT offset, const StraightSkeleton &s, OfK k=Exact_predicates_inexact_constructions_kernel)
 returns a container with the offset polygons at distance offset obtained from the straight skeleton s. More...
 
template<class OfKPolygon , class FT , class InKPolygon , class OfK , class SsK >
std::vector< boost::shared_ptr< OfKPolygon > > CGAL::create_exterior_skeleton_and_offset_polygons_2 (FT offset, const InKPolygon &poly, OfK ofk=Exact_predicates_inexact_constructions_kernel, SsK ssk=Exact_predicates_inexact_constructions_kernel)
 returns a container with all the outer offset polygons at distance offset of the 2D polygon poly. More...
 
template<class OfKPolygon , class FT , class InKPolygon , class HoleIterator , class OfK , class SsK >
std::vector< boost::shared_ptr< OfKPolygon > > CGAL::create_interior_skeleton_and_offset_polygons_2 (FT offset, const InKPolygon &outer_boundary, HoleIterator holes_begin, HoleIterator holes_end, OfK ofk=CGAL::Exact_predicates_inexact_constructions_kernel, SsK ssk=CGAL::Exact_predicates_inexact_constructions_kernel)
 returns a container with all the inner offset polygons at distance offset of the 2D polygon with holes whose outer boundary is outer_boundary and its holes are given by [holes_begin,holes_end). More...
 
template<class OfKPolygon , class FT , class InKPolygon , class OfK , class SsK >
std::vector< boost::shared_ptr< OfKPolygon > > CGAL::create_interior_skeleton_and_offset_polygons_2 (FT offset, const InKPolygon &poly, OfK ofk=CGAL::Exact_predicates_inexact_constructions_kernel, SsK ssk=CGAL::Exact_predicates_inexact_constructions_kernel)
 returns a container with all the inner offset polygons at distance offset of the 2D polygon poly. More...
 
template<class OfKPolygon , class FT , class InKPolygon , class OfK , class SsK >
std::vector< boost::shared_ptr< OfKPolygon > > CGAL::create_interior_skeleton_and_offset_polygons_with_holes_2 (FT offset, const InKPolygon &poly_with_holes, OfK ofk=CGAL::Exact_predicates_inexact_constructions_kernel, SsK ssk=CGAL::Exact_predicates_inexact_constructions_kernel)
 returns a container with all the inner offset polygons with holes at distance offset of the 2D polygon with holes poly_with_holes. More...
 
template<class OfKPolygon , class FT , class InKPolygon , class OfK , class SsK >
std::vector< boost::shared_ptr< OfKPolygon > > CGAL::create_exterior_skeleton_and_offset_polygons_with_holes_2 (FT offset, const InKPolygon &poly_with_holes, OfK ofk=Exact_predicates_inexact_constructions_kernel, SsK ssk=Exact_predicates_inexact_constructions_kernel)
 returns a container with all the outer offset polygons with holes at distance offset of the 2D polygon poly_with_holes. More...
 
template<class Target_skeleton , class Source_skeleton , class Items_converter >
boost::shared_ptr< Target_skeleton > CGAL::convert_straight_skeleton_2 (Source_skeleton const &s, Items_converted const &ic=Items_converter())
 returns a new straight skeleton data structure with the same combinatorial and geometric data as s using the items converter ic to convert the geometric embedding to the types of the target skeleton. More...
 

Function Documentation

◆ arrange_offset_polygons_2()

template<class K , class InputPolygonPtrIterator , class OutputPolygonWithHolesPtrIterator >
bool CGAL::arrange_offset_polygons_2 ( InputPolygonPtrIterator  begin,
InputPolygonPtrIterator  end,
OutputPolygonWithHolesPtrIterator  out,
const K &  k 
)

#include <CGAL/arrange_offset_polygons_2.h>

The function arrange_offset_polygons_2() arranges the sequence of 2D polygons obtained by create_offset_polygons_2() into 2D polygons with holes by determining geometric parent-hole relationships using a simple algorithm based on the particular characteristics of offset polygons.

The function determines parent-hole relationships among the polygons given by [begin,end] creating boost::shared_ptr< GeneralPolygonWithHoles_2 > objects added to the output sequence given out. A CLOCKWISE oriented polygon H is a hole of a COUNTERCLOCKWISE polygon P, iff at least one vertex of H is ON_BOUNDED_SIDE of P.

This function should not be used to arrange arbitrary polygons into polygons with holes unless they meet the requirements specified below.

Template Parameters
Kmust be a model of Kernel.
InputPolygonPtrIteratormust be a model of InputIterator whose value_type is a smart pointer (such as boost::shared_ptr) whose element_type is a model of SequenceContainer with value type K::Point_2.
OutputPolygonWithHolesPtrIteratormust be a model of OutputIterator whose value_type is a smart pointer (such as boost::shared_ptr) whose element_type is a model of GeneralPolygonWithHoles_2.
Precondition
The input polygons must be simple.
The set of input polygons are unique and interior disjoint. That is, given distinct polygons P and Q, there are vertices of P which are not on the boundary of Q and are all on the bounded or unbounded side of Q (but not both).
Returns
true if no error was encountered, and false otherwise.
See also
create_exterior_straight_skeleton_2()
CGAL::Straight_skeleton_builder_2<Traits,Ss,Visitor>

◆ compute_outer_frame_margin()

template<class InputIterator , class Traits >
boost::optional< typename Traits::FT > CGAL::compute_outer_frame_margin ( InputIterator  first,
InputIterator  beyond,
typename Traits::FT  offset,
const Traits &  traits = Default_traits 
)

#include <CGAL/compute_outer_frame_margin.h>

computes the separation required between a polygon and the outer frame used to obtain an exterior skeleton suitable for the computation of outer offset polygons at a given distance.

Given a non-degenerate strictly-simple 2D polygon whose vertices are passed in the range [first,beyond), calculates the largest euclidean distance d between each input vertex and its corresponding offset vertex at a distance offset.

If such a distance can be approximately computed, returns an optional<FT> with the value d + (offset * 1.05). If the distance cannot be computed, not even approximately, due to overflow for instance, returns an empty optional<FT> (an absent result).

This result is the required separation between the input polygon and the rectangular frame used to construct an exterior offset contour at distance offset (which is done by placing the polygon as a hole of that frame).

Such a separation must be computed in this way because if the frame is too close to the polygon, the inward offset contour from the frame could collide with the outward offset contour of the polygon, resulting in a merged contour offset instead of two contour offsets, one of them corresponding to the frame.

Simply using 2*offset as the separation is incorrect since offset is the distance between an offset line and its original, not between an offset vertex and its original. The later, which is calculated by this function and needed to place the frame sufficiently away from the polygon, can be thousands of times larger than offset.

If the result is absent, any attempt to construct an exterior offset polygon at distance offset will fail. This will occur whenever the polygon has a vertex with an internal angle approaching 0 (because the offset vertex of a vertex whose internal angle equals 0 is at infinity).

The default traits class Default_traits is an instance of the class Polygon_offset_builder_traits_2<Kernel> parameterized on the kernel in which the type InputIterator::value_type is defined.

Template Parameters
Traitsmust be a model for PolygonOffsetBuilderTraits_2.
InputIteratormust be a model of InputIterator with value_type equivalent to Traits::Point_2.
Precondition
offset > 0.
The range [first,beyond) contains the vertices of a non-degenerate strictly-simple 2D polygon.
See also
PolygonOffsetBuilderTraits_2
CGAL::Polygon_offset_builder_traits_2<K>
Examples:
Straight_skeleton_2/Low_level_API.cpp.

◆ convert_straight_skeleton_2()

template<class Target_skeleton , class Source_skeleton , class Items_converter >
boost::shared_ptr<Target_skeleton> CGAL::convert_straight_skeleton_2 ( Source_skeleton const &  s,
Items_converted const &  ic = Items_converter() 
)

#include <CGAL/Straight_skeleton_converter_2.h>

returns a new straight skeleton data structure with the same combinatorial and geometric data as s using the items converter ic to convert the geometric embedding to the types of the target skeleton.

Template Parameters
Target_skeletonmust be a model of StraightSkeleton_2
Source_skeletonmust be a model of StraightSkeleton_2
Items_convertermust be a model of StraightSkeletonItemsConverter_2
See also
CGAL::Straight_skeleton_items_converter_2<SrcSs,TgtSs,NTCV>
CGAL::Straight_skeleton_converter_2<SrcSs,TgtSs,ItemsCV>

◆ create_exterior_skeleton_and_offset_polygons_2()

template<class OfKPolygon , class FT , class InKPolygon , class OfK , class SsK >
std::vector< boost::shared_ptr<OfKPolygon> > CGAL::create_exterior_skeleton_and_offset_polygons_2 ( FT  offset,
const InKPolygon &  poly,
OfK  ofk = Exact_predicates_inexact_constructions_kernel,
SsK  ssk = Exact_predicates_inexact_constructions_kernel 
)

#include <CGAL/create_offset_polygons_2.h>

returns a container with all the outer offset polygons at distance offset of the 2D polygon poly.

A temporary straight skeleton is constructed in the limited exterior of the input polygon to obtain the offsets. The construction of this skeleton is the most expensive operation, therefore, to construct offsets at more than one single distance, use the separate functions create_exterior_straight_skeleton_2() and create_offset_polygons_2() instead. The exterior skeleton is limited by an outer rectangular frame placed at a margin sufficiently large to allow the offset polygons to be constructed.

Template Parameters
OfKmust be a model of Kernel. It is used to instantiate Polygon_offset_builder_traits_2<OfK> for constructing the offset polygons.
SsKmust be a model of Kernel. It is used to instantiate Straight_skeleton_builder_traits_2<SsK> for constructing the straight skeleton.
FTmust be a model of FieldNumberType convertible to OfK::FT and SsK::FT.
InKPolygonmust be a model of SequenceContainer with value type InK::Point_2 (e.g. Polygon_2<InK>) or a model of GeneralPolygonWithHoles_2 (e.g. Polygon_with_holes_2<InK>).
OfKPolygonis a polygon without holes type determined from OfK and InKPolygon, see Section Polygon Return Type.
Note
If SsK != OfK the constructed straight skeleton is converted to Straight_skeleton_2<OfK>.
See also
create_interior_skeleton_and_offset_polygons_2()
create_exterior_skeleton_and_offset_polygons_with_holes_2()
Polygon_offset_builder_2<Ss,Traits,Container>
Examples:
Straight_skeleton_2/Create_skeleton_and_offset_polygons_2.cpp.

◆ create_exterior_skeleton_and_offset_polygons_with_holes_2()

template<class OfKPolygon , class FT , class InKPolygon , class OfK , class SsK >
std::vector<boost::shared_ptr<OfKPolygon> > CGAL::create_exterior_skeleton_and_offset_polygons_with_holes_2 ( FT  offset,
const InKPolygon &  poly_with_holes,
OfK  ofk = Exact_predicates_inexact_constructions_kernel,
SsK  ssk = Exact_predicates_inexact_constructions_kernel 
)

#include <CGAL/create_offset_polygons_from_polygon_with_holes_2.h>

returns a container with all the outer offset polygons with holes at distance offset of the 2D polygon poly_with_holes.

This is equivalent to arrange_offset_polygons_2(create_exterior_skeleton_and_offset_polygons_2(offset, poly_with_holes, ofk, ssk)).

Template Parameters
OfKmust be a model of Kernel. It is used to instantiate Polygon_offset_builder_traits_2<OfK> for constructing the offset polygons.
SsKmust be a model of Kernel. It is used to instantiate Straight_skeleton_builder_traits_2<SsK> for constructing the straight skeleton.
FTmust be a model of FieldNumberType convertible to OfK::FT and SsK::FT.
InKPolygonmust be a model of SequenceContainer with value type InK::Point_2 (e.g. Polygon_2<InK>) or a model of GeneralPolygonWithHoles_2 (e.g. Polygon_with_holes_2<InK>).
OfKPolygonis a polygon without holes type determined by OfK and InKPolygon, see Section Polygon Return Type.
Note
If SsK != OfK the constructed straight skeleton is converted to Straight_skeleton_2<OfK>.
See also
create_exterior_skeleton_and_offset_polygons_2()
create_interior_skeleton_and_offset_polygons_with_holes_2()
Polygon_offset_builder_2<Ss,Traits,Container>

◆ create_interior_skeleton_and_offset_polygons_2() [1/2]

template<class OfKPolygon , class FT , class InKPolygon , class HoleIterator , class OfK , class SsK >
std::vector< boost::shared_ptr<OfKPolygon> > CGAL::create_interior_skeleton_and_offset_polygons_2 ( FT  offset,
const InKPolygon &  outer_boundary,
HoleIterator  holes_begin,
HoleIterator  holes_end,
OfK  ofk = CGAL::Exact_predicates_inexact_constructions_kernel,
SsK  ssk = CGAL::Exact_predicates_inexact_constructions_kernel 
)

#include <CGAL/create_offset_polygons_2.h>

returns a container with all the inner offset polygons at distance offset of the 2D polygon with holes whose outer boundary is outer_boundary and its holes are given by [holes_begin,holes_end).

A temporary straight skeleton is constructed in the interior of the input polygon to obtain the offsets. The construction of this skeleton is the most expensive operation, therefore, to construct offsets at more than one single distance, use the separate functions create_interior_straight_skeleton_2() and create_offset_polygons_2() instead.

Template Parameters
OfKmust be a model of Kernel. It is used to instantiate Polygon_offset_builder_traits_2<OfK> for constructing the offset polygons.
SsKmust be a model of Kernel. It is used to instantiate Straight_skeleton_builder_traits_2<SsK> for constructing the straight skeleton.
FTmust be a model of FieldNumberType convertible to OfK::FT and SsK::FT.
HoleIteratormust be a model of InputIterator with value type being a model of ConstRange with value type SsK::Point_2.
InKPolygonmust be a model of SequenceContainer with value type InK::Point_2 (e.g. Polygon_2<InK>).
OfKPolygonis a polygon without holes type determined from OfK and InKPolygon, see Section Polygon Return Type.
Note
If SsK != OfK the constructed straight skeleton is converted to Straight_skeleton_2<OfK>.
See also
create_exterior_skeleton_and_offset_polygons_2()
create_interior_skeleton_and_offset_polygons_with_holes_2()
Polygon_offset_builder_2<Ss,Traits,Container>
Examples:
Straight_skeleton_2/Create_saop_from_polygon_with_holes_2.cpp, and Straight_skeleton_2/Create_skeleton_and_offset_polygons_2.cpp.

◆ create_interior_skeleton_and_offset_polygons_2() [2/2]

template<class OfKPolygon , class FT , class InKPolygon , class OfK , class SsK >
std::vector< boost::shared_ptr<OfKPolygon> > CGAL::create_interior_skeleton_and_offset_polygons_2 ( FT  offset,
const InKPolygon &  poly,
OfK  ofk = CGAL::Exact_predicates_inexact_constructions_kernel,
SsK  ssk = CGAL::Exact_predicates_inexact_constructions_kernel 
)

#include <CGAL/create_offset_polygons_2.h>

returns a container with all the inner offset polygons at distance offset of the 2D polygon poly.

A temporary straight skeleton is constructed in the interior of the input polygon to obtain the offsets. The construction of this skeleton is the most expensive operation, therefore, to construct offsets at more than one single distance, use the separate functions create_interior_straight_skeleton_2() and create_offset_polygons_2() instead.

Template Parameters
OfKmust be a model of Kernel. It is used to instantiate Polygon_offset_builder_traits_2<OfK> for constructing the offset polygons.
SsKmust be a model of Kernel. It is used to instantiate Straight_skeleton_builder_traits_2<SsK> for constructing the straight skeleton.
FTmust be a model of FieldNumberType convertible to OfK::FT and SsK::FT.
InKPolygonmust be a model of SequenceContainer with value type InK::Point_2 (e.g. Polygon_2<InK>) or a model of GeneralPolygonWithHoles_2 (e.g. Polygon_with_holes_2<InK>).
OfKPolygonis a polygon without holes type determined by OfK and InKPolygon, see Section Polygon Return Type.
Note
If SsK != OfK the constructed straight skeleton is converted to Straight_skeleton_2<OfK>.
See also
create_exterior_skeleton_and_offset_polygons_2()
create_interior_skeleton_and_offset_polygons_with_holes_2()
Polygon_offset_builder_2<Ss,Traits,Container>

◆ create_interior_skeleton_and_offset_polygons_with_holes_2()

template<class OfKPolygon , class FT , class InKPolygon , class OfK , class SsK >
std::vector< boost::shared_ptr< OfKPolygon > > CGAL::create_interior_skeleton_and_offset_polygons_with_holes_2 ( FT  offset,
const InKPolygon &  poly_with_holes,
OfK  ofk = CGAL::Exact_predicates_inexact_constructions_kernel,
SsK  ssk = CGAL::Exact_predicates_inexact_constructions_kernel 
)

#include <CGAL/create_offset_polygons_from_polygon_with_holes_2.h>

returns a container with all the inner offset polygons with holes at distance offset of the 2D polygon with holes poly_with_holes.

This is equivalent to arrange_offset_polygons_2(create_interior_skeleton_and_offset_polygons_2(offset, poly_with_holes, ofk, ssk)).

Template Parameters
OfKmust be a model of Kernel. It is used to instantiate Polygon_offset_builder_traits_2<OfK> for constructing the offset polygons.
SsKmust be a model of Kernel. It is used to instantiate Straight_skeleton_builder_traits_2<SsK> for constructing the straight skeleton.
FTmust be a model of FieldNumberType convertible to OfK::FT and SsK::FT.
InKPolygonmust be a model of SequenceContainer with value type InK::Point_2 (e.g. Polygon_2<InK>) or a model of GeneralPolygonWithHoles_2 (e.g. Polygon_with_holes_2<InK>).
OfKPolygonis a polygon without holes type determined by OfK and InKPolygon, see Section Polygon Return Type.
Note
If SsK != OfK the constructed straight skeleton is converted to Straight_skeleton_2<OfK>.
See also
create_interior_skeleton_and_offset_polygons_2()
create_exterior_skeleton_and_offset_polygons_with_holes_2()
Polygon_offset_builder_2<Ss,Traits,Container>
Examples:
Straight_skeleton_2/Create_skeleton_and_offset_polygons_with_holes_2.cpp, and Straight_skeleton_2/Show_offset_polygon.cpp.

◆ create_offset_polygons_2()

template<class OfKPolygon , class FT , class StraightSkeleton , class OfK >
std::vector< boost::shared_ptr<OfKPolygon> > CGAL::create_offset_polygons_2 ( FT  offset,
const StraightSkeleton &  s,
OfK  k = Exact_predicates_inexact_constructions_kernel 
)

#include <CGAL/create_offset_polygons_2.h>

returns a container with the offset polygons at distance offset obtained from the straight skeleton s.

If s is the inner skeleton of a polygon with holes, the offset polygons will be generated in its interior. If s is the outer skeleton of a polygon with holes, the offset polygons will be generated in its exterior.

Template Parameters
OfKmust be a model of Kernel. It is used to instantiate Polygon_offset_builder_traits_2<OfK> for constructing the offset polygons.
FTmust be a model of FieldNumberType convertible to OfK::FT.
StraightSkeletonis Straight_skeleton_2<SsK>.
OfKPolygonis a polygon without holes type determined from OfK, see Section Polygon Return Type.
Note
If SsK != OfK the constructed straight skeleton is converted to Straight_skeleton_2<OfK>.
See also
create_interior_straight_skeleton_2()
create_exterior_straight_skeleton_2()
create_interior_skeleton_and_offset_polygons_2()
create_exterior_skeleton_and_offset_polygons_2()
Polygon_offset_builder_2<Ss,Traits,Container>