Giter Site home page Giter Site logo

delabella's Introduction

DelaBella

2D Exact Delaunay triangulation

delabella

What you can do with DelaBella?

  • Delaunay triangulations

    delaunay

  • Voronoi diagrams

    voronoi

  • Constrained Delaunay triangulations

    constraints

  • Interior / exterior detection based on constraint edges

    floodfill

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

terminal

Benchmarks

Benchmarks

For more tests and informations please see Benchmarks

delabella's People

Contributors

cschreib avatar msokalski avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

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.

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.

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.

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.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.