Documentation question regarding constrained triangulation

[fogti]

At first glance, this library looks like it should be capable to produce something like spade's https://docs.rs/spade/latest/spade/struct.ConstrainedDelaunayTriangulation.html "constrained Delaunay triangulation", but so far, I couldn't figure out how to reproduce this with the integer triangulation routines of this library.

My problem is that I want to triangulate a bunch of shapes into common triangulation without introducing any holes, i.e. I have a bunch of overlapping shapes and anything contained in them should be triangulated, optimally as a Delaunay triangulation (but that's not the critical part, and poses some difficulties by itself because unfortunately IntDelaunay::into_raw isn't publically accessible, and even then, the transformation into a Delaunay triangulation might mess with the constraint edges).

triangulate_with_steiner_points allows one to force the insertion of some points, but it is unclear how one should force the insertion of specific edges.

Downstream application: mikwielgus/anyangle#7

[NailxSharipov]

Both libraries do Delaunay triangulation, but they have different focuses.

iTriangle is primarily designed for polygon triangulation, while Spade focuses on triangulating a set of points with constrained-edge insertion.

Do you want to build a navigation mesh for a group of shapes and preserve the inner points?

The IntTriangulatable trait automatically simplifies(do union) the input shapes using the non-zero fill rule.

use i_triangle::int::triangulatable::IntTriangulatable;

let triangulation = shapes.triangulate();

Delaunay refinement can then be applied with:

use i_triangle::int::triangulatable::IntTriangulatable;

let delaunay = shapes
    .triangulate()
    .into_delaunay();

But you will lose all your inner points.

If you need to preserve the original vertices, collect them and pass them as Steiner points:

let delaunay = shapes
    .triangulate_with_steiner_points(&original_points)
    .into_delaunay();

However, this preserves only the vertices, not the original internal edges between them.

[fogti]

Is there a way to insert new edges between already present vertices/points into a RawIntTriangulation afterwards (which afaik would suffice in this case, when using Steiner points)?

[NailxSharipov]

No there is no way. Is it a wall or some kind of it? Only an inner hole. Probably with current data structure and algorithm it achievable but I am not think about it yet.

[fogti]

I should note that the primary reason why we use i_triangle for this is that i_triangle has proper support for integer triangulations, and spade doesn't.

Yes, it is a wall; or, in the anyangle case, it is a projection of a 3D object (where the third dimension is discrete, rather than continuous, and all edges along this 3rd dimension are axis-aligned with it) into the 2D plane, and the edges of the projected objects should be preserved.

[NailxSharipov]

I asked codex to implement this logic. You can find it here

I don't like it solution. It just inject this edge in ready delaunay triangulation. It's ugly but for one or two edges looks ok.

I would add this to the original triangulation at the beginning as some kind of hole. The original idea of triangulation is that we all convert to linked list and then sweep by it. And all we need it's to add this constraints edges as line hole.

[fogti]

I probably would only need the ability to merge two triangulations where the second triangulation fills the holes in the first one, without any simplification, etc., and repeat that for a collection of triangulations.

i.e. a way to merge a bunch of inner-disjoint triangulations whose boundaries match.

I'm currently pursuing ways to turn a "bag" of potentially overlapping objects into a collection of inner-disjoint ones by cutting out the overlapping parts: mikwielgus/anyangle#17

[fogti]

In anyangle, I solved this problem via mikwielgus/anyangle#32, although it might be a good idea to make this easier to do with utilities upstream (albeit idk which ones specifically would be appropriate).