Module org.dyn4j

Package org.dyn4j.geometry.decompose

This package contains algorithms to decompose polygons into Convex pieces.

Three implementations of the Decomposer interface are provided: Bayazit, EarClipping, and SweepLine.

All three 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.

The EarClipping and SweepLine 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.

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) time-complexity.

The EarClipping algorithm has O(n2) time-complexity.

The 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 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.

William Bittle
Skip navigation links