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.

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) into `Convex` pieces.
Triangulator
Represents an algorithm to triangulate a given polygon (as a list of points) into `Triangle`s.
• Class Summary
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.