Page 1 of 1

[solved] Unpredictable error triangulating a polygon

Posted: Thu Nov 30, 2017 2:50 pm
by 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 :?

Re: Unpredictable error triangulating a polygon

Posted: Thu Nov 30, 2017 3:11 pm
by grump
The outline of your polygon (including the commented vertices) looks like this:
Image
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
        }

Re: Unpredictable error triangulating a polygon

Posted: Thu Nov 30, 2017 3:27 pm
by 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.
grump wrote: Thu Nov 30, 2017 3:11 pm 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).

Re: Unpredictable error triangulating a polygon

Posted: Thu Nov 30, 2017 5:36 pm
by 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. :D