[solved] Unpredictable error triangulating a polygon

[kbmonkey]

I hope someone can help me.

I have some code that draws a graph, it gives an error when I call love.math.triangulate. I have boiled the code down to this contrived example for demonstration purposes:

Code: Select all

function love.load()

    vertices = {
        0,              138,
        20,             138,
        41,             144,
        62,             162,
        82,             181,
        103,            181,
        124,            191,
        --144,            192,      -- THINGS START GOING WRONG HERE :(
        --165,            195,
        --186,            196
        }

    triangles = love.math.triangulate ( vertices )
    
end

function love.draw()
    
    love.graphics.setLineJoin("none")
    
	for triNo, triangle in ipairs ( triangles ) do
		love.graphics.polygon ( "fill", triangle )
	end
    
end

function love.keypressed()
    love.event.quit()
end

The error appears when I uncomment the line noted in the code. I am scratching my head on this one folks

[grump]

The outline of your polygon (including the commented vertices) looks like this:

I don't know what algorithm triangulate uses, but it probably fails because it considers this an invalid polygon. Add another point and it works:

Code: Select all

    vertices = {
        0,              138,
        20,             138,
        41,             144,
        62,             162,
        82,             181,
        103,            181,
        124,            191,
        144,            192,
        165,            195,
        186,            196,
        200,            400, -- added
        }

[vrld]

From love.math.triangulate:

Decomposes a simple convex or concave polygon into triangles.

[...]

table polygon
Polygon to triangulate. Must not intersect itself.

A simple polygon is one that does not intersect itself and has no holes.

I don't know what algorithm triangulate uses

Kong's triangulation. The result is not necessarily optimal with regard to the shape of the triangles (they may have very acute angles), but the algorithm is fast and easier to implement than alternatives (like decomposition into monotone polygons).

[kbmonkey]

Thanks grump and vrld, I have it working. The trick is to ensure the first and last points are on the extremities of the polygon. Your help was invaluable, cheers.