A Survey of Polygon Offseting Strategies

Fernando Cacciola
May, 2003.

Set-Theoretic Offsetting

According to M. Held [HE91], there is a set-theoretic approach to offsetting which was initially introduced by Persson [Per78], Harenbrock [Har80], Bruckner[Bru82] and Diedenhoven [Die84] as a mean to generate tool-paths for countour parallel pocket machining.
The central idea of all these techniques is to create the offset curve piecewise and then connect the pieces, remove loops and detect holes in order to arrange the final result.
Unfortunately, the post-processing of the pieces is so far from trivial that complex heuristics and ad-hoc procedures are needed.
Furthermore, for most of the published algorithms, specially those for polygon offseting (instead of parametric curve offseting), counter-examples that break the algorithms appear more or less frequently in some real world data.

Structural Offsetting

The inherent problem of set-theoretic approaches is the complexity of the reconstruction of the combinatorial structure of an offset curve. This reconstruction requires tracking the interaction of different parts of the curve, but this tracking is difficult because the algorithms basically operates locally.
In consecuence, the topological changes that should ocurr on the true offset curve are sometimes missed, thus a result is computed but it is locally wrong.

Therefore, alternative methods has been investigated. These methods seek to overcome the problems due to locality using geometric structures which contain the complete combinatorial structure needed for the offseting. These methods are called structural because the offset curves are constructed directly out of geometric structures naturally suited for such task.
One of this approaches, presented in [HE91], uses a Voronoi Diagram (VD) to produce rounded or constant-radius offset curves. VD-based offset curves are strictly parallel to the source curve: each and every point in the offset curve is exactly at the same distance from the source. Thus, a reflex vertex in the source curve generates a circular arc in the offset curve (hence the name rounded)
Another approach has been implicitely described by Aichholzer et. al. in [Ai95]. Their paper presents a novel geometric structure, called a Straight Skeleton (SK), which is uniquely associated with every simple polygon (possibly multiple connected) and which corresponds to the trace of the vertices of all the offset polygons that can be constructed on the inside. The offset curves traced by a Straight Skeleton are polygons, which means that reflex vertices do not generate circular arcs as in the case of VD-based offseting. Therefore, such offseting geometry is usually called mittered, and each offset polygon edge is not at the same distance to the source polygon edges but to the lines supporting such edges.


This document explores some of the details of the straight skeleton approach to polygon offseting; details which in turn expose the inherent limitations of set-theoretic approaches to offsetting.

Offseting, Front Propagation, the Grassfire Transform and the Staright Skeleton.

Consider a Jordan Curve 'P' (such as a polygon) and imagine that every point on the curve is set on fire so that the curve consumes itself until the different fire fronts meet. The trace of the ignited curve, which can be seen as a normal inward shrinking of the curve, is called a Grassfire Transform, and is an instance of the constant-speed Front Propagation problem (see [Ma] for a general description of the front propagation model).
Front propagation problems, and in particular, the constant-speed case, has been investigated mostly in the fields of Image Processing.
Grassfire-like transformations are obtained directly from an image using the Morphological Operations known as Erosion or Dilatation; which are used to shrink or expand the boundary of an image object. Additionally, exaustive boundary shrinking (that is, until the fronts meet) can be performed and the process is known as Skeletonization. In particular, the Skeleton of an image feature can be obtained by means of the Medial Axis Transform (MAT).
All these standard Image Processing operations are described in most image processing textbook, and many internet sites contains online tutorials..
C++ code and some references for some of these image-based operations can be found on: www.magicsoftware.com

An offset curve can be viewed as a snapshot of the contour evolution under the grassfire transform at a given instant: when the transformed countour is at given offset distance from the original. Thus, to understand the kind of combinatorial problems that arise on offseting, it is useful to analyze how curve pieces (edges) evolve during this transform. Whatever the algorithm to be used, it has to know how to handle the topological changes of the curve pieces during the front propagation.

In the sequel, consider the case of a polygon: a jordan curve made of a sequence of connected edges which are straight line segments, joined by common points called vertices.
In the case of the so-called mittered-offset (as traced by a Straight Skeleton), the edges move at constant speed along those lines which bisect two edges, that is, along angular bisectors. Edges expand and/or contract as they move, but they always remain parallel to the source edges (that is, any mittered-offset polygon only contains edges which are parallel to some source polygon edge).
If during the front propagation, edges only expand and/or contract (without reaching length zero), the topology of the polygon is preserved. That is, the offset polygon has the exact same connected set of edges than the source. Only the geometry changes (edges have different lengths now).

Figure 1:
The blue lines are the outward and inward offset polygons corresponding to the red lines
The topology is preserved as only the geometry changes.

 


