Polygonal Decomposition – Concavity Support

[Abe _King_ Participant]

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!

Monkey

#Import "MakeConvex.monkey2"</p> <p>Alias Poly:polygonmath</p> <p>Function Main()</p> <p> ' 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) )</p> <p> ' Convert to stack Local points:= New Stack<Vec2i>( pointsA ) </p> <p> ' Basic printing function Local printPoints:= ( Lambda(s:Stack<Vec2i>) Local ps:= "" For Local p:=Eachin s ps += p.X + "," + p.Y + " --> " Next Print ps + "~n" End )</p> <p> ' Display the original point list printPoints( points )</p> <p> ' Display the created groups Local groups:=Poly.MakeConvex( points ) For Local poly:=Eachin groups Print "group: " printPoints( poly ) Next</p> <p>End</p> <p>#Rem Results: 0,0 --> 0,1 --> 1,3 --> 2,1 --> 2,0 --> 1,1 --> </p> <p> group: 1,1 --> 0,0 --> 0,1 --> 1,3 --> </p> <p> group: 1,3 --> 2,1 --> 2,0 --> 1,1 --> #End

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

#Import "MakeConvex.monkey2"   Alias Poly:polygonmath   Function 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 stack Local points:= New Stack<Vec2i>( pointsA ) ' Basic printing function Local printPoints:= ( Lambda(s:Stack<Vec2i>) Local ps:= "" For Local p:=Eachin s ps += p.X + "," + p.Y + "  -->  " Next Print ps + "~n" End ) ' Display the original point list printPoints( points ) ' Display the created groups Local groups:=Poly.MakeConvex( points ) For Local poly:=Eachin groups Print "group: " printPoints( poly ) Next End   #Rem Results:   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:

https://gamedevnotesblog.wordpress.com/2017/10/29/designing-algorithms-intuitively-convex-decomposition-of-simple-polygons/

[DruggedBunny Participant]

Interesting, saved!

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.

[abakobo Participant]

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:

1. 

   one.jpg
   

2. 

   two.jpg
   

[DruggedBunny Participant]

[EDIT: Oopsie, ha ha.]

[Abe _King_ Participant]

@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.

[abakobo Participant]

Ah Ok shader stufff!?

Yes splitting a convex to convex is pretty straightforward… thx again.

[Abe _King_ Participant]

@abakobo –removed wrong reply— No shaders involved there! All primitive work, with special thanks to Ethernauts for his help

[Author]

Posts