-
Notifications
You must be signed in to change notification settings - Fork 141
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Conforming/Constrained Delaunay #9
Comments
This would be very cool indeed, but is unfortunately much more difficult to implement. I don't have any plans to tackle this yet. |
This is off topic but I'd appreciate any other links from folks that know more, if you don't mind - I've been working on a list of existing implementations. The implementations I know of are
|
@mdsumner |
this lib by @mikolalysenko performs constrained Delaunay triangulations |
@nicoptere the problem with cdt2d is that it's extremely slow. I've added some benchmarks for it (non-constrained version) in the readme. |
@mourner yes, Mikola mentioned it could run a 100 times faster with a proper refactor :) |
Thank you! I hope Mikola will some day get to implement his idea of a compiled fast robust arithmetic engine for JS. The ideas he described to me are amazing, they're just way above my math/engineering skills to even attempt, and require a huge ton of effort. |
I'd do it if someone would pay me. Gotta eat somehow |
@mdsumner |
Hey Guys, sorry to necro this thread a bit, but we had a need to do something similar, where points supplied inside a larger point group would have the larger point group clipped to that concave boundary. In short it creates a concave boundary around a set of points. Also, it clips holes to a concave boundary and creates a separate triangle/delaunay object for it. It still needs some work, but thought I would throw it up here in case it would help anyone. Edit: Also please let me know if I correctly attributed all of the hard work yall have done! |
If people are still looking for this, I created a library to constrain triangulations from Delaunator: https://github.com/kninnug/constrainautor. It takes a triangulation from Delaunator and a list of edges, and constrains the triangulation to contain those edges. The output is in the same format as Delaunator. |
Shameless plug: https://github.com/brunoimbrizi/triangle-wasm A JavaScript wrapper around Jonathan Shewchuk's Triangle compiled to WebAssembly. It does conforming/constrained triangulation, it supports holes, minimum angles, minimum area and more. |
@brunoimbrizi whoa, this is great! Did you run any benchmarks with this? Very curious to know how fast it performs on bigger polygons (e.g. vs https://github.com/mapbox/earcut) |
@mourner Thanks! I haven't tested it against other libraries, but I assume it would be slower than earcut. I think Triangle is stronger when you need to control the shape and size of the triangles (i.e. for finite element meshing). |
@kninnug I tried out Constrainautor and it's really nice. Thank you! demo page @brunoimbrizi Nice! Even though your wrapper is open source (MIT license), Triangle itself isn't open source, so that's one reason I haven't tried it. |
Conforming or constrained triangulation would be utter-cool. Input can be points, lines and polygons while output edges will not cross existing input edges. Conforming would introduce new points in order to be true delaunay triangles (steiner points) while constrained is not always truely delaunay but doesn't introduce extra points.
Relevant information:
The text was updated successfully, but these errors were encountered: