carrier image

Hexagonal Delaunay Triangulation

Suflner, Gerd and Gunther Greiner

Proceedings, 18th International Meshing Roundtable, Springer-Verlag, pp.519-538, October 25-28 2009


18th International Meshing Roundtable
Salt Lake City, UT, USA.
October 25-28, 2009

RTT AG, Munich, Germany
Computer Graphics Group, University of Erlangen-Nuremberg, Germany

We present a novel and robust algorithm for triangulating point clouds in R2. It is based on a highly adaptive hexagonal subdivision scheme of the input domain. That hexagon mesh has a dual triangular mesh with the following properties:
any angle of any triangle lies in the range between 43.9 degrees and 90degrees,
the aspect ratio of triangles is bound to 1.20787,
the triangulation has the Delaunay property,
the minimum triangle size is bounded by the minimum distance between input points.
The iterative character of the hexagon subdivision allows incremental addition of further input points for selectively refining certain regions. Finally we extend the algorithm to handle planar straight-line graphs (PSLG). Meshes produced by this method are suitable for all kinds of algorithms where numerical stability is affected by triangles with skinny or obtuse angles.

Download Full Paper (PDF Format)

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