delfrrr / delaunator-cpp Goto Github PK
View Code? Open in Web Editor NEWA really fast C++ library for Delaunay triangulation of 2D points
License: MIT License
A really fast C++ library for Delaunay triangulation of 2D points
License: MIT License
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
data controlled recursions can case stack overflows
cc @cleeus
delaunator.hpp have not inline fubctions. In class Delaunator.
@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.
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.
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,
#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 ?
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:
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?
I found that line
delaunator-cpp/include/delaunator.hpp
Line 76 in c1521f6
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
The tuple header has to be included for std::tie in Line 304.
Thank you.
@flippmoke anything else?
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>
keep in mind random point sets aren’t good to benchmark triangulations.
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 ?
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'
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.
pls just add it(
I am going to experiment with a few layout change of the library for a couple of reasons:
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.
// 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
The two functions: get_hull_area
and sum
seem to be unused.
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();
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.