Module org.dyn4j

Class EarClipping

  • All Implemented Interfaces:
    Decomposer, Triangulator

    public class EarClipping
    extends java.lang.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).

    Since:
    2.2.0
    Version:
    3.2.0
    Author:
    William Bittle
    • Constructor Summary

      Constructors 
      Constructor Description
      EarClipping()  
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      protected boolean contains​(Vector2 a, Vector2 b, Vector2 c, Vector2 p)
      Returns true if the given point, p, is contained in the triangle created by a, b, and c.
      (package private) DoubleEdgeList createTriangulation​(Vector2... points)
      Creates a triangulation of the given simple polygon and places it into the returned doubly-connected edge list (DCEL).
      java.util.List<Convex> decompose​(Vector2... points)
      Performs the decomposition on the given polygon returning a list of Convex shapes.
      (package private) boolean isEar​(EarClippingVertex vertex, int n)
      Returns true if the given vertex is considered an ear vertex.
      (package private) boolean isReflex​(EarClippingVertex vertex)
      Returns true if the given vertex is a reflex vertex.
      java.util.List<Triangle> triangulate​(Vector2... points)
      Performs the triangulation on the given polygon returning a list of Triangles.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • EarClipping

        public EarClipping()
    • Method Detail

      • decompose

        public java.util.List<Convex> decompose​(Vector2... points)
        Description copied from interface: Decomposer
        Performs the decomposition on the given polygon returning a list of Convex shapes.
        Specified by:
        decompose in interface Decomposer
        Parameters:
        points - the polygon vertices
        Returns:
        List<Convex>
      • triangulate

        public java.util.List<Triangle> triangulate​(Vector2... points)
        Description copied from interface: Triangulator
        Performs the triangulation on the given polygon returning a list of Triangles.
        Specified by:
        triangulate in interface Triangulator
        Parameters:
        points - the polygon vertices
        Returns:
        List<Triangle>
      • createTriangulation

        final DoubleEdgeList createTriangulation​(Vector2... points)
        Creates a triangulation of the given simple polygon and places it into the returned doubly-connected edge list (DCEL).
        Parameters:
        points - the simple polygon vertices
        Returns:
        DoubleEdgeList
        Since:
        3.1.9
      • isReflex

        final boolean isReflex​(EarClippingVertex vertex)
        Returns true if the given vertex is a reflex vertex.

        A reflex vertex is a vertex who's adjacent vertices create an an angle greater than 180 degrees (or the cross product is positive) for CCW vertex winding.

        Parameters:
        vertex - the vertex to test
        Returns:
        boolean true if the given vertex is considered a reflex vertex
      • isEar

        final boolean isEar​(EarClippingVertex vertex,
                            int n)
        Returns true if the given vertex is considered an ear vertex.

        A vertex is an ear vertex if the triangle created by the adjacent vertices of the given vertex does not contain any other vertices within it.

        A reflex vertex cannot be an ear.

        Parameters:
        vertex - the vertex to test for ear-ness
        n - the number of vertices
        Returns:
        boolean true if the given vertex is considered an ear vertex
      • contains

        protected boolean contains​(Vector2 a,
                                   Vector2 b,
                                   Vector2 c,
                                   Vector2 p)
        Returns true if the given point, p, is contained in the triangle created by a, b, and c.
        Parameters:
        a - the first point of the triangle
        b - the second point of the triangle
        c - the third point of the triangle
        p - the point to test for containment
        Returns:
        boolean true if the given point is contained in the given triangle