Convex
pieces.
Three implementations of the Decomposer
interface are provided: Bayazit
,
EarClipping
, and
SweepLine
.
All three Decomposer
algorithms are nonoptimal, 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.
The EarClipping
and SweepLine
algorithms both triangulate the simple polygon first, then run HertelMehlhorn to recombine triangles
into convex pieces. HertelMehlhorn is guarenteed to produce a convex decomposition with no more than
4 times the minimum number of convex pieces.
The EarClipping
and SweepLine
algorithms also implement the Triangulator
interface to provide
the ability to get a triangulation as well.
The Bayazit
algorithm has O(nr) timecomplexity.
The EarClipping
algorithm has O(n^{2}) timecomplexity.
The SweepLine
algorithm has O(n log n) timecomplexity.
In general the algorithms will generate different decompositions. If used for preprocessing just
choose the best result, for runtime generation, the Bayazit
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.
Interface  Description 

Decomposer 
Represents an algorithm to decompose a given polygon (as a list of points) into
Convex pieces. 
Triangulator 
Represents an algorithm to triangulate a given polygon (as a list of points) into
Triangle s. 
Class  Description 

Bayazit 
Implementation of the Bayazit convex decomposition algorithm for simple polygons.

EarClipping 
Implementation of the Ear Clipping convex decomposition algorithm for simple polygons.

SweepLine 
Implementation of the Sweep convex decomposition algorithm for simple polygons.
