January 17, 2019 at 2:00 am #15932
This will convert a generic Vec2D list, assumed polygon, and convert it into a list of convex polygons. It has a very simple interface, it literally only uses one function. I’m not certain this has been done, but the more the merrier!
You can find the source in this Gist: https://gist.github.com/Ghouly-The-Ghost/d8d2c9973ff7dc120d94b356730c75f9
This is how you use it!Monkey1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#Import "MakeConvex.monkey2"Alias Poly:polygonmathFunction Main()' Using this concave shape.' /\' / \' / \' / \' | /\ |' | / \ |' |/ \|'Local pointsA:=New Vec2i(New Vec2i(0,0),New Vec2i(0,1),New Vec2i(1,3),New Vec2i(2,1),New Vec2i(2,0),New Vec2i(1,1) )' Convert to stackLocal points:= New Stack<Vec2i>( pointsA )' Basic printing functionLocal printPoints:= ( Lambda(s:Stack<Vec2i>)Local ps:= ""For Local p:=Eachin sps += p.X + "," + p.Y + " --> "NextPrint ps + "~n"End )' Display the original point listprintPoints( points )' Display the created groupsLocal groups:=Poly.MakeConvex( points )For Local poly:=Eachin groupsPrint "group: "printPoints( poly )NextEnd#RemResults:0,0 --> 0,1 --> 1,3 --> 2,1 --> 2,0 --> 1,1 -->group:1,1 --> 0,0 --> 0,1 --> 1,3 -->group:1,3 --> 2,1 --> 2,0 --> 1,1 -->#End
I want to add thanks to the guys behind HaxePunk, that’s the reason I was able to write this! Special thanks to Matrefeytontias who is responsible for the algorithm and the source code I translated. He even wrote an article over the process over here:January 17, 2019 at 6:14 am #15935
There’s a vaguely similar module in the Ted2Go Module Manager (under Build menu), png2polygon, might be of interest if you haven’t seen it — produces polygons from PNG images, worked really well as far as I recall.January 17, 2019 at 3:58 pm #15942
LOL! You could not do it at a better time for me as I was going to use Mark Bayazit’s algorithm for this purpose (https://mpen.ca/406/bayazit). I suppose you do it for box2d. Have you implemented the max number of vertices=8 ?
I’m working on a box2dxt function to decompose complex polygons and I’ve nearly finished the step of decomposing complex poly to simple polys now! so now I need concave decomp (and reduction to 8 vertices).
You can see pictures (attached) of the “decomplexification” of complex polys 😉 Now I have to split and convex decomp it!
So… great thx!
Attachments:January 17, 2019 at 6:26 pm #15945
[EDIT: Oopsie, ha ha.]January 17, 2019 at 11:39 pm #15946
@abakobo My intentions for making this actually weren’t for Box2d, although I was thinking it would be fairly useful in the future if I wanted to use it with Box2D.
I actually needed this for textured polygons which I have got working – shown here: https://www.youtube.com/watch?v=fp1nCmfV-aw&feature=youtu.be
This splits it up into a stack of convex polygons though, and if you needed to break them down into less than 8 vertices I would imagine the step of splitting an already convex polygon would be pretty simple.
This is not a proof . . . but I believe, since all diagonals of a convex polygon lie inside of it, that if you split a convex polygon from any vertex to another you’ll end up with two convex polygons. So it should be easy to do using some recursive function. And I suppose you could re-use this function if you are not confident it will always be convex – since this code guarantees one.January 18, 2019 at 7:03 am #15949
Ah Ok shader stufff!?
Yes splitting a convex to convex is pretty straightforward… thx again.January 18, 2019 at 8:41 am #15950
@abakobo –removed wrong reply— No shaders involved there! All primitive work, with special thanks to Ethernauts for his help 🙂January 26, 2019 at 6:59 pm #16007
I have finnnallly finished the complex polygon (positive)partitionning. I had made a lot of mistakes and the problem was a bit difficult. But it’s there. It just won’t allow collinear&intersecting segment at the “edge” of the poly.
If anybody wants to try it, the code is attached. Run polytoolstest.monkey2 for demo. It is not decomposing to convex polys yet.
You must be logged in to reply to this topic.