Eli Packer, Leo Valque

Snap Rounding is a well known method for converting arbitrary-precision arrangements of segments into a smaller precision representation. This package supports methods to converting into various including fixed-precision or floating-point representation.

Introduced in: CGAL 3.1
Depends on: 2D Arrangements
BibTeX: cgal:p-sr2-26a
License: GPL
Windows Demo: 2D Snap Rounding

Classified Reference Pages

Parameters

Optional parameters of the functions of this package are implemented as Named Parameters. The page Named Parameters describes their usage.

Snap Rounding Functions

Snap Rounding Traits

Modules
	Concepts

Classes
class	CGAL::Hot_pixel_snap_rounding_traits_2< Base_kernel >
	The class `Hot_pixel_snap_rounding_traits_2<Kernel>` is a model of the `HotPixelSnapRoundingTraits_2` concept. More...

struct	CGAL::Double_grid_snap_rounding_traits_2< InputKernel, ExactKernel, BaseTraits >
	The class `Double_grid_snap_rounding_traits_2<InputKernel, ExactKernel, BaseTraits>` is a model of the `VerticalSlabsSnapRoundingTraits_2` concept. More...

struct	CGAL::Float_grid_snap_rounding_traits_2< InputKernel, ExactKernel, BaseTraits >
	The class `Float_grid_snap_rounding_traits_2<InputKernel, ExactKernel, BaseTraits>` is a model of the `VerticalSlabsSnapRoundingTraits_2` concept. More...

struct	CGAL::Integer_grid_snap_rounding_traits_2< InputKernel, ExactKernel, BaseTraits >
	The class `Integer_grid_snap_rounding_traits_2<InputKernel, ExactKernel, BaseTraits>` is a model of the `VerticalSlabsSnapRoundingTraits_2` concept. More...

Functions
template<class SegmentRange , class OutputPolylineIterator , class NamedParameters = parameters::Default_named_parameters>
OutputPolylineIterator	CGAL::hot_pixel_snap_rounding_2 (const SegmentRange &segments, OutputPolylineIterator out, const NamedParameters &np=parameters::default_values())
	subdivides and rounds a range of segments so that they are pairwise disjoint in their interiors.

template<class SegmentRange , class OutputSegmentIterator , class NamedParameters = parameters::Default_named_parameters>
OutputSegmentIterator	CGAL::hot_pixel_snap_rounding_2 (const SegmentRange &segments, OutputSegmentIterator out, const NamedParameters &np=parameters::default_values())
	subdivides and rounds a range of segments so that they are pairwise disjoint in their interiors.

template<class PolygonRange , class OutputPolygonIterator , class NamedParameters = parameters::Default_named_parameters>
OutputPolygonIterator	CGAL::hot_pixel_snap_rounding_2 (PolygonRange &polygons, OutputPolygonIterator out, const NamedParameters &np=parameters::default_values())
	subdivides and rounds a range of polygons so that their boundary segments are pairwise disjoint in their interiors.

template<class Traits , class InputIterator , class OutputContainer >
void	CGAL::snap_rounding_2 (InputIterator begin, InputIterator end, OutputContainer &output_container, typename Traits::NT pixel_size, bool do_isr=true, bool int_output=true, unsigned int number_of_kd_trees=1)

template<class SegmentRange , class OutputPolylineIterator , class NamedParameters = parameters::Default_named_parameters>
OutputPolylineIterator	CGAL::snap_rounding_2 (const SegmentRange &segments, OutputPolylineIterator out, const NamedParameters &np=parameters::default_values())
	subdivides and rounds a range of segments so that they are pairwise disjoint in their interiors.

template<class SegmentRange , class OutputSegmentIterator , class NamedParameters = parameters::Default_named_parameters>
OutputSegmentIterator	CGAL::snap_rounding_2 (const SegmentRange &segments, OutputSegmentIterator out, const NamedParameters &np=parameters::default_values())
	subdivides and rounds a range of segments so that they are pairwise disjoint in their interiors.

template<class PolygonRange , class OutputPolygonIterator , class NamedParameters = parameters::Default_named_parameters>
OutputPolygonIterator	CGAL::snap_rounding_2 (PolygonRange &polygons, OutputPolygonIterator out, const NamedParameters &np=parameters::default_values())
	subdivides and rounds a range of polygons so that their boundary segments are pairwise disjoint in their interiors.

template<class SegmentRange , class OutputPolylineIterator , class NamedParameters = parameters::Default_named_parameters>
OutputPolylineIterator	CGAL::vertical_slabs_snap_rounding_2 (const SegmentRange &segments, OutputPolylineIterator out, const NamedParameters &np=parameters::default_values())
	subdivides and rounds a range of segments so that they are pairwise disjoint in their interiors.

template<class SegmentRange , class OutputSegmentIterator , class NamedParameters = parameters::Default_named_parameters>
OutputSegmentIterator	CGAL::vertical_slabs_snap_rounding_2 (const SegmentRange &segments, OutputSegmentIterator out, const NamedParameters &np=parameters::default_values())
	subdivides and rounds a range of segments so that they are pairwise disjoint in their interiors.

template<class PolygonRange , class OutputPolygonIterator , class NamedParameters = parameters::Default_named_parameters>
OutputPolygonIterator	CGAL::vertical_slabs_snap_rounding_2 (PolygonRange &polygons, OutputPolygonIterator out, const NamedParameters &np=parameters::default_values())
	subdivides and rounds a range of polygons so that their boundary segments are pairwise disjoint in their interiors.

Function Documentation

◆ hot_pixel_snap_rounding_2() [1/3]

template<class SegmentRange , class OutputPolylineIterator , class NamedParameters = parameters::Default_named_parameters>

OutputPolylineIterator CGAL::hot_pixel_snap_rounding_2	(	const SegmentRange &	segments,
		OutputPolylineIterator	out,
		const NamedParameters &	np = `parameters::default_values()`
	)

#include <CGAL/Hot_pixel_snap_rounding_2.h>

subdivides and rounds a range of segments so that they are pairwise disjoint in their interiors.

The output is a range of polylines, where each polyline corresponds to an input segment.

Template Parameters

SegmentRange	a range of whose value type is model of `Kernel::Segment_2`
OutputPolylineIterator	model of OutputIterator holding `Polyline`. `Polyline` must be a type that provides a `push_back(Point_2)` function.
NamedParameters	a sequence of Named Parameters

Parameters

segments	the input segment range
out	the output inserter
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

The size of the pixel. The plane will be tiled with square pixels of that width such that the origin is the center of a pixel. Type: `GT::FT` Default: FT(1.)
determines whether to apply Iterative Snap Rounding, see the user manual for more details. Type: Boolean Default: true
If set to true, the output coordinates are expressed in the integer grid (pixel indices). Otherwise, they are given in the input coordinate system. Type: Boolean Default: true
an instance of a geometric traits class Type: The traits class must respect the concept of `HotPixelSnapRoundingTraits_2` Default: an instance of `CGAL::Hot_pixel_snap_rounding_traits_2`

Examples: Snap_rounding_2/snap_rounding.cpp.

◆ hot_pixel_snap_rounding_2() [2/3]

template<class SegmentRange , class OutputSegmentIterator , class NamedParameters = parameters::Default_named_parameters>

OutputSegmentIterator CGAL::hot_pixel_snap_rounding_2	(	const SegmentRange &	segments,
		OutputSegmentIterator	out,
		const NamedParameters &	np = `parameters::default_values()`
	)

#include <CGAL/Hot_pixel_snap_rounding_2.h>

subdivides and rounds a range of segments so that they are pairwise disjoint in their interiors.

The output is a range of segments.

Template Parameters

SegmentRange	a range whose value type is model of `Kernel::Segment_2`
OutputSegmentIterator	model of OutputIterator holding `Kernel::Segment_2`
NamedParameters	a sequence of Named Parameters

Parameters

segments	the input segment range
out	the output inserter
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

