Skip to content

2D Delaunay triangulation (dela) - super stable (bella!)

License

Notifications You must be signed in to change notification settings

Mr-Question/delabella

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

34 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

delabella

2D Delaunay triangulation (dela) - super stable (bella!)

Example triangulation of signed distance field around some fancy font glyph

Example

delabella usage:

#include "delabella.h"
// ...

	// somewhere in your code ...

	int POINTS = 1000000;

	struct MyPoint
	{
		char something;
		float x;
		int something_else;
		float y;
		float foo[5];
	};

	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();
	}

	IDelaBella* idb = IDelaBella::Create();

	int verts = idb->Triangulate(POINTS, &cloud->x, &cloud->y, sizeof(MyPoint));

	// if positive, all ok 
	if (verts>0)
	{
		int tris = verts / 3;
		const DelaBella_Triangle* dela = idb->GetFirstDelaunayTriangle();
		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();

	// ...

performance comparison:

Output from speedtest.cpp

points QHULL S-HULL S-HULL-3D DELAUNATOR DELABELLA
10 0.023 ms 0.009 ms 0.016 ms 0.004 ms 0.002 ms
25 0.068 ms 0.028 ms 0.033 ms 0.011 ms 0.006 ms
50 0.132 ms 0.065 ms 0.046 ms 0.022 ms 0.013 ms
100 0.256 ms 0.124 ms 0.096 ms 0.043 ms 0.028 ms
250 0.658 ms 0.375 ms 0.267 ms 0.118 ms 0.097 ms
500 1.354 ms 0.691 ms 0.620 ms 0.301 ms 0.181 ms
1,000 3.173 ms 1.442 ms 1.220 ms 0.527 ms 0.384 ms
2,500 8.709 ms 3.864 ms 3.175 ms 1.509 ms 1.191 ms
5,000 17.050 ms 8.891 ms 8.823 ms 3.231 ms 2.857 ms
10,000 34.756 ms 18.308 ms 17.732 ms 6.947 ms 5.957 ms
25,000 110.397 ms 53.015 ms 44.851 ms 19.349 ms 16.812 ms
50,000 215.183 ms 114.530 ms 94.747 ms 42.580 ms 35.093 ms
100,000 432.254 ms 231.915 ms 188.614 ms 85.278 ms 74.180 ms
250,000 1242.280 ms 652.245 ms 510.195 ms 255.369 ms 196.017 ms
500,000 2782.869 ms 1400.072 ms 1090.790 ms 567.055 ms 419.753 ms
1,000,000 5913.905 ms 3127.992 ms 2286.446 ms 1276.912 ms 897.941 ms
2,500,000 16091.611 ms 8820.593 ms 6203.232 ms 3747.699 ms 2405.105 ms
5,000,000 53809.487 ms 19320.767 ms 13289.362 ms 8374.141 ms 5056.733 ms

speedtest results in Log,Log scale

About

2D Delaunay triangulation (dela) - super stable (bella!)

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • C++ 91.0%
  • C 9.0%