However, two kind of events might ocurr which do change the topology of the offset polygon; that is, after such events, the offset polygons hsa a different set of connected edges..
An edge might contract until it vanishes, even if it started expanding. This is called an edge event.
After an edge event, the edge no longer appears in the offset polygon.

Figure 2:
This figure shows a sequence of inward offsets (black) of a source convex polygon (red).
The propagation of some edges are highligthed to show edge events.
The edge fronts drawn in green, cyan, blue and yellow collapse at different instants, that is, at different distances from the lines supporting the source edges.
Colser edges collapse first.
After an edge collapses it is no longer contained in the offset polygon.

Right after the very last offset polygon, at the maximum allowed offset distance, all remaining edges collapses. This corresponds the a simultaneous closing edge event. The yellow edge is one of the edges that collpases at the closing event.
Edge events are the result of a coallision between two disjoint edge fronts which oclude the collapsing edge. For example, the green edge collapses after the coallision of the cyan and blue edges.

Thinking of the polygon offseting as a front propagation, events occurr at diferent instants, but thinking geometrically, events, which are topological changes affecting edges, ocurr at a given offset distance from the line supporting the edge. Determining the instant of an event amounts to calculating the distance from the supporting lines of the edges involved where the event ocurrs. Since an edge event is the result of the coallision of two disjoints edges that oclude a third edge; and since edges move along bisectors, edge events are the result of bisector intersections, and the corresponding instant is given by the distance from the intersection point to the lines supporting the two colliding and the collapsing edges (it should be the same for the three egdes).
An initial edge event is the result of the coallision of its inmediately adjacent edges and can be computed by intersecting the left and right bisectors of a single edge. For example, the collapsing of the green edge (in Figure 2) is an initial edge event.
Because each event changes the topology, only initial edge events can be determined a priori with trivial local procedures. The reason is that a given edge which would collide at a given instant might have collapsed before that. Therefore, it is far more efficient to precompute initial edge events and then detect further edge events one at a time in the order of ocurrence, so that new edge events are searched from the updated topology.

In a convex polygon only edge events ocurr. Therefore, convex polygon offseting can be computed incrementally by determining the first edge event (the closer to the source supporting line), then creating the new offset polygon without this edge, and proceeding again detecting the next edge event from the updated polygon. If a given next edge event ocurrs after the requested distance, the final result is constructed by a simple offset of the last updated polygon (but this time without the topolgy reconfiguration).

If the source polygon is non-convex, reflex vertices (with interior angles > PI) induce a propagation of the consecutive edges at the reflex vertex which might collide with another edge front splitting such oposite edge. This is called an split event, and it changes the topology because after the event the split edge branches two disjoint offset polygons which propagate independently.

Figure 3:
This figure shows a sample offseting of a non-convex polygon.
The cyan and blue edges move toghether and eventually collide with the yellow edge.
After the coallision, there are two disjoint polygons propagating.
The split edge (yellow) is contained (partially) in the subsequent offset polygons after the event.

Unfortunately, split events are non-local. The reflex front (the two consecutive edges moving along a bisector emerging from a reflex vertex), might collide and split almost any other edge in the polygon, even those edges which initially do not cross the line describing the trayectory of the reflex front (the reflex bisector). The reason for this is that edges might expand while they propagate, so at a given distance, an expanded edge might get in the way of a reflex front and produce a split event.

The instant of a split event is also determined by the distance from the point where the oposite edge is split to the lines supporting the split edge and the two edges of the reflex front (this distance must be the same for the three edges, as in the case of the edge event).
If for a given non-convex polygon, the instant for the first split event is known, and such instant comes after the required offset distance for the requested offset polygon, the offseting may proceed incrementally as if the polygon were convex, that is, by detecting each edge event at a time and updating the topology for the detection of the next edge event.

Split events ocurr only from the edges at a reflex vertex. For each reflex vertex in the source polygon, it is possible to compute its corresponding split event by performing an exaustive search against all the other edges. For each candidate oposite edge, a candidate split point is computed and the closer split point determines the split event for the reflex front emerging from the reflex.vertex.
The split point search must be performed against all other edges (and considering their supporting lines) because edges which are not initially visible from the reflex vertex might be visible later on becasue of possible edge expansions.

It can be shown that if a reflex vertex produces a split, non of the two subsequent offset polygons contain the offseted projection of such reflex vertex (that is, the two new polygons have convex vertices at the split point). Therefore, all possible split events can be precomputed before any of the offset polygons are constructed (using the exaustive search mentioned above).

However, since events change the topology, a given precomputed split event might never actually ocurr. This is because the candidate oposite edge might not be actually in the way of the reflex wavefront at the precomputed instant, both because of prior edge or split events.
Additionally, precomputed edge events (such as inital edge events) might never ocurr if any split event ocurred before.

Conclusions

As explained in the previous section, the topologial changes that ocurr during the front propagation, which must be reflected in the offset polygon at any given distance, are the result of the coallision of disjoint source edges. This implies that the construction of an offset curve is esentially a combinatorial problem.
Traditional divide-and-conquer or incremental algorithms are bounded to fail because they do not explicitely detect all posible interactions.

For example, two edge fronts from completely unrelated parts of the source polygon might collide producing an edge event thus swepping out a large portion of the source. Incremental algorithms must be able to track the entire sequence of edge events in order to determine the topology of the result. Algorithms resorting only to geometric information (such as intersections between individual offset edges) might include in the result an edge which shouldn't be included, thus outputing a polygon which is defective.

The situation is even more complex when reflex vertices are involved since they might split an edge resulting in multiple offset curves. Furhermore, different reflex vertices might produce multiple splits of the same edge. Again, the correct topology is very hard to construct with geometric information only.

If the input polygon is convex and reflex vertices introduce split events which ocurr before the desired offset distance, almost any non-combinatorial algorithm will fail. Only the algorithm that contructs a Straight Skeleton is completely suited for mittered offseting because the algorithm is specifically tracking all front interactions and therefore implicitely computing a continuous offseting, outputing the traces of the moving vertices during the propagation.

It is possible to reduce (perhaps significantly) the combinatorial complexity of a given input by rounding reflex vertices: the sharper the vertex the deeper the possible coallision with an oposite front. Smooth vertices reduces that chances of significant topological changes which might be missed by set-theoretic algorthims.

Image based offseting is possible. It's running time is a factor of the source polygon size (perimeter and area) and the offset distance, but they always produce correct results.
Although trivial to implement (see the references about morphological operations given at the beggining) they produce only rounded offseting.

Comparison of approaches

Reliability

Only the image-based offseting is truly reliable.
Offseting based on the Straight Skeleton is only unreliable down to the numerical issues which can arise during the SK computation, but once the SK is constructed,
the building of the offset polygon is pretty robust (there are very corner-case numerical issues invoved).
As explained, non-combinatorial algorithms are unreliable in general unless augmented with some of the techniques used by the SK (but hybrid approaches have not been reported as far as I know).

Running time

Because of its non-ombinatorial nature, traditional analitic set-theoretic algorithms are the fastest.

SK-based offseting requires some time to create the SK, but the algorithm presented by Felkel [Fe98] is pretty fast.
However, because of numerical issues, a real implementation must be able to deal with imprecise calculations.
One possibility is to use only fast floating point arithmetic but verify the result and in case of failure try again a number of times after a very small geometric perturbation. Therefore, the effective running time might be significant for some worst-case data.
Additionally, because of numerical issues, the SK construction might fail altogheter unless exact arithmetic is used, which currently runs rather slow for this sort of problems.
However, the author have succeeded to implement a fast SK computation algorithm which has been proven to perform sufficientlty fast with TrueType glyphs.

Notice that any analitical algorithm, specially those performing intersection computations and reconstructing topological information from the intersection points are bounded to problems due to numerical errors, so in this regard the SK algorithm is not particularly more sensible to impresicion than any of the set-theoretic approaches.

Image-based algorithms are free from numerical errors and topological incosistences but are significantly slower than the analitical counerparts. Still, due to its simplicity, they might offer a good solution for certain combinations of input size and required offset distances.

Implementation complexity

The implementation of the staright skeleton algorithm is not much complex than the implementation of most other computational geometric algorithms involving distance and intersection calculations.
The image-based algorithms are rather easy to implement.

References

[HE91] M. Held. "On the Computational Geometry ofPocket Machining", LNCS500, Springer-Verlag,1991

[Per78] H. Persson. "NC Machining of Arbitrarily Shaped Pockets", CAD, 1978

[Har80] D. Harenbrock. "The Connection of CAD and CAM by Means of the Program Package PROREN1/NC". 1980

[Bru82] L.K. Bruckner. "Geometric Algorithms for 21/2D Roughing Process of Scluptured Surfaces" 1982

[Die84] H. Diedenhoven. "Application of CAD Techniques for the Generation of Coallision-free Tool-Paths for NC Machines with Five Axes"

[Ai95] O. Aichholzer. et. al. "A Novel Type of Skeleton for Polygons", 1995.

[Ma] R. Malladi. et. al. "Shape Modeling with Front Propagation: A Level Set Approach"

[Fe98] P. Felke. et. al. "Straight Skeleton Implementation"