Home

Awesome

Relatively Robust Divide and Conquer 2D Delaunay Construction Algorithm

Copyright 2005-2017 (c) Wael El Oraiby, All rights reserved.

Introduction

This is a library that builds a 2D Delaunay Construction using a divide and conquer algorithm very similar to the one by Guibas and Stolfi.

Given a set of inputs points, the program will output Delaunay faces (not necessarily triangles, as long as the points are circumscribed to a circle).

Contributors

Thanks to:

Configuration and compilation using CMake and Make

$ mkdir build
$ cd build
$ cmake ..
$ make

Usage

The algorithm builds the 2D Delaunay triangulation given a set of points of at least 3 points using:

delaunay2d_t* delaunay2d_from(del_point2d_t *points, unsigned int num_points);

the returned delaunay2d_t structures contains:

You have to release the structure by calling delaunay2d_release.

See the provided example if you want more information. The example requires Qt 5 however.

Triangulated Output

A new feature is the ability to triangulate the output of the delaunay2d function. The function for doing so is:

tri_delaunay2d_t* tri_delaunay2d_from(delaunay2d_t *orig);

This will create a new structure that has the following fields:

Release the tri_delaunay2d_t structure by calling tri_delaunay2d_release.

Robustness

Currently robustness is achieved by using 64 bits precision inputs and computation using 80 bits. It's possible to achieve the maximum fast robustness using __float128 for computation (without using a slow BigFloat library). This however is not supported with ARM.

Historical Note: Previous version of delaunay used the Predicates from Jonathan Richard Shewchuk. The code is however unstable when compiled with gcc with -m32 and run on x64 machines. As such the code was removed.

Examples

random grid vertical and horizontal lines circles

Notes

The implementation is relatively robust (take a look at the pictures above, some of these cases will crash most freely available implementations), in case of input or predicate floating point rounding errors, it will assert. Note that while the robustness is more than enough for most application, there is still room for improvement.

License

The delaunay.c source code is licensed under Affero GPL version 3.0 or later. While I think this license is the best for OSS, you can obtain a more permissive license suitable for closed source programs for a modest fee. You can contact me for that contact me.