Personal tools
You are here: Home Projects In-house Projects Deconstructing Approximate Offsets Constructing Approximate Offsets
« September 2020 »
September
SuMoTuWeThFrSa
12345
6789101112
13141516171819
20212223242526
27282930
Log in


Forgot your password?
 

Constructing Approximate Offsets

We present a new construction of approximate offset polygons whose boundaries consist of straight-line segments and circular arcs, and whose vertex coordinates are rational. The construction time depends on the number of vertices of the input polygonal shape and on the approximation tolerance.

  • For the details on the deconstruction of the approximate offsets please go here.

Abstract

We devised and implemented a novel algorithm for the approximate construction of offset polygons. The exact offset of a polygonal shape whose vertex coordinates are rational, with rational offset radius, can have non-rational vertices. In contrast our new algorithm constructs for given polygonal shape P, offset r, and tolerance ε, an ε-approximation of Offset(P,r) whose vertex-coordinates are rational and that prefers circular arcs over piecewise-linear approximation where the exact offset also shows circular arcs.

The Goals

We give a novel ε-approximation for Offset(P,r) consisting of straight-line segments and circular arcs and denoted as Õ that meets three conditions:

  1. H(Õ, Offset(P,r)) <= ε (where H denotes Symmetric Hausdorff Distance)
  2. The vertices of Õ have rational coordinates (of bounded bitlength), and finally
  3. Õ prefers a circular arc over a piecewise-linear approximation where the exact offset also shows a circular arc.

Goals 1 and 2, namely, producing a guaranteed approximation with rational vertex coordinates are particularly important when the offset polygon is the input to further or cascaded geometric computation. Goal 3 is useful for scenarios like NC milling.

The Algorithm

An offset r of a polygon P is defined as a Minkowski sum with a disk of radius r: P ⊕ D(r). We create a rational-vertex inner approximation of the disk by a polygon K, that is the kgon's vertices lie on the boundary of D(r), and and its edges are within its inner ε-annulus. Notice that P ⊕ K already achieves goals 1 and 2.

However we would like to receive a smother approximation with reduced number of vertices. To that purpose we ensure that slopes of K are unique, that is it is slope-disjoint with P. Therefore it is easy to detect the sequences of K's slopes in the P ⊕ K, and replace them with the corresponding circular arcs (that now do have rational endpoints). Such replacement is not straightforward, because it might not be possible to replace the K-slopes that were truncated (for non-convex P), or because such replacement can cause self-intersections in the resulting contour, or can create non-convex connections between circular arcs and segments of the contour, where the exact offset has smooth connections. We overcome these difficulties and produce rational vertex approximation that meets our goals.

room_example.jpg

The input polygon is depicted in the bold blue. The green polygon represents Minkowski Sum with disk approximation K for ε = 10^-1 r. Cyan circles highlight detected K slopes. Orange circles show chains that can't be replaced by circular arcs due to self-intersection they will cause in the contour.

 

Examples

Cascading example:

cascaded.jpg

The computation of the exact r-ε inset (in orange) by current CGAL implementation (with CORE number types) took 8.908 sec.

The construction of the cascading approximate ε-offset and the following r-inset (in green) with precision δ = 10^-1 ε took only 0.212 sec. (Both constructions are done without the circular arc replacement step)

 

Approximation quality example:

app_offset_compare.jpg

Our approximation (in cyan) compared to the existing implementation (in magenta) of the rational approximate offset in CGAL. The input polygon size is 335, ε = 10^-2 r. The new approximation is smoother due to the nature of the involved algorithms, and in this case (r/ε < n) is computed faster (1.501 sec. vs 2.004 sec.)

 

Document Actions