Decomposer algorithms are non-optimal, meaning they do
not always produce a decomposition with the minimum number of convex pieces. Instead, they get close
in exchange for performance.
NOTE: All three
Decomposer algorithms operate on simple
polygons without holes.
algorithms both triangulate the simple polygon first, then run Hertel-Mehlhorn to recombine triangles
into convex pieces. Hertel-Mehlhorn is guarenteed to produce a convex decomposition with no more than
4 times the minimum number of convex pieces.
Bayazit algorithm has O(nr) time-complexity.
EarClipping algorithm has O(n2) time-complexity.
SweepLine algorithm has O(n log n) time-complexity.
In general the algorithms will generate different decompositions. If used for pre-processing just
choose the best result, for runtime generation, the
may be slower but will generally produce a better decomposition.
A "better" decomposition is one that contains fewer convex pieces and the convex pieces that are created are of better quality for simulation.
- William Bittle
Interface Summary Interface Description DecomposerRepresents an algorithm to decompose a given polygon (as a list of points) into
TriangulatorRepresents an algorithm to triangulate a given polygon (as a list of points) into
Class Summary Class Description BayazitImplementation of the Bayazit convex decomposition algorithm for simple polygons. EarClippingImplementation of the Ear Clipping convex decomposition algorithm for simple polygons. SweepLineImplementation of the Sweep convex decomposition algorithm for simple polygons.