The size of the pixel. The plane will be tiled with square pixels of that width such that the origin is the center of a pixel. Type: `GT::FT` Default: FT(1.)
determines whether to apply Iterative Snap Rounding, see the user manual for more details. Type: Boolean Default: true
If set to true, the output coordinates are expressed in the integer grid (pixel indices). Otherwise, they are given in the input coordinate system. Type: Boolean Default: true
an instance of a geometric traits class Type: The traits class must respect the concept of `HotPixelSnapRoundingTraits_2` Default: an instance of `CGAL::Hot_pixel_snap_rounding_traits_2`

◆ hot_pixel_snap_rounding_2() [3/3]

template<class PolygonRange , class OutputPolygonIterator , class NamedParameters = parameters::Default_named_parameters>

OutputPolygonIterator CGAL::hot_pixel_snap_rounding_2	(	PolygonRange &	polygons,
		OutputPolygonIterator	out,
		const NamedParameters &	np = `parameters::default_values()`
	)

#include <CGAL/Hot_pixel_snap_rounding_2.h>

subdivides and rounds a range of polygons so that their boundary segments are pairwise disjoint in their interiors.

Each polygon in the output are free of self intersections but may present pinched sections or/and common vertices or segments with other polygons.

Template Parameters

PolygonRange	a range of `CGAL::Polygon_2`
OutputPolygonIterator	model of OutputIterator holding `CGAL::Polygon_2`
NamedParameters	a sequence of Named Parameters

Parameters

polygons	the range of input polygons
out	the output inserter
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

The size of the pixel. The plane will be tiled with square pixels of that width such that the origin is the center of a pixel. Type: `GT::FT` Default: FT(1.)
determines whether to apply Iterative Snap Rounding, see the user manual for more details. Type: Boolean Default: true
If set to true, the output coordinates are expressed in the integer grid (pixel indices). Otherwise, they are given in the input coordinate system. Type: Boolean Default: true
an instance of a geometric traits class Type: The traits class must respect the concept of `HotPixelSnapRoundingTraits_2` Default: an instance of `CGAL::Hot_pixel_snap_rounding_traits_2`

Warning: an input convex polygon might no longer be convex after rounding.

◆ snap_rounding_2() [1/4]

template<class SegmentRange , class OutputPolylineIterator , class NamedParameters = parameters::Default_named_parameters>

OutputPolylineIterator CGAL::snap_rounding_2	(	const SegmentRange &	segments,
		OutputPolylineIterator	out,
		const NamedParameters &	np = `parameters::default_values()`
	)

#include <CGAL/Snap_rounding_2.h>

subdivides and rounds a range of segments so that they are pairwise disjoint in their interiors.

The output is a range of polylines, where each polyline corresponds to an input segment.

calls the function CGAL::vertical_slabs_snap_rounding_2() or CGAL::hot_pixel_snap_rounding_2() depending if geom_traits is model of VerticalSlabsSnapRoundingTraits_2 or HotPixelSnapRoundingTraits_2.

Template Parameters

SegmentRange	a range of whose value type is model of `Kernel::Segment_2`
OutputPolylineIterator	model of OutputIterator holding `Polyline`. `Polyline` must be a type that provides a `push_back(Point_2)` function.
NamedParameters	a sequence of Named Parameters

Parameters

segments	the input segment range
out	the output inserter
np	an optional sequence of Named Parameters including the one listed below

Optional Named Parameters

an instance of a geometric traits class
Type: The traits class must respect the concept of VerticalSlabsSnapRoundingTraits_2 or HotPixelSnapRoundingTraits_2
Default: an instance of Double_snap_rounding_traits_2

◆ snap_rounding_2() [2/4]

template<class SegmentRange , class OutputSegmentIterator , class NamedParameters = parameters::Default_named_parameters>

OutputSegmentIterator CGAL::snap_rounding_2	(	const SegmentRange &	segments,
		OutputSegmentIterator	out,
		const NamedParameters &	np = `parameters::default_values()`
	)

#include <CGAL/Snap_rounding_2.h>

subdivides and rounds a range of segments so that they are pairwise disjoint in their interiors.

The output is a range of segments.

