[solved] Unpredictable error triangulating a polygon

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
User avatar
kbmonkey
Party member
Posts: 127
Joined: Tue Sep 01, 2015 12:19 pm

[solved] Unpredictable error triangulating a polygon

Post by kbmonkey » Thu Nov 30, 2017 2:50 pm

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 :?
Last edited by kbmonkey on Thu Nov 30, 2017 5:57 pm, edited 1 time in total.

grump
Party member
Posts: 583
Joined: Sat Jul 22, 2017 7:43 pm

Re: Unpredictable error triangulating a polygon

Post by grump » Thu Nov 30, 2017 3:11 pm

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
        }

User avatar
vrld
Party member
Posts: 917
Joined: Sun Apr 04, 2010 9:14 pm
Location: Germany
Contact:

Re: Unpredictable error triangulating a polygon

Post by vrld » Thu Nov 30, 2017 3:27 pm

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).
I have come here to chew bubblegum and kick ass... and I'm all out of bubblegum.

hump | HC | SUIT | moonshine

User avatar
kbmonkey
Party member
Posts: 127
Joined: Tue Sep 01, 2015 12:19 pm

Re: Unpredictable error triangulating a polygon

Post by kbmonkey » Thu Nov 30, 2017 5:36 pm

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

Post Reply

Who is online

Users browsing this forum: No registered users and 10 guests