precise voronol cell extraction of free-from planar piecewise c1-continuous closed rational curves

摘要

We present an algorithm for generating Voronoi cells for a set of planar piecewise C-1 - continuous closed rational curves, which is precise up to machine precision. The algorithm starts with the symbolically generated bisectors for pairs of C-1-continuous curve segments (C(t), C-i(r)). The bisecttors are represented implicitly in the tr-parameter space. Then, they are properly trimmed after being split into monotone pieces. The trimming procedure uses the orientation of the original curves as well as their curvature fields, resulting in a set of trimmed-bisector segments represented as implicit curves in a parameter space. A lower-envelope algorithm is then used inthe parameter space of the curve whose Voronoi cell is sought. The lower envelope represents the exact boundary of the voronoi cell. The algorithm also support piecewise C-1-continuous curves and generates the Voronoi cell of such input curves using additional point/curve bisector segments.