calls the function CGAL::vertical_slabs_snap_rounding_2() or CGAL::hot_pixel_snap_rounding_2() depending if the parameter geom_traits is model of VerticalSlabsSnapRoundingTraits_2 or HotPixelSnapRoundingTraits_2.

Template Parameters

SegmentRange	a range whose value type is model of `Kernel::Segment_2`
OutputSegmentIterator	model of OutputIterator holding `Kernel::Segment_2`
NamedParameters	a sequence of Named Parameters

Parameters

segments	the input segment range
out	the output inserter
np	an optional sequence of Named Parameters including the one listed below

Optional Named Parameters

an instance of a geometric traits class
Type: The traits class must respect the concept of VerticalSlabsSnapRoundingTraits_2 or HotPixelSnapRoundingTraits_2
Default: an instance of CGAL::Double_grid_snap_rounding_traits_2

◆ snap_rounding_2() [3/4]

template<class Traits , class InputIterator , class OutputContainer >

void CGAL::snap_rounding_2	(	InputIterator	begin,
		InputIterator	end,
		OutputContainer &	output_container,
		typename Traits::NT	pixel_size,
		bool	do_isr = `true`,
		bool	int_output = `true`,
		unsigned int	number_of_kd_trees = `1`
	)

#include <CGAL/Snap_rounding_2.h>

Deprecated:: use newer API of CGAL::snap_rounding_2() or CGAL::hot_pixel_snap_rounding_2()

Template Parameters

Traits	must be a model of `SnapRoundingTraits_2`.
InputIterator	must be an iterator with value type `Traits::Segment_2`.
OutputContainer	must be a container with a method `push_back(const OutputContainer::value_type& c)`, where `OutputContainer::value_type` must be a container with a method `push_back(const Traits::Point_2& p)`

Parameters

begin,end	The first two parameters denote the iterator range of the input segments.
output_container	is a reference to a container of the output polylines. Since a polyline is composed of a sequence of points, a polyline is a container itself.
do_isr	The fifth parameter determines whether to apply ISR or SR.
pixel_size	The fourth parameter denotes the pixel size `w`. The plane will be tiled with square pixels of width `w` such that the origin is the center of a pixel. `pixel_size` must have a positive value.
int_output	The sixth parameter denotes the output representation. If the value of the sixth parameter is `true` then the centers of pixels constitute the integer grid, and hence the vertices of the output polylines will be integers. For example, the coordinates of the center of the pixel to the right of the pixel containing the origin will be `(1,0)` regardless of the pixel width. If the value of the sixth parameter is `false`, then the centers of hot pixels (and hence the vertices of the output polylines) will bear their original coordinates, which may not necessarily be integers. In the latter case, the coordinates of the center of the pixel to the right of the pixel containing the origin, for example, will be `(w,0)`.
number_of_kd_trees	The seventh parameter is briefly described later on this page; for a detailed description see [3].

Snap Rounding (SR, for short) is a well-known method for converting arbitrary-precision arrangements of segments into a fixed-precision representation [1], [2], [4]. In the study of robust geometric computing, it can be classified as a finite precision approximation technique. Iterated Snap Rounding (ISR, for short) is a modification of SR in which each vertex is at least half-the-width-of-a-pixel away from any non-incident edge [3]. This package supports both methods. Algorithmic details and experimental results are given in [3].

Given a finite collection \( \Sc\) of segments in the plane, the arrangement of \( \Sc\) denoted \( \Ac(\Sc)\) is the subdivision of the plane into vertices, edges, and faces induced by \( \Sc\). A vertex of the arrangement is either a segment endpoint or the intersection of two segments. Given an arrangement of segments whose vertices are represented with arbitrary-precision coordinates, SR proceeds as follows. We tile the plane with a grid of unit squares, pixels, each centered at a point with integer coordinates. A pixel is hot if it contains a vertex of the arrangement. Each vertex of the arrangement is replaced by the center of the hot pixel containing it and each edge \( e\) is replaced by the polygonal chain through the centers of the hot pixels met by \( e\), in the same order as they are met by \( e\).

