msokalski/delabella

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

DelaBella

2D Exact Delaunay triangulation

• Bunch of credits must go to David for inventing such beautiful algorithm (Newton Apple Wrapper):

  http://www.s-hull.org/

• It is pretty well described in this paper:

  https://arxiv.org/ftp/arxiv/papers/1602/1602.04707.pdf

• Currently DelaBella makes use of adaptive-exact predicates by William C. Lenthe

  https://github.com/wlenthe/GeometricPredicates

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

delabella's Issues

// wtf? dilithium crystals are fucked.

I have been trying to use this library for a couple of days now but, the application always exits right after "// wtf? dilithium crystals are fucked." when generating a random points. it seems to be working fine but with my own data sets its not.

Amazing work by the way.

data.txt

support build using gcc

Thanks for an interesting library :-)
Currently it does not seem to compile usign gcc, e.g. due to intrin.h missing. Support for gcc would be highly appreciated.

Incorrect result built on dence point set

Hi, the following point set gives triangulation with twisted or absent triangles:

Here is the source point set in XY textual format:
dump.zip

Delabella either hangs or generates incorrect outcomes for circular points on MacOS platform

The following code snippet shows how the input points are generated.

  int POINTS = 100;
  const double radius = 5;
  const double PI = 3.14159265358979323846;

  typedef double MyCoord;

  struct MyPoint {
    MyCoord x;
    MyCoord y;
    // ...
  };

  MyPoint* cloud = new MyPoint[POINTS];

  // gen some points on the circle
  for (int i = 0; i < POINTS; i++) {
    double angle = i * PI / 180.0;
    cloud[i].x = radius * cos(angle);
    cloud[i].y = radius * sin(angle);
  }
 

In case of POINTS = 5, it gives the wrong outcome. In case of POINTS = 100, it hangs.

I have found the root cause is due to unexpected #undef on Macro FP_FAST_FMAF, FP_FAST_FMA and FP_FAST_FMAL by random header file in delabella.cpp on MacOS platform. You may want to add the following #error statements before or after random header to verify the problem.

#ifndef FP_FAST_FMAF
#error  FP_FAST_FMAF should be defined for predicates.h
#endif

Though there is no error on Windows platform, it stops the compilation on MacOS platform if you place them after random header file. Therefore, one possible right solution is to move the following Macro definitions after random header file, e.g. right before delabella.h in delabella.cpp.

#undef FP_FAST_FMAF
#define FP_FAST_FMAF
#undef FP_FAST_FMA
#define FP_FAST_FMA
#undef FP_FAST_FMAL
#define FP_FAST_FMAL

May the author fix this problem?

Thanks,
Haipeng

pr was nullptr.

Here I am again with my stupid questions :D. i have a different data set and it now throws this error.
"pr was nullptr" for line 718 "Vert* pr = entry; "

ps.txt

I have been trying at it for a couple of hours now with no luck.

your help is greatly appreciated.

btw, I really like the library name. It got suck in my head "2D Delaunay triangulation (dela) - super stable (bella!)" it got a rhyme to it.

Read access violation: pr was nullptr.

There was a bug in my code that caused this, it put a lot of points very very close to each other. So, this likely won't happen much in the real world, but it probably shouldn't crash on bad data. Here's the offending line:

https://github.com/msokalski/delabella/blob/master/delabella.cpp#L710

Illegal hardware instruction

It appears that Delabella does not work in Rosetta2 on M1 Macs.

At present, some unrelated issues prevent me from compiling my application as a native aarch64 application for M1 Macs. Instead, I rely on the emulator Rosetta2 to run an X86-64 build on the M1 Mac. This has always worked before.

Now with Delabella, the program crashes on load with 'illegal hardware instruction'.

It appears that Rosetta2 does not support any AVX instructions. I suspect the problem may be the FMA instruction, I will try to build without it and report back. Unfortunately, I seem to recall running into other problems if I built without FMA before...

Infinite loop test case

I'm working on converting my program from Triangle to Delabella. I've run into a few issues -- some are proving tough to isolate. As I am able to capture the cases, I will post them here as issue reports.

First, do you expect any differences on an Apple M1 or M2 processor vs. an Intel/AMD x86-64 processor? I am seeing some different behavior when I switch from my new Mac to my old one.

Also, are there any particular compiler options that are required to get correct results from Delabella?

Here is a simple test program and an input file that will into an infinite loop on my x86-64 machine (MacOS, XCode).

dba_test.txt
dba_test.cpp.txt

No available tag

Hello,

Thanks for your package, I would like to package it for conda, but I would need a tag published.

Would you be able to push a tag on the repo to mark the first release?

Thank you

Crash with cocircular input

With the default configuration, the library hard-crashes with this input:

{-144.00000000000000, -134.29487083643272}
{-144.00000000000000, -137.55508053080453}
{-160.00000000000000, -137.55508053080453}
{-160.00000000000000, -134.29487083643272}

and this one:

{456.00000000000000, -512.00000000000000}
{512.00000000000000, -568.00000000000000}
{512.00000000000000, -648.00000000000000}
{456.00000000000000, -704.00000000000000}
{376.00000000000000, -704.00000000000000}
{320.00000000000000, -648.00000000000000}
{320.00000000000000, -568.00000000000000}
{376.00000000000000, -512.00000000000000}

for some reason it gets to a point where "cache" is nullptr in Prepare.
The message that all points are cocircular is printed before the crash, if that helps.

Polygon with holes

Hi, i need to triangulation polygon with holes, what should i do

error: ‘CLOCK_MONOTONIC’ was not declared in this scope

user@host:~/libs-dev/delabella-build
$ cmake -Wno-dev -G Ninja -DCMAKE_INSTALL_PREFIX=${HOME}/gcc-env -DCMAKE_CXX_COMPILER=g++ -DCMAKE_BUILD_TYPE=Release -DCMAKE_CXX_FLAGS="-march=native -mtune=native" ../delabella
-- The CXX compiler identification is GNU 12.2.1
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Check for working CXX compiler: /home/user/gcc-env/bin/g++ - skipped
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Configuring done
-- Generating done
-- Build files has been written to: /home/user/libs-dev/delabella-build
user@host:~/libs-dev/delabella-build
$ ninja
[1/2] Building CXX object CMakeFiles/delabella.dir/delabella.cpp.o
FAILED: CMakeFiles/delabella.dir/delabella.cpp.o
/home/user/gcc-env/bin/g++  -I/home/user/libs-dev/delabella -march=native -mtune=native -O3 -DNDEBUG -MD -MT CMakeFiles/delabella.dir/delabella.cpp.o -MF CMakeFiles/delabella.dir/delabella.cpp.o.d -o CMakeFiles/delabella.dir/delabella.cpp.o -c /home/user/libs-dev/delabella/delabella.cpp
/home/user/libs-dev/delabella/delabella.cpp: In function ‘uint64_t uSec()’:
/home/user/libs-dev/delabella/delabella.cpp:56:23: error: ‘CLOCK_MONOTONIC’ was not declared in this scope
   56 |         clock_gettime(CLOCK_MONOTONIC, &ts);
      |                       ^~~~~~~~~~~~~~~
/home/user/libs-dev/delabella/delabella.cpp:56:9: error: ‘clock_gettime’ was not declared in this scope
   56 |         clock_gettime(CLOCK_MONOTONIC, &ts);
      |         ^~~~~~~~~~~~~
ninja: build stopped: subcommand failed.