## [solved] Unpredictable error triangulating a polygon

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
kbmonkey
Party member
Posts: 127
Joined: Tue Sep 01, 2015 12:19 pm

### [solved] Unpredictable error triangulating a polygon

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: 620
Joined: Sat Jul 22, 2017 7:43 pm

### Re: Unpredictable error triangulating a polygon

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,
}

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

### Re: Unpredictable error triangulating a polygon

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

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

### Re: Unpredictable error triangulating a polygon

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.

### Who is online

Users browsing this forum: No registered users and 19 guests