In a snap-rounded arrangement, the distance between a vertex and a non-incident edge can be extremely small compared with the width of a pixel in the grid used for rounding. ISR is a modification of SR which makes a vertex and a non-incident edge well separated (the distance between each is at least half-the-width-of-a-pixel). However, the guaranteed quality of the approximation in ISR degrades. For more details on ISR see [3].

The traits used here must support (arbitrary-precision) rational number type as this is a basic requirement of SR.

About the Number of kd-Trees

A basic query used in the algorithm is to report the hot pixels of size \( w\) that a certain segment \( s\) intersects. An alternative way to do the same is to query the hot pixels' centers contained in a Minkowski sum of \( s\) with a pixel of width \( w\) centered at the origin; we denote this Minkowski sum by \( M(s)\). Since efficiently implementing this kind of query is difficult, we use an orthogonal range-search structure instead. We query with the bounding box \( B(M(s))\) of \( M(s)\) in a two-dimensional kd-tree which stores the centers of hot pixels. Since \( B(M(s))\) in general is larger than \( M(s)\), we still need to filter out the hot pixels which do not intersect \( s\).

While this approach is easy to implement with CGAL, it may incur considerable overhead since the area of \( B(M(s))\) may be much larger than the area of \( M(s)\), possibly resulting in many redundant hot pixels to filter out. Our heuristic solution, which we describe next, is to use a cluster of kd-trees rather than just one. The cluster includes several kd-trees, each has the plane, and hence the centers of hot pixels, rotated by a different angle in the first quadrant of the plane; for our purpose, a rotation by angles outside this quadrant is symmetric to a rotation by an angle in the first quadrant.

Given a parameter \( c\), the angles of rotation are \( (i - 1) \frac{\pi}{2c}, i=1,\ldots,c\), and we construct a kd-tree corresponding to each of these angles. Then for a query segment \( s\), we choose the kd-tree for which the area of \( B(M(s))\) is the smallest, in order to (potentially) get less hot pixels to filter out. Since constructing many kd-trees may be costly, our algorithm avoids building a kd-tree which it expects to be queried a relatively small number of times (we estimate this number in advance). How many kd-trees should be used? It is difficult to provide a simple answer for that. There are inputs for which the time to build more than one kd-tree is far greater than the time saved by having to filter out less hot pixels (sparse arrangements demonstrate this behavior), and there are inputs which benefit from using several kd-trees. Thus, the user can control the number of kd-trees with the parameter number_of_kd_trees. Typically, but not always, one kd-tree (the default) is sufficient.

Examples: Snap_rounding_2/double_snap_rounding.cpp.

◆ snap_rounding_2() [4/4]

template<class PolygonRange , class OutputPolygonIterator , class NamedParameters = parameters::Default_named_parameters>

OutputPolygonIterator CGAL::snap_rounding_2	(	PolygonRange &	polygons,
		OutputPolygonIterator	out,
		const NamedParameters &	np = `parameters::default_values()`
	)

#include <CGAL/Snap_rounding_2.h>

subdivides and rounds a range of polygons so that their boundary segments are pairwise disjoint in their interiors.

Each polygon in the output are free of self intersections but may present pinched sections or/and common vertices or segments with other polygons.

calls the function CGAL::vertical_slabs_snap_rounding_2() or CGAL::hot_pixel_snap_rounding_2() depending if geom_traits is model of VerticalSlabsSnapRoundingTraits_2 or HotPixelSnapRoundingTraits_2.

Template Parameters

PolygonRange	a range of `CGAL::Polygon_2`
OutputPolygonIterator	model of OutputIterator holding `CGAL::Polygon_2`
NamedParameters	a sequence of Named Parameters

Parameters

polygons	the range of input polygons
out	the output inserter
np	an optional sequence of Named Parameters including the one listed below

Optional Named Parameters

an instance of a geometric traits class
Type: The traits class must respect the concept of VerticalSlabsSnapRoundingTraits_2
Default: an instance of Double_snap_rounding_traits_2

Warning: an input convex polygon might no longer be convex after rounding.

◆ vertical_slabs_snap_rounding_2() [1/3]

template<class SegmentRange , class OutputPolylineIterator , class NamedParameters = parameters::Default_named_parameters>

OutputPolylineIterator CGAL::vertical_slabs_snap_rounding_2	(	const SegmentRange &	segments,
		OutputPolylineIterator	out,
		const NamedParameters &	np = `parameters::default_values()`
	)

#include <CGAL/Vertical_slabs_snap_rounding_2.h>

subdivides and rounds a range of segments so that they are pairwise disjoint in their interiors.

The output is a range of polylines, where each polyline corresponds to an input segment.

Template Parameters

SegmentRange	a range of whose value type is model of `Kernel::Segment_2`
OutputPolylineIterator	model of OutputIterator holding `Polyline`. `Polyline` must be a type that provides a `push_back(Point_2)` function.
NamedParameters	a sequence of Named Parameters

Parameters

segments	the input segment range
out	the output inserter
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

an instance of a geometric traits class
Type: The traits class must respect the concept of VerticalSlabsSnapRoundingTraits_2
Default: an instance of Double_snap_rounding_traits_2

◆ vertical_slabs_snap_rounding_2() [2/3]

template<class SegmentRange , class OutputSegmentIterator , class NamedParameters = parameters::Default_named_parameters>

OutputSegmentIterator CGAL::vertical_slabs_snap_rounding_2	(	const SegmentRange &	segments,
		OutputSegmentIterator	out,
		const NamedParameters &	np = `parameters::default_values()`
	)

#include <CGAL/Vertical_slabs_snap_rounding_2.h>

subdivides and rounds a range of segments so that they are pairwise disjoint in their interiors.

The output is a range of segments.

Template Parameters

SegmentRange	a range whose value type is model of `Kernel::Segment_2`
OutputSegmentIterator	model of OutputIterator holding `Kernel::Segment_2`
NamedParameters	a sequence of Named Parameters

Parameters

segments	the input segment range
out	the output inserter
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

an instance of a geometric traits class
Type: The traits class must respect the concept of VerticalSlabsSnapRoundingTraits_2
Default: an instance of CGAL::Double_grid_snap_rounding_traits_2

◆ vertical_slabs_snap_rounding_2() [3/3]

template<class PolygonRange , class OutputPolygonIterator , class NamedParameters = parameters::Default_named_parameters>

OutputPolygonIterator CGAL::vertical_slabs_snap_rounding_2	(	PolygonRange &	polygons,
		OutputPolygonIterator	out,
		const NamedParameters &	np = `parameters::default_values()`
	)

#include <CGAL/Vertical_slabs_snap_rounding_2.h>

subdivides and rounds a range of polygons so that their boundary segments are pairwise disjoint in their interiors.

Each polygon in the output are free of self intersections but may present pinched sections or/and common vertices or segments with other polygons.

Template Parameters

PolygonRange	a range of `CGAL::Polygon_2`
OutputPolygonIterator	model of OutputIterator holding `CGAL::Polygon_2`
NamedParameters	a sequence of Named Parameters

Parameters

polygons	the range of input polygons
out	the output inserter
np	an optional sequence of Named Parameters among the ones listed below

Optional Named Parameters

an instance of a geometric traits class
Type: The traits class must respect the concept of VerticalSlabsSnapRoundingTraits_2
Default: an instance of Double_snap_rounding_traits_2

Warning: an input convex polygon might no longer be convex after rounding.

Classified Reference Pages

Parameters

Snap Rounding Functions

Snap Rounding Traits

Modules

Classes

Functions

Function Documentation

◆ hot_pixel_snap_rounding_2() [1/3]

◆ hot_pixel_snap_rounding_2() [2/3]

◆ hot_pixel_snap_rounding_2() [3/3]

◆ snap_rounding_2() [1/4]

◆ snap_rounding_2() [2/4]

◆ snap_rounding_2() [3/4]

◆ snap_rounding_2() [4/4]

◆ vertical_slabs_snap_rounding_2() [1/3]

◆ vertical_slabs_snap_rounding_2() [2/3]

◆ vertical_slabs_snap_rounding_2() [3/3]