Breaking a concave polygon into convex ones

actionscript-3 physics polygon box2d
Bart van Heukelom picture Bart van Heukelom · Mar 16, 2010 · Viewed 10.6k times · Source

I'm using a game physics library (Box2D) which only supports convex polygon shapes. However, I'd like the level builder to be able to just specify concave polygons without having to worry about that.

So, how can I automatically break apart a concave polygon into convex ones (or even all triangles). Speed would be cool, but ease of implementation is more important. The breaking apart will only be done on game initialization.

(My language is Flash/ActionScript 3, but that shouldn't matter)

Answer

Joey picture Joey · Mar 16, 2010

Bernard Chazelle and David P. Dobkin presented an algorithm for that in 1985: Optimal Convex Decompositions.

Other approaches can be found on Wikipedia.

Related questions

What is the best way to get the minimum or maximum value from an Array of numbers?

Let's say I have an Array of numbers: [2,3,3,4,2,2,5,6,7,2] What is the best way to find the minimum or maximum value in that Array? Right now, to get the maximum, I am looping through the Array, and resetting a variable to …

Read More
Difference between e.target and e.currentTarget

I don't understand the difference, they both seem the same but I guess they are not. Any examples of when to use one or the other would be appreciated.

Read More
Call AngularJS from legacy code

I'm using AngularJS to build HTML controls that interact with a legacy Flex application. All callbacks from the Flex app must be attached to the DOM window. For example (in AS3) ExternalInterface.call("save", data); Will call window.save = function(…

Read More