Ear cutting may terminate too early?

[danieltwagner]

Thank you for creating this helpful library! I have just started playing around with it and may have come across a bug. As I'm just coming to grips with it I would appreciate another set of eyes

Here is a reproducing example:

outer = []triangolatte.Point{
    {0.0, 0.0},
    {-10.0, 0.0},
    {-10.0, -10.0},
    {0.0, -10.0},
}

hole = []triangolatte.Point{
    {-1.8813725490196056, -4.059803921568627},
    {-3.663725490196078, -2.0794117647058803},
    {-2.1784313725490176, -3.465686274509803},
    {-2.0794117647058803, -3.5647058823529405},
}

poly, err := triangolatte.JoinHoles([][]triangolatte.Point{outer, hole})
if err != nil {
    panic(fmt.Sprintf("JoinHoles failed: %s", err))
}

fmt.Println("Poly is", poly)
_, err = triangolatte.Polygon(poly)
if err != nil {
    panic(fmt.Sprintf("Polygon failed: %s", err))
}

The above will fail to triangulate the resulting polygon. In my opinion this is because it terminates too early. This proposed change fixes the example above:

diff --git a/polygon.go b/polygon.go
index 1c3fe48..825813c 100644
--- a/polygon.go
+++ b/polygon.go
@@ -292,7 +292,7 @@ func Polygon(points []Point) ([]float64, error) {

                        ear.Remove()
                        ear = ear.Next
-                       stop = stop.Next
+                       stop = ear
                        continue
                }

With the fix applied it does, however, still fail to triangulate the more complete polygon from which I created the above example. The original polygon I was trying to triangulate is reproduced in this gist

Sadly the original example is quite large and I don't have good insights where it fails. I did find that tripy manages to triangulate the original polygon.

I would appreciate any insights on where things break.

[tchayen]

Hi!

Thanks a lot for reporting this issue. It is quite likely that I made an off by one error there. Would you mind submitting this fix in a PR? (Also very welcome would be adding a test case that verifies this so it won't be accidentally broken in future).

Regarding more complex PR: I am aware that the lib does not cover all possible cases, especially the huge ones. I haven't studied tripy's source code, but for example there's earcut.js (that was also my reference when creating this library) that handles more edge cases but has a lot of specialized code for that. So I guess this is as much as it is doable using this rather concise solution.