Triangulating complex polygons

[furi]

Hi! I'm trying to work on a means to import .fla files into LOVE.

I've got almost everything working, but in the case that a line intersects with itself, love.math.triangulate errors out.
Are there any known alternatives to the built-in function that properly work in this situation? If not, how would I get started on tackling this problem?

[I~=Spam]

If it intersects itself, by definition, the method that is used to chop up the polygon is not defined. The reason for this is that the shape isn't a polygon if it intersects itself.

[furi]

If it intersects itself, by definition, the method that is used to chop up the polygon is not defined. The reason for this is that the shape isn't a polygon if it intersects itself.

https://en.wikipedia.org/wiki/Complex_polygon

[I~=Spam]

If it intersects itself, by definition, the method that is used to chop up the polygon is not defined. The reason for this is that the shape isn't a polygon if it intersects itself.

https://en.wikipedia.org/wiki/Complex_polygon

Oh I missed complex polygon in the title. I didn't know that there is a subset of polygons that modifies the original definition that they cannot intersect themselves. lol Either way love's algorithm clearly cannot do it.

A quick google search yielded this: http://www.cs.cmu.edu/~quake/triangle.html It is in C but you can build a lua library right?

Here's a list of libraries that do simple polygons (some might do complex too): http://vterrain.org/Implementation/Libs ... ulate.html

And other http://www.cosy.sbg.ac.at/~held/project ... riang.html

This might have one too: http://www.cgal.org/ EDIT: Here is a better link http://doc.cgal.org/latest/Manual/packa ... rtPolygons

EDIT2: Another lib lol https://code.google.com/p/polypartition/

[ivan]

Are there any known alternatives to the built-in function that properly work in this situation? If not, how would I get started on tackling this problem?

What you would need to do is decompose the complex polygon into concave polygons and triangulate each one.

I'm afraid this is a bit of hairy problem especially when you get odd-even rules involved.
From what I understand, the general technique for decomposing self-intersections is:
1.find all intersecting edges
2.store the points where each pair of edges intersects
3.iterate each edge by making turns in specific directions
Seems simple, but it's hard to write an algorithm that is robust and could work in realtime.

Look at libraries like General Polygon Clipper they have functionality you are look for.
But as I said, keep in mind that this is not something you want to do in realtime...

[ivan]

A quick google search yielded this: http://www.cs.cmu.edu/~quake/triangle.html It is in C but you can build a lua library right?

'Triangle' is a great, fast library if you're looking for constrained Delauney triangulation.
It supports holes, but I don't think it would work with complex polygons.

EDIT2: Another lib lol https://code.google.com/p/polypartition/

This one is nice too, but again it's for triangulation + partitioning into convex shapes.

What you want is something like Clipper or GPC:
http://www.angusj.com/delphi/clipper.php
http://www.cs.man.ac.uk/~toby/alan/software/ (Lua binding: http://webserver2.tecgraf.puc-rio.br/~lhf/ftp/lua/#lgpc )

[I~=Spam]

http://www.angusj.com/delphi/clipper.php

This looks nice.

http://www.cs.man.ac.uk/~toby/alan/software/ (Lua binding: http://webserver2.tecgraf.puc-rio.br/~lhf/ftp/lua/#lgpc )

Cool! A lua wrapper! But this is for non-commercial use only unless you get a commercial licence from the university that maintains it. That wouldn't matter to me because I make things that are either open source or just for me. But idk about furi... http://www.cs.man.ac.uk/~toby/alan/software/#Licensing