DelaBella
2D Exact Delaunay triangulation
-
Bunch of credits must go to David for inventing such beautiful algorithm (Newton Apple Wrapper):
-
It is pretty well described in this paper:
-
Currently DelaBella makes use of adaptive-exact predicates by William C. Lenthe
What you can do with DelaBella?
-
Delaunay triangulations
-
Voronoi diagrams
-
Constrained Delaunay triangulations
-
Interior / exterior detection based on constraint edges
Minimalistic DelaBella usage:
#include "delabella.h"
// ...
// somewhere in your code ...
int POINTS = 1000000;
typedef double MyCoord;
struct MyPoint
{
MyCoord x;
MyCoord y;
// ...
};
MyPoint* cloud = new MyPoint[POINTS];
srand(36341);
// gen some random input
for (int i = 0; i < POINTS; i++)
{
cloud[i].x = rand();
cloud[i].y = rand();
}
IDelaBella2<MyCoord>* idb = IDelaBella2<MyCoord>::Create();
int verts = idb->Triangulate(POINTS, &cloud->x, &cloud->y, sizeof(MyPoint));
// if positive, all ok
if (verts>0)
{
int tris = idb->GetNumPolygons();
const IDelaBella2<MyCoord>::Simplex* dela = idb->GetFirstDelaunaySimplex();
for (int i = 0; i<tris; i++)
{
// do something with dela triangle
// ...
dela = dela->next;
}
}
else
{
// no points given or all points are colinear
// make emergency call ...
}
delete[] cloud;
idb->Destroy();
// ...
On the go progress information for all lengthy functions
Benchmarks
For more tests and informations please see Benchmarks