Menu
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)
757
A concave polygon is a polygon which is not convex. This polygon is just the opposite of a convex polygon. A simple polygon is considered as a concave polygon if and only if at least one of the interior angles is a reflex angle (between 180° and 360°).
Sum of all the interior angles of a polygon of n sides = (n – 2)180°. The diagonals of the convex polygon lie completely inside the polygon. Area of convex polygon can be determined by dividing the polygon into triangles and then finding the area of each triangle and summing up them.
What is the Difference Between a Concave and Convex Polygon? A convex polygon does not have a dent in the shape whereas a concave polygon has one side of the shape towards the inside of the shape. The interior angles of a convex polygon are less than 180° whereas the angles in a concave polygon are more than 180°.
In real life, a stop sign is an example of a convex polygon, and a cross is an example of a concave polygon.
Bernard Chazelle and David P. Dobkin presented an algorithm for that in 1985: Optimal Convex Decompositions.
Other approaches can be found on Wikipedia.
78
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
