Infinite loop on triangulation

[lgarczyn]

Hello, thanks for the great library. However even simple attempts give me systematic infinite loops.

                Vector2[] data = new []
                {
                    new Vector2(-1, -1),
                    new Vector2(1, -1),
                    new Vector2(1, 1),
                    new Vector2(-1, 1),
                };

                IntVector[] iPoints = iGeom.Int(data);
                PathLayout pathLayout = new PathLayout(0, data.Length, false);

                PlainShape shape = new(iPoints, new[] {pathLayout}, Allocator.Temp);

                Mesh mesh = shape.DelaunayTriangulate(iGeom);

I feel like some kind of general safety loop counter would help for debugging these cases.

[NailxSharipov]

Hi, that's right. Sad to say but it's nothing I can fix here.

It's because it's not a "valid" shape. In valid shape all outer contours must be a path where all points go in clockwise direction and all holes must be a path where all points go in counter-clockwise direction.

The easy way to check points direction in a path is calculate it's area and see a sign.

This library is not support shape validation. In general it's very complex process.

If you still need a library which can triangulate any shape including not valid and self interesected. I can recommend my other rust triangulation library https://github.com/iShape-Rust/iTriangle

P.S.

Area can be calculated with this function (I hope convert it to float is not a problem)

private static long Area(NativeSlice<IntVector> self) {
    int n = self.Length;
    long sum = 0;
    var p1 = self[n - 1];
    for (int i = 0; i < n; i++) {
        var p2 = self[i];
        long dif_x = p2.x - p1.x;
        long sum_y = p2.y + p1.y;
        sum += dif_x * sum_y;
        p1 = p2;
    }

    return sum >> 1;
}

[lgarczyn]

Hi, that's right. Sad to say but it's nothing I can fix here.

It's because it's not a "valid" shape. In valid shape all outer contours must be a path where all points go in clockwise direction and all holes must be a path where all points go in counter-clockwise direction.

The easy way to check points direction in a path is calculate it's area and see a sign.

This library is not support shape validation. In general it's very complex process.

If you still need a library which can triangulate any shape including not valid and self interesected. I can recommend my other rust triangulation library https://github.com/iShape-Rust/iTriangle

P.S.

Area can be calculated with this function (I hope convert it to float is not a problem)

private static long Area(NativeSlice<IntVector> self) {
    int n = self.Length;
    long sum = 0;
    var p1 = self[n - 1];
    for (int i = 0; i < n; i++) {
        var p2 = self[i];
        long dif_x = p2.x - p1.x;
        long sum_y = p2.y + p1.y;
        sum += dif_x * sum_y;
        p1 = p2;
    }

    return sum >> 1;
}

I've tried both values of PathLayout isClockwise, both go in infinite loops

[NailxSharipov]

Can not reproduce it. Could you give me a little bit more details? Which function is going to infinity loop? Is it Delaunay.Build Is it on x86 or arm processor?

have you tried this correct path?

new Vector2[] { new Vector2(-1, -1), new Vector2(-1, 1), new Vector2(1, 1), new Vector2(1, -1) }