delfrrr / delaunator-cpp Goto Github PK

View Code? Open in Web Editor NEW

479.0 22.0 96.0 2.28 MB

A really fast C++ library for Delaunay triangulation of 2D points

License: MIT License

CMake 13.39% C++ 78.82% Shell 5.54% JavaScript 0.95% Makefile 1.29%

computational-geometry algorithm delaunay triangulation 2d cpp mapbox

delaunator-cpp's Introduction

delaunator-cpp

A really fast C++ library for Delaunay triangulation of 2D points.

delaunator-cpp is a C++ port from https://github.com/mapbox/delaunator a JavaScript implementation of very fast 2D Delaunay algorithm.

Features

Probably the fastest C++ open source 2D Delaunay implementation
Example showing triangulation of GeoJson points

Usage

examples/basic.cpp

#include <delaunator.hpp>
#include <cstdio>

int main() {
    /* x0, y0, x1, y1, ... */
    std::vector<double> coords = {-1, 1, 1, 1, 1, -1, -1, -1};

    //triangulation happens here
    delaunator::Delaunator d(coords);

    for(std::size_t i = 0; i < d.triangles.size(); i+=3) {
        printf(
            "Triangle points: [[%f, %f], [%f, %f], [%f, %f]]\n",
            d.coords[2 * d.triangles[i]],        //tx0
            d.coords[2 * d.triangles[i] + 1],    //ty0
            d.coords[2 * d.triangles[i + 1]],    //tx1
            d.coords[2 * d.triangles[i + 1] + 1],//ty1
            d.coords[2 * d.triangles[i + 2]],    //tx2
            d.coords[2 * d.triangles[i + 2] + 1] //ty2
        );
    }
}

See more examples here

Benchmarks

Run on (4 X 2300 MHz CPU s)
2018-09-29 09:27:28
------------------------------------------------------------
Benchmark                     Time           CPU Iterations
------------------------------------------------------------
BM_45K_geojson_nodes         22 ms         22 ms         32
BM_uniform/2000               1 ms          1 ms        982
BM_uniform/100000            63 ms         62 ms          9
BM_uniform/200000           140 ms        140 ms          4
BM_uniform/500000           400 ms        399 ms          2
BM_uniform/1000000          994 ms        993 ms          1

Library is ~10% faster then JS version for 1M uniform points (details)

delaunator-cpp's People

Contributors

Stargazers

Watchers

Forkers

morishuz flippmoke mourner stevenlovegrove liang-god damonsj peterzhousz glancefox xiaohulugo mr-question jarrettsjohnson huzhaoqing jxhhl payechan robotvisionhang nguyenvuducthuy soerendd lopesivan t0mac0 zengdelang sirnate0 jayjeetatgithub jdowens sheikware qianqian121 zhang-zhilong duandongbin000 vb6hobbyst7 zjudzl abostrom courriergui lauraxinzhang actuallyfro eminsight shoejunk storijimmy aidenryan thekobithirdparty esilvia valeriizolotov xuyoji freegliboracle truyenpt gaoshuai youruncleda franklinbf marcus-davi ranhaohr vaibhav-hexa prabindh externalrepositories qlwin andrewyghub navman1501 loumalouomega templeblock tschesky lyf7115 simongervaise utjfritz youaodi marcoseiza italink reubingeorge s-cy zhgzheng tylder wlxklyh raydelto matt-the-bass luoxz-ai ztkboj58623 vicwjb qingliu2018 15831944 ray202205 cartolake attixray gondotcl rcads lamarrr chitalu nick-selsby jackzhousz yanfeng1022 uniwangwang githubjiangly ivashkin-ivan eegkit josephlarralde crazybangsky myusernamee

delaunator-cpp's Issues

just add #include <tuple> to delaunator.hpp

