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

[JSeligstein]

I ran into this as well. I was generating a random shape counter-clockwise by accident and ran into infinite loop issues.

Could be nice to add a debug-mode feature that checks polygons at runtime that's turned off in production.

Thanks for the great library.

[lgarczyn]

Or just some "max iteration count" setting

[NailxSharipov]

I'd be happy to help. But I'm very busy this month. I'll be free by the end of January.
To implement a clean solution, I'll need to port the polygon boolean library. And I actually have a plan to rewrite this library, because it's outdated. I wrote it more then 5 years ago, and since thet time I've become more skilled and rethought some things.

But if you have a fast fixes I can apply it.