tchayen / triangolatte Goto Github PK

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.

I was looking into using this library for a small side project but I am currently running into an error.

This is a reproducible unit test:

func TestTriangulationError(t *testing.T) {
	vertices := []triangolatte.Point{
		{X: 512.00, Y: 30.00},
		{X: 512.00, Y: 145.04},
		{X: 596.96, Y: 145.04},
		{X: 596.96, Y: 85.05},
		{X: 636.96, Y: 85.05},
		{X: 636.96, Y: 30.00},
		{X: 512.00, Y: 30.00},
	}

	_, err := triangolatte.Polygon(vertices)
	if err != nil {
		t.Fatal(err)
	}
}

=== RUN   TestTriangulationError
--- FAIL: TestTriangulationError (0.00s)
    shape_test.go:22: oops
FAIL

Process finished with exit code 1

I have no experience with doing polygon triangulation so maybe I am doing something stupid? What resources would you recommend to learn more about the algorithm in detail?

Please provide a more descriptive and helpful error, i.e. include problematic point index and so on