carrier image

Implementing Ruppert's Algorithm for Generic Curves in 2D

Barbara M. Anthony and Matthew D. Flatau

Research Notes, 19th International Meshing Roundtable, Springer-Verlag, pp.Research Note, October 3-6 2010


19th International Meshing Roundtable
Chattanooga, Tennessee, USA.
October 3-6, 2010

Southwestern University, Georgetown Texas
Email: fanthonyb,

While quality implementations exist for meshing straight-line inputs, fewer are available for handling curved inputs, even in 2D. Many are based on the well- known Ruppert's algorithm [10] which has led to a large body of research in meshing. In this work, we provide a software package that handles a variety of smooth inputs in 2D, based on a minimal modification of Ruppert's algorithm. Existing software for curved inputs lacks the elegance of Ruppert's original algorithm [1, 3] (and subsequent improvements) or is application-specific [2]. In contrast, we seek to keep the core of our work as similar as possible to Ruppert's algorithm to allow our software to benefit from related research and to be easily updated for additional input curve types. In particular, the di erences in our implementation versus the original are limited to two pre- processing steps in the spirit of [7] and a generalized midpoint calculation.

Download Full Paper (PDF Format)

Contact author(s) or publisher for availability and copyright information on above referenced article