Monotone polygon

Algorithm

Discrete mathematics

Visualization

Telecommunications

OpenGL

Computer science

Offset (computer science)

Mathematics

Winding number

Mathematical analysis

Artificial intelligence

Geometry

Combinatorics

Polygon (computer graphics)

Programming language

Simple polygon

Frame (networking)

In this paper we present a simple new algorithm to offset multiple, non-overlapping polygons with arbitrary holes that makes use of winding numbers. Our algorithm constructs an intermediate “raw offset curve” as input to the tessellator routines in the OpenGL Utility library (GLU), which calculates the winding number for each connected region. By construction, the invalid loops of our raw offset curve bound areas with non-positive winding numbers and thus can be removed by using the positive winding rule implemented in the GLU tessellator. The proposed algorithm takes O((n + k)logn) time and O(n + k) space, where n is the number of vertices in the input polygon and k is the number of self-intersections in the raw offset curve. The implementation is extremely simple and reliably produces correct and logically consistent results.

Polygon Offsetting by Computing Winding Numbers