Module org.dyn4j

Class EarClipping

  • All Implemented Interfaces:
    Decomposer, Triangulator

    public class EarClipping
    extends Object
    implements Decomposer, Triangulator
    Implementation of the Ear Clipping convex decomposition algorithm for simple polygons.

    This algorithm operates only on simple polygons. A simple polygon is a polygon that has vertices that are connected by edges where:

    • Edges can only intersect at vertices
    • Vertices have at most two edge connections

    This implementation does not handle polygons with holes, but accepts both counter-clockwise and clockwise polygons.

    The polygon to decompose must be 4 or more vertices.

    This algorithm creates a valid triangulation (N - 2) triangles, then employs the Hertel-Mehlhorn algorithm to reduce the number of convex pieces.

    This algorithm is O(n2).

    William Bittle
    • Constructor Detail

      • EarClipping

        public EarClipping()