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. ClosestEdgeToVertexSearchCriteriaRepresents a
BinarySearchTreeSearchCriteriafor finding the closest edge to the left of a given vertex.
DoubleEdgeListHighly specialized Doubly Connected Edge List (DCEL) used to store vertices of a simple polygon and then be used to create and store triangulations and convex decompositions of that same polygon. DoubleEdgeListFaceRepresents a face in the
DoubleEdgeListHalfEdgeRepresents a half edge of the
DoubleEdgeListVertexRepresents a vertex in the
EarClippingImplementation of the Ear Clipping convex decomposition algorithm for simple polygons. EarClippingVertexNode class for a vertex within a simple polygon for the
MonotonePolygon<E>Represents a monotone polygon. MonotoneVertex<E>Represents a vertex of a monotone polygon. SweepLineImplementation of the Sweep convex decomposition algorithm for simple polygons. SweepLineEdgeRepresents an edge of a polygon storing the next and previous edges and the vertices that make up this edge. SweepLineStateRepresents the current state of the SweepLine algorithm. SweepLineVertexRepresents a vertex on a polygon that stores information about the left and right edges and left and right vertices.
Enum Summary Enum Description MonotoneChainTypeEnumeration of monotone chain types. MonotonePolygonTypeEnumeration of the types of monotone polygons supported. SweepLineVertexTypeEnumeration of the