|
CGAL 6.2 - 2D Snap Rounding
|
Loading...
Searching...
No Matches
|
CGAL 6.2 - 2D Snap Rounding
|
Average running times of snap rounding methods
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].
Figure 38.1 An arrangement of segments before (a) and after (b) SR (hot pixels are shaded)
Float Snap Rounding is a variant of Snap Rounding for converting arbitrary-precision arrangements of segment into another representation, typically using floating-point coordinates. Float Snap Rounding provides the same guarantees as standard Snap Rounding. By default, Float Snap Rounding rounds to double preserving all input coordinates. Other representations can be used by supplying a model of FloatSnapRoundingTraits_2.
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, the function snap_rounding_2() 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\). Figure 38.1 demonstrates the results of SR.
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. Figure 38.2 depicts the results of SR and ISR on the same input. Conceptually, the ISR procedure is equivalent to repeated application of SR, namely we apply SR to the original set of segments, then we use the output of SR as input to another round of SR and so on until all the vertices are well separated from non-incident edges. Algorithmically we operate differently, as this repeated application of SR would have resulted in an efficient overall process. The algorithmic details are given in [3].
Our package supports both schemes, implementing the algorithm described in [3]. Although the paper only describes an algorithm for ISR, it is easy to derive an algorithm for SR, by performing only the first rounding level for each segment.
The input to the program is a set \( S\) of \( n\) segments, \( S=\{s_1,\ldots,s_n\}\) and the output is a set \( G\) of \( n\) polylines, with a polyline \( g_i\) for each input segments \( s_i\). An input segment is given by the coordinates of its endpoints. An output polyline is given by the ordered set of vertices \( v_0,\ldots,v_k\) along the polyline. The polyline consists of the segments \( (v_0v_1),\ldots,(v_{k-1}v_k)\).
There are three template parameters: Traits is the underlying geometry, i.e., the number type used and the coordinate representation. InputIterator is the type of the iterators that point to the first and after-the-last elements of the input. Finally, OutputContainer is the type of the output container.
Since the algorithm requires kernel functionalities such as the rounding to the center of a pixel, a special traits class must be provided. The precise description of the requirements is given by the concept SnapRoundingTraits_2. The class Snap_rounding_traits_2 is a model of this concept.
Figure 38.2 An arrangement of segments before (a), after SR (b) and ISR (c) (hot pixels are shaded).
The following example generates an ISR representation of an arrangement of four line segments. In particular it produces a list of points that are the vertices of the resulting polylines in a plane tiled with one-unit square pixels.
Example: Snap_rounding_2/snap_rounding.cpp
The package is supplied with a graphical demo program that opens a window, allows the user to edit segments dynamically, applies a selected snap-rounding procedures, and displays the result onto the same window (see <CGAL_ROOT>/demo/Snap_rounding_2/Snap_rounding_2.cpp).
Given an arrangement of segments whose vertices are represented with arbitrary-precision coordinates, the float_snap_rounding_2() function outputs one polyline for each input segment with rounded coordinates. The function ensures that the resulting polylines do not intersect and provide the same topological guarantee as the Snap Rounding algorithm [5].
The algorithm is illustrated on the figure Figure 38.3 and proceeds as follows. First, the segments are subdivided exactly at their (potential) intersection points. Then the vertices are processed from left to right. Whenever a vertex lies too close to a segment, that segment is subdivided at the \(x\)-coordinate of the vertex. Finally, the vertices are rounded.
Figure 38.3 An arrangement of segments before subdividing the segments (a), after subdividing the segments (b) and after rounding (c).
The function float_snap_rounding_2() outputs the result as a range of polylines, one for each input segment. The functions compute_snapped_subcurves_2() and compute_snapped_polygons_2() perform the same algorithm but provide different input and/or output formats. The function compute_snapped_subcurves_2() outputs the result as a range of segments, whereas compute_snapped_polygons_2() takes a range of polygons as input and outputs a range of polygons.
The following example snaps a non-trivial instance of five segments.
Example: Snap_rounding_2/float_snap_rounding.cpp
We evaluate the different methods on two tests: In the first test, the segment endpoints are chosen uniformly and independantly in the unit box. In the second test, we generate perturbed copies of a given segment. This experiment is repeated several times using different input segments.
First with segments whose endpoints are randomly and independantly chosen in the unit box. Second with perturbated copy of a given segment, we perform this test several times with different input segments. The two pixel sizes for snap rounding are chosen so that the rounding shift is of the same order of magnitude as the rounding induced by using respectively double or float coordinates. The first test is standard but typically exhibits few, if any, rounding issues. The second test is deliberately designed to be difficult, as it produces a large number of rounding issues when rounding is performed naively. In these settings, float snap rounding significantly outperforms standard snap rounding and remains in the same order of magnitude than computing the intersections without snap. The result of our test is resume in the next table:
| Test Case | Computing intersection (Unsafe rounding) | Float snap rounding (double precision) | Float snap rounding (simple precision) | Snap rounding (pixel size \(10^{-15}\) ) | Snap rounding (pixel size \(10^{-7}\)) |
|---|---|---|---|---|---|
| 500 Random Segments | 0.103s | 0.233s | 0.208s | 6.91s | 4.25s |
| 1000 Random Segments | 0.379s | 1.36s | 1.23s | 1m 0s | 53.3s |
| 2000 Random Segments | 1.45s | 4.95s | 5.22s | – | – |
| 4000 Random Segments | 6.15s | 29.2s | 31.5s | – | – |
| 100 Almost identical Segments | 0.016s | 0.025s | 1.37s | 0.452s | 2.00s |
| 150 Almost identical Segments | 0.032s | 0.064 | 5.11s | 1.48s | 7.41s |
| 200 Almost identical Segments | 0.057s | 0.125s | – | 3.48s | – |
| 400 Almost identical Segments | 0.216s | 0.641s | – | 38.5s | – |
The algorithm runs in approximately \(O(n \log n + k)\), where \(n\) is the number of input segments and \(k\) is the number of vertices created during the process. In the worst case, the number of created vertices is \(O(n^3)\), or \(O(n^2)\) if the input segments are free of intersections.
The algorithm uses a traits class that models the concept FloatSnapRoundingTraits_2. By default, the traits class Double_snap_rounding_traits_2, which rounds coordinates to double precision floating point, is used. The package also provides Float_snap_rounding_traits_2, which rounds coordinates to single precision floating point. Other traits classes can be used to round to different representations as long as the rounding operation preserves the order of vertices along the \(x\) and \(y\) directions. See FloatSnapRoundingTraits_2 for more details.
Snap Rounding and Iterative Snap Rounding was introduced by Eli Packer in 2001.
Float Snap Rounding was introduced by Léo Valque in 2026.
1.9.6