Conforming/Constrained Delaunay

[tomvantilburg]

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:

• http://www.cs.cmu.edu/~quake/triangle.defs.html#conform
• http://www.cs.cmu.edu/~quake/triangle.delaunay.html
• http://lin-ear-th-inking.blogspot.nl/2009/04/delaunay-triangulation-in-jts-111.html

[mourner]

This would be very cool indeed, but is unfortunately much more difficult to implement. I don't have any plans to tackle this yet.

[mdsumner]

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

• Triangle (the quake site above)
• JTS (as above)
• Tinfour https://github.com/gwlucastrig/Tinfour
• CGAL CGAL.org
• Manifold.net (commercial)
• Eonfusion (commercial, defunct)

[MaxGraey]

@mdsumner Poly2Tri: Original: https://github.com/greenm01/poly2tri Js Port: https://github.com/r3mi/poly2tri.js

[nicoptere]

this lib by @mikolalysenko performs constrained Delaunay triangulations https://github.com/mikolalysenko/cdt2d

[mourner]

@nicoptere the problem with cdt2d is that it's extremely slow. I've added some benchmarks for it (non-constrained version) in the readme.

[nicoptere]

@mourner yes, Mikola mentioned it could run a 100 times faster with a proper refactor :) I never tried it on big datasets though, just used it to triangulate the paths of the building from OSM & in my experience, it is robust enough where most (all) other JS libs fail. your work is awesome btw, thank you for your efforts 🙏

[mourner]

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.

[mikolalysenko]

I'd do it if someone would pay me. Gotta eat somehow

[qwilka]

@mdsumner another for the list, TTL from SINTEF in Norway: https://www.sintef.no/projectweb/geometry-toolkits/ttl/ https://github.com/SINTEF-Geometry/TTL

[willmac321]

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. https://www.npmjs.com/package/constrainodelaunato

Edit: Also please let me know if I correctly attributed all of the hard work yall have done!

[kninnug]

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.

[brunoimbrizi]

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.

[mourner]

@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)

[brunoimbrizi]

@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).

[redblobgames]

@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.