Module org.dyn4j

## Class EarClipping

• java.lang.Object
• org.dyn4j.geometry.decompose.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
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 `Triangle`s.
• ### 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 `Triangle`s.
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