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?
Triangulating complex polygons
Forum rules
Before you make a thread asking for help, read this.
Before you make a thread asking for help, read this.
Re: Triangulating complex polygons
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.
My Tox ID: 0F1FB9170B94694A90FBCF6C4DDBDB9F58A9E4CDD0B4267E50BF9CDD62A0F947E376C5482610
Re: Triangulating complex polygons
https://en.wikipedia.org/wiki/Complex_polygonI~=Spam wrote: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.
Re: Triangulating complex polygons
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.furi wrote:https://en.wikipedia.org/wiki/Complex_polygonI~=Spam wrote: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.
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/
My Tox ID: 0F1FB9170B94694A90FBCF6C4DDBDB9F58A9E4CDD0B4267E50BF9CDD62A0F947E376C5482610
Re: Triangulating complex polygons
What you would need to do is decompose the complex polygon into concave polygons and triangulate each one.furi wrote: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'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...
Re: Triangulating complex polygons
'Triangle' is a great, fast library if you're looking for constrained Delauney triangulation.I~=Spam wrote: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?
It supports holes, but I don't think it would work with complex polygons.
This one is nice too, but again it's for triangulation + partitioning into convex shapes.I~=Spam wrote:EDIT2: Another lib lol https://code.google.com/p/polypartition/
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 )
Re: Triangulating complex polygons
This looks nice.ivan wrote:http://www.angusj.com/delphi/clipper.php
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/#Licensingivan wrote:http://www.cs.man.ac.uk/~toby/alan/software/ (Lua binding: http://webserver2.tecgraf.puc-rio.br/~lhf/ftp/lua/#lgpc )
My Tox ID: 0F1FB9170B94694A90FBCF6C4DDBDB9F58A9E4CDD0B4267E50BF9CDD62A0F947E376C5482610
Who is online
Users browsing this forum: Bing [Bot] and 6 guests