pls just add it(

Unsigned integer overflow detected by AddressSanitizer

when compiling with -fsanitize=address,undefined,integer

$ make test
/home/travis/build/delfrrr/delaunator-cpp/include/delaunator.hpp:412:34: runtime error: unsigned integer overflow: 18446744073709551615 + 2 cannot be represented in type 'unsigned long'

Missing include of tuple

The tuple header has to be included for std::tie in Line 304.

Use struct instead of Delaunator class

remove properties that will not be needed after triangulation
convert private methods to static functions
do not perform triangulation in a constructor (struct method or static function?)

@flippmoke anything else?

Break delaunator.hpp into pieces

Hi,

Is there some reason why the non-inline functions in delaunator.hpp aren't in a source (.cpp) file? The functions aren't inlined, which makes including the header file in more than one source a problem. Would it make sense to split the file apart and also provide a unified file via includes for those who desire it?

Thanks,

`get_hull_area` and `sum` are unused

The two functions: get_hull_area and sum seem to be unused.

Compilation fail under Linux

The following fix is needed to compile under a recent Linux (Fedora 36):

modified   test/main.test.cpp
@@ -1,2 +1,3 @@
 #define CATCH_CONFIG_MAIN
+#define CATCH_CONFIG_NO_POSIX_SIGNALS
 #include <catch.hpp>

Parity with the JS version

@delfrrr happy to discover this port — great work! Just wanted to point out that several fixes that were made in the last week are very important for the algorithm robustness, so should definitely be ported out:

I'd also recommend porting over the tests from the JS version to make sure the edge cases are handled the same way.

LNK2005

delaunator.hpp have not inline fubctions. In class Delaunator.

CMake - [Mason] Failed to download

CMake fails to generate the project as the URL for the mason binaries seems to be no longer valid:

CMake Error at cmake/mason.cmake:118 (message):
  [Mason] Failed to download
  https://mason-binaries.s3.amazonaws.com/linux-/benchmark/1.2.0.tar.gz:
  curl: (22) The requested URL returned error: 403 Forbidden

Steps to reproduce:

Open the repository in CMake
Try to generate project files

may be possible to use use std::execution::par

Hi,
Thanks for the routine, it's crazy fast.
I noticed line 306 can use std::execution::par for a tiny speedup

par shaved a fair amount of time off, though using par_unseq wasn't any better

// sort the points by distance from the seed triangle circumcenter
std::sort(std::execution::par,ids.begin(), ids.end(), compare{ coords, m_center_x, m_center_y });

GenTin Num Points = 1000000, time = 631.198200
GenTin Num Points = 1000000, time = 510.206700 par
GenTin Num Points = 1000000, time = 509.641300 par_unseq

cheers, can close

Triangles orientation are not counter clockwise and differences in code to Mapbox's delaunator

The triangles produced by the code in the master branch seems to be oriented in clockwise order whereas Mapbox's delaunator library advertises the orientation produced by code to be counterclockwise. Since this is a port of the latter, and that the counterclockwise order is more typical, I was just wondering if this is a bug or is it intentional?

For e.g., running the binary compiled from basic.cpp using the test data

/* x0, y0, x1, y1, ... */
std::vector<double> coords = {-1, 1, 1, 1, 1, -1, -1, -1};

produces triangles

Triangle points: [[-1.000000, 1.000000], [1.000000, 1.000000], [1.000000, -1.000000]]
Triangle points: [[1.000000, -1.000000], [-1.000000, -1.000000], [-1.000000, 1.000000]]

The 3 points of each triangle for this case is clearly in a clockwise order.

I compared the code to the JS code in the Mapbox's repository and I noticed 2 key differences:

inline bool orient(
    const double px,
    const double py,
    const double qx,
    const double qy,
    const double rx,
    const double ry) {

    // Current code. This seems to be a bug
    // return (qy - py) * (rx - qx) - (qx - px) * (ry - qy) < 0.0; 

    // orient2dfast from https://github.com/mourner/robust-predicates/blob/master/src/orient2d.js
    // The above library appears to be a port of Prof Jonathan Shewchuk's robust predicate library
    // Also see Prof Shewchuk's page http://www.cs.cmu.edu/~quake/robust.html
    return ((py - ry) * (qx - rx) - (px - rx) * (qy - ry)) < 0.0;
}

Another difference is in the legalize method

            // edge swapped on the other side of the hull (rare); fix the halfedge reference
            if (hbl == INVALID_INDEX) {
                std::size_t e = hull_start;
                do {
                    if (hull_tri[e] == bl) {
                        hull_tri[e] = a;
                        break;
                    }

                    // Current code
                    // e = hull_next[e];

                    // Code in Mapbox's JS library
                    e = hull_prev[e];
                } while (e != hull_start);
            }

However, making the above 2 changes still did not fix the orientation.

Am I missing something? Or is the origin at the top-left corner instead of the bottom-left?

Identify a certain triangle

Hello,
If I have a large number of triangles and want to find which triangle encapsulates a certain point. What is the best method to do that ?

eg. I triangulated a domain ❌0-1, y:0-1 and want to find which triangle that enclose the point 0.1, 0.1. Are there routines sin delaunator to do that efficiently ?

Backports distance caching optimisation

mapbox/delaunator#33

Infinite loop with some input coordinates

#include <delaunator.hpp>

int main() {
    std::vector<double> coords = {
        0,
        0,
        1022,
        0,
        0,
        1024,
        1022,
        1024,
        387,
        403,
        387.4791259765625,
        403.1723327636719,
        388.0328369140625,
        403.0395812988281,
        388.6558227539063,
        402.6470947265625,
        389.3426818847656,
        402.0401611328125,
        390.0880126953125,
        401.2640380859375,
        390.886474609375,
        400.364013671875,
        391.732666015625,
        399.3855590820313,
        392.6212463378906,
        398.3738403320313,
        393.5468139648438,
        397.3742065429688,
        394.5039978027344,
        396.4319763183594,
        395.4874267578125,
        395.5924987792969,
        396.49169921875,
        394.9010620117188,
        397.511474609375,
        394.4029235839844,
        398.5413818359375,
        394.1434936523438,
        399.5759887695313,
        394.1680297851563,
        400.6099853515625,
        394.5217895507813,
        401.637939453125,
        395.2501525878906,
        402.6545104980469,
        396.3984680175781,
        403.6543273925781,
        398.0119323730469,
        404.6320190429688,
        400.135986328125,
        405.5821533203125,
        402.8158569335938,
        406.4994201660156,
        406.096923828125,
        407.3783569335938,
        410.0243835449219,
        408.2136840820313,
        414.6436462402344,
        409,
        420,
        409.5401611328125,
        426.6988525390625,
        409.6764526367188,
        435.189453125,
        409.4627380371094,
        445.2825622558594,
        408.95263671875,
        456.7891540527344,
        408.2000122070313,
        469.52001953125,
        407.2585754394531,
        483.2860717773438,
        406.1820678710938,
        497.8982543945313,
        405.0243225097656,
        513.1673583984375,
        403.8389892578125,
        528.9043579101563,
        402.6799926757813,
        544.9199829101563,
        401.6009521484375,
        561.0253295898438,
        400.6557006835938,
        577.031005859375,
        399.8979187011719,
        592.7481689453125,
        399.3814392089844,
        607.9874267578125,
        399.1600036621094,
        622.5599975585938,
        399.287353515625,
        636.2764892578125,
        399.8172912597656,
        648.9478759765625,
        400.8034973144531,
        660.385009765625,
        402.2998352050781,
        670.398681640625,
        404.3600158691406,
        678.7999267578125,
        407.0377502441406,
        685.399658203125,
        410.3868713378906,
        690.0086669921875,
        414.4611206054688,
        692.437744140625,
        419.3142700195313,
        692.4979248046875,
        425,
        690,
        431.9559326171875,
        684.6681518554688,
        440.4808349609375,
        676.5036010742188,
        450.4205932617188,
        665.7330932617188,
        461.6210327148438,
        652.5830078125,
        473.9280090332031,
        637.280029296875,
        487.1872863769531,
        620.050537109375,
        501.2446594238281,
        601.1212768554688,
        515.946044921875,
        580.71875,
        531.13720703125,
        559.0693969726563,
        546.6640014648438,
        536.4000244140625,
        562.3721923828125,
        512.9368896484375,
        578.1077270507813,
        488.9068603515625,
        593.71630859375,
        464.5363159179688,
        609.0437622070313,
        440.0518798828125,
        623.9359741210938,
        415.6799926757813,
        638.23876953125,
        391.6473388671875,
        651.7979736328125,
        368.1804809570313,
        664.4593505859375,
        345.5059204101563,
        676.0687255859375,
        323.8502502441406,
        686.471923828125,
        303.4400024414063,
        695.514892578125,
        284.5018005371094,
        703.0433959960938,
        267.2620544433594,
        708.9031982421875,
        251.9474792480469,
        712.9401245117188,
        238.7846374511719,
        715,
        228,
        715.1982421875,
        219.0757293701172,
        713.8192749023438,
        211.3032836914063,
        710.9628295898438,
        204.6234283447266,
        706.728515625,
        198.9767456054688,
        701.2160034179688,
        194.3040008544922,
        694.52490234375,
        190.5457916259766,
        686.7549438476563,
        187.642822265625,
        678.0057373046875,
        185.5357360839844,
        668.3768310546875,
        184.1652526855469,
        657.968017578125,
        183.4720001220703,
        646.87890625,
        183.3966674804688,
        635.2090454101563,
        183.8799438476563,
        623.05810546875,
        184.8624572753906,
        610.5260009765625,
        186.2849273681641,
        597.7119140625,
        188.0880126953125,
        584.7160034179688,
        190.2123565673828,
        571.637451171875,
        192.5986633300781,
        558.5762329101563,
        195.1875915527344,
        545.6318359375,
        197.9198150634766,
        532.9039916992188,
        200.7359924316406,
        520.4923095703125,
        203.5768127441406,
        508.4963989257813,
        206.3829650878906,
        497.0158996582031,
        209.0950927734375,
        486.1506042480469,
        211.6538848876953,
        476,
        214,
        466.0330810546875,
        216.533935546875,
        455.6854858398438,
        219.6620178222656,
        445.0069580078125,
        223.33349609375,
        434.0472717285156,
        227.4977416992188,
        422.8559875488281,
        232.10400390625,
        411.4830322265625,
        237.1016387939453,
        399.9779968261719,
        242.43994140625,
        388.3906860351563,
        248.0682067871094,
        376.7706909179688,
        253.9358215332031,
        365.16796875,
        259.9920043945313,
        353.6321105957031,
        266.1860961914063,
        342.2128295898438,
        272.4674682617188,
        330.9599609375,
        278.7853393554688,
        319.923095703125,
        285.0890808105469,
        309.1519775390625,
        291.3280029296875,
        298.6964721679688,
        297.4513854980469,
        288.6061401367188,
        303.4085693359375,
        278.9307861328125,
        309.1488647460938,
        269.7201843261719,
        314.62158203125,
        261.0240173339844,
        319.7760009765625,
        252.8919677734375,
        324.5614929199219,
        245.3738098144531,
        328.9273071289063,
        238.5192718505859,
        332.8228149414063,
        232.3781127929688,
        336.1972351074219,
        227,
        339
    };

    //triangulation happens here
    delaunator::Delaunator d(coords);
}

this gets stuck in delaunator::Delaunator::legalize(unsigned long).
Running with -fsanitize=integer yields some unsigned overflow, maybe that could be a cause ?

orient function robustness issue

I found that line

delaunator-cpp/include/delaunator.hpp

Line 76 in c1521f6

return (qy - py) * (rx - qx) - (qx - px) * (ry - qy) < 0.0;

can cause differences between debug and release mode in some edge cases. In debug mode the result is exactly zero, which means the line evaluates to false, but in release mode the result is a very small negative number.

This can be prevented by using return (qy - py) * (rx - qx) - (qx - px) * (ry - qy) < -std::numeric_limits<double>::epsilon(); instead, which seems to solve the problem in my case (the value is on the order of -1e-21). I am curious to know if this is a good solution in general and I am happy to make a pull request out of it if desired.

For reference: GeodynamicWorldBuilder/WorldBuilder#479

Logic error in bounding rectangle initialization.

std::numeric_limits::min() is used to initialize maximum value variables that should grow to the highest encountered value. It represents the smallest positive normal double, so this value can never grow negative (e. g. for only negative inputs). Use std::numeric_limits::lowest() istead.

Lines 223 and 224 of delaunator.hpp:
double max_x = std::numeric_limits::min();
double max_y = std::numeric_limits::min();

should be:
double max_x = std::numeric_limits::lowest();
double max_y = std::numeric_limits::lowest();

may have some bug if in some rare cases

// edge swapped on the other side of the hull (rare); fix the halfedge reference
if ( hbl == INVALID_INDEX ) {
	std::size_t e = hull_start;
	do {
		if ( hull_tri[ e ] == bl ) {
			hull_tri[ e ] = a;
			break;
		}
		e = hull_next[ e ];

		//	add bug check 20230706 
		if ( e == hull_next[ e ] ) {
			break;
		}
		//	add bug check 20230706 

	} while ( e != hull_start );
}

may has bugs if input points in some rare cases

Doesn't compile with errors in mason_packages

user@host:~/libs-dev/delaunator-cpp-build
$ cmake -Wno-dev -G Ninja -DWERROR=OFF -DCMAKE_INSTALL_PREFIX=${HOME}/gcc-env -DCMAKE_CXX_COMPILER=g++ -DCMAKE_C_COMPILER=gcc -DCMAKE_BUILD_TYPE=RelWithDebInfo -DCMAKE_CXX_FLAGS="-march=native -mtune=native" -DCMAKE_C_FLAGS="-march=native -mtune=native" ../delaunator-cpp
-- The C compiler identification is GNU 12.2.1
-- The CXX compiler identification is GNU 12.2.1
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Check for working C compiler: /somewhere/gcc-env/bin/gcc - skipped
-- Detecting C compile features
-- Detecting C compile features - done
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Check for working CXX compiler: /somewhere/gcc-env/bin/g++ - skipped
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Configuring release build
-- Performing Test CMAKE_HAVE_LIBC_PTHREAD
-- Performing Test CMAKE_HAVE_LIBC_PTHREAD - Success
-- Found Threads: TRUE
-- Configuring done
-- Generating done
-- Build files have been written to: /somewhere/libs-dev/delaunator-cpp-build
user@host:~/libs-dev/delaunator-cpp-build
$ ninja
[8/9] Building CXX object CMakeFiles/unit-tests.dir/test/main.test.cpp.o
FAILED: CMakeFiles/unit-tests.dir/test/main.test.cpp.o
/somewhere/gcc-env/bin/g++  -I/somewhere/libs-dev/delaunator-cpp/include -isystem /somewhere/libs-dev/delaunator-cpp/mason_packages/headers/catch/2.4.0/include -isystem /somewhere/libs-dev/delaunator-cpp/mason_packages/headers/rapidjson/1.1.0/include -isystem /somewhere/libs-dev/delaunator-cpp/mason_packages/linux-x86_64/benchmark/1.2.0/include -march=native -mtune=native -O3 -DNDEBUG -D_GLIBCXX_USE_CXX11_ABI=0 -Wall -Wextra -Wconversion -Wunreachable-code -Wuninitialized -pedantic-errors -Wold-style-cast -Wno-error=unused-variable -Wshadow -Wfloat-equal -Weffc++ -O2 -g -DNDEBUG -std=gnu++14 -MD -MT CMakeFiles/unit-tests.dir/test/main.test.cpp.o -MF CMakeFiles/unit-tests.dir/test/main.test.cpp.o.d -o CMakeFiles/unit-tests.dir/test/main.test.cpp.o -c /somewhere/libs-dev/delaunator-cpp/test/main.test.cpp
In file included from /usr/include/signal.h:328,
                 from /somewhere/libs-dev/delaunator-cpp/mason_packages/headers/catch/2.4.0/include/catch.hpp:5267,
                 from /somewhere/libs-dev/delaunator-cpp/test/main.test.cpp:2:
/somewhere/libs-dev/delaunator-cpp/mason_packages/headers/catch/2.4.0/include/catch.hpp:7860:58: error: call to non-‘constexpr’ function ‘long int sysconf(int)’
 7860 |     constexpr static std::size_t sigStackSize = 32768 >= MINSIGSTKSZ ? 32768 : MINSIGSTKSZ;
      |                                                          ^~~~~~~~~~~
In file included from /usr/include/bits/sigstksz.h:24:
/usr/include/unistd.h:640:17: note: ‘long int sysconf(int)’ declared here
  640 | extern long int sysconf (int __name) __THROW;
      |                 ^~~~~~~
/somewhere/libs-dev/delaunator-cpp/mason_packages/headers/catch/2.4.0/include/catch.hpp:7919:45: error: size of array ‘altStackMem’ is not an integral constant-expression
 7919 |     char FatalConditionHandler::altStackMem[sigStackSize] = {};
      |                                             ^~~~~~~~~~~~
ninja: build stopped: subcommand failed.

Halfedges should be initialized to size_t max value by default

Remove recursion from Delaunator::legalize

data controlled recursions can case stack overflows
cc @cleeus

Comparison with CGAL?

Nice to see this work! it leaves me wondering however if your claim that the code is probably the fastest 2d triangulation tool is actually true.
CGAL has some incredibly fast Delaunay triangulation routines. Maybe worth a comparison?
https://doc.cgal.org/latest/Triangulation_2/index.html

keep in mind random point sets aren’t good to benchmark triangulations.

Construct delaunay network but one point didn't form triangles with other points

Sort is slow on gcc

GCC 7.5+ copies the comparator in the process of sorting. Since we cache distances in a vector in the comparator, we have to copy those distances and it's very slow if the number of points is large.

Is it possible to know the neighbor triangle of each edge in a triangle?

Thank you.

Is able to triangulate polygon with holes ?

Is possible to triangulate polygon with holes ?
( attached image )

This is the 'B' letter from Arial font, for using in the text rendering via OpenGL.

Experimenting with changes to library layout

I am going to experiment with a few layout change of the library for a couple of reasons:

Break code out to seperate methods make algorithm more readable
Change names of variables and methods to make intent more clear
Lower amount of allocations performed during algorithm
Decrease the amount of memory allocated in the heap at any one period and lower overall memory footprint of algorithm
Decrease likelihood of cache misses
Migrate away from uses of indices in some portions of the code with a preference for use of pointers instead.
- Allows for more compiler optimizations
- Makes code more readable by specifying what index actual references into
- Reduces memory overhead
Allow more generic user defined data types via templates (user can define a data structure that suits their use more easily)

You will likely see these as a series of PRs that I will try to break out into concise updates (not all at once) so that it can be well understood why certain changes are being made and the code more easily reviewed.