Package org.dyn4j.geometry.decompose
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.
 Since:
 2.2.0
 Version:
 3.2.0
 Author:
 William Bittle

Interface Summary Interface Description Decomposer Represents an algorithm to decompose a given polygon (as a list of points) intoConvex
pieces.Triangulator Represents an algorithm to triangulate a given polygon (as a list of points) intoTriangle
s. 
Class Summary Class Description Bayazit Implementation of the Bayazit convex decomposition algorithm for simple polygons.ClosestEdgeToVertexSearchCriteria Represents aBinarySearchTreeSearchCriteria
for finding the closest edge to the left of a given vertex.DoubleEdgeList Highly 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.DoubleEdgeListFace Represents a face in theDoubleEdgeList
.DoubleEdgeListHalfEdge Represents a half edge of theDoubleEdgeList
.DoubleEdgeListVertex Represents a vertex in theDoubleEdgeList
.EarClipping Implementation of the Ear Clipping convex decomposition algorithm for simple polygons.EarClippingVertex Node class for a vertex within a simple polygon for theEarClipping
algorithm.MonotonePolygon<E> Represents a monotone polygon.MonotoneVertex<E> Represents a vertex of a monotone polygon.SweepLine Implementation of the Sweep convex decomposition algorithm for simple polygons.SweepLineEdge Represents an edge of a polygon storing the next and previous edges and the vertices that make up this edge.SweepLineState Represents the current state of the SweepLine algorithm.SweepLineVertex Represents a vertex on a polygon that stores information about the left and right edges and left and right vertices. 
Enum Summary Enum Description MonotoneChainType Enumeration of monotone chain types.MonotonePolygonType Enumeration of the types of monotone polygons supported.SweepLineVertexType Enumeration of theSweepLineVertex
types.