2D Delaunay Triangulation Performance – Example1

Fade is a very fast Delaunay triangulation software, see the diagram below. With the present test code you can compare the performance on your own hardware. Example1 loops over an increasing number of random points and calls timer(“..”) before and after the triangulation to measure the time consumption of the algorithm.

for(int numPoints=100000;numPoints<=1000000;numPoints+=100000)
{
  // Create random points
  cout<<"\n"<<numPoints<<" points: "<<endl;
  std::vector<Point2> vInputPoints;
  generateRandomPoints(	
			numPoints, 	// number of points
			-100,		// range min
			+100,		// range max
			vInputPoints,   // output vector
			0 		// seed value (0 for randomness)
			);

  timer("INSERT"); // Start timer

	// Triangulate
	Fade_2D dt(numPoints);
	dt.insert(vInputPoints);

  timer("INSERT"); // Stop timer
}

1 Million Points on a Core i7 6800K

This Delaunay triangulation benchmark has been run on one core of a desktop computer (Core i7 6800K, Linux x64). One million points (2 million triangles) take 0.42 seconds.

Delaunay triangulation performance:  One million points (2 million triangles) take 0.42 seconds.

Delaunay Triangulation Performance of Fade2D

Huge Datasets – Up to 100 Million Points on a Core i7 6800K

The same machine has been used to test Fade2D with huge datasets. 10 million points take 4.46 seconds while 100 million points take 47.82 seconds: The time consumption behaves well, it grows almost linearly with the number of input points.

Big Delaunay triangulation benchmark: 100 million points take 47 seconds.

Delaunay Triangulation Performance of Fade2D, big benchmark (10-100 million points)

Raspberry PI2 – 1 Million Points on an ARM Cortex A7

Whether it is a fun benchmark or even a very important one: Fade2D has been run on a comparably weak Raspberry PI2. It uses a Broadcom BCM2836 SoC containing a 32-bit ARM Cortex-A7 cpu.

This poor little 3-watt device has fought incredibly brave, it was only 16 times slower than a today’s top desktop computer with a 140-watt TDP. This result encourages us to provide support for further embedded devices. If you have any suggestions feel free to add your comments below.
Raspberry PI Delaunay benchmark
Raspberry PI Delaunay Benchmark: 1 Million points on a weak embedded device

Delaunay Triangulation Performance on a Raspberry PI2

The next article Example2 – Traversing teaches you the important basics you need to access specific elements in a triangulation.

Spread the word. Share this post!

Leave A Reply

Your email address will not be published. Required fields are marked *

*

By continuing to use the site, you agree to the use of cookies. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.

Close