CGAL 4.8.2  2D Snap Rounding

Modules  
Concepts  
Classes  
class  CGAL::Snap_rounding_traits_2< Kernel > 
The class Snap_rounding_traits_2<Kernel> is a model of the SnapRoundingTraits_2 concept, and is the only traits class supplied with the package. More...  
Functions  
template<class Traits , class InputIterator , class OutputContainer >  
void  CGAL::snap_rounding_2 (InputIterator begin, InputIterator end, OutputContainer &output_container, typename Traits::FT pixel_size, bool do_isr=true, bool int_output=true, unsigned int number_of_kd_trees=1) 
More...  
void CGAL::snap_rounding_2  (  InputIterator  begin, 
InputIterator  end,  
OutputContainer &  output_container,  
typename Traits::FT  pixel_size,  
bool  do_isr = true , 

bool  int_output = true , 

unsigned int  number_of_kd_trees = 1 

) 
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) 
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 arbitraryprecision arrangements of segments into a fixedprecision 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 halfthewidthofapixel away from any nonincident edge [3]. This package supports both methods. Algorithmic details and experimental results are given in [3].
Given a finite collection \( \S\) of segments in the plane, the arrangement of \( \S\) denoted \( \A(\S)\) is the subdivision of the plane into vertices, edges, and faces induced by \( \S\). 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 arbitraryprecision 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 snaprounded arrangement, the distance between a vertex and a nonincident 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 nonincident edge well separated (the distance between each is at least halfthewidthofapixel). However, the guaranteed quality of the approximation in ISR degrades. For more details on ISR see [3].
The traits used here must support (arbitraryprecision) rational number type as this is a basic requirement of SR.
About the Number of kdTrees
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 rangesearch structure instead. We query with the bounding box \( B(M(s))\) of \( M(s)\) in a twodimensional kdtree 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 kdtrees rather than just one. The cluster includes several kdtrees, 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 kdtree corresponding to each of these angles. Then for a query segment \( s\), we choose the kdtree 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 kdtrees may be costly, our algorithm avoids building a kdtree which it expects to be queried a relatively small number of times (we estimate this number in advance). How many kdtrees 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 kdtree 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 kdtrees. Thus, the user can control the number of kdtrees with the parameter number_of_kd_trees
. Typically, but not always, one kdtree (the default) is sufficient.
#include <CGAL/Snap_rounding_2.h>