EarClippingTriangulator

View source
ceramic._Triangulate.EarClippingTriangulator (private class)

Implementation of the ear-clipping algorithm for polygon triangulation.

A simple implementation of the ear cutting algorithm to triangulate simple polygons without holes. The algorithm works by:

  1. Finding "ear" vertices (vertices that form triangles with no other vertices inside)
  2. Clipping these ears one by one
  3. Repeating until only one triangle remains

For more information:

  • http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/algorithm2.html
  • http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

Performance characteristics:

  • Time complexity: O(n²) for n vertices
  • Works with both convex and concave polygons
  • Handles degenerate cases (nearly collinear vertices)

Limitations:

  • If the input polygon is not simple (self-intersects), there will be output but it is of unspecified quality (garbage in, garbage out).
  • If the polygon vertices are very large or very close together then GeometryUtils.isClockwise() may not be able to properly assess the winding (because it uses floats). In that case the vertices should be adjusted, eg by finding the smallest X and Y values and subtracting that from each vertex.

@author badlogicgames@gmail.com @author Nicolas Gramlich (optimizations, collinear edge support) @author Eric Spitz @author Thomas ten Cate (bugfixes, optimizations) @author Nathan Sweet (rewrite, return indices, no allocation, optimizations) @author Jérémy Faivre (ported to Haxe)

Instance Members

computeTriangles(vertices: Array<Float>, ?offset: Int = 0, ?count: Int = -1, ?outputTriangles: Array<Int>): Array<Int>

Triangulates the given (convex or concave) simple polygon to a list of triangle vertices.

The algorithm automatically detects and handles the winding order of the input, always producing triangles in clockwise order. The triangulation is performed in-place with minimal allocations.

Name Type Default Description
vertices Array<Float> Pairs describing vertices of the polygon [x0,y0, x1,y1, ...], in either clockwise or counterclockwise order.
offset Int 0 The offset into the vertices array (in array elements, not vertices). Default: 0
count Int -1 The number of array elements to use (not vertex count). Use -1 to process all remaining elements. Default: -1
outputTriangles Array<Int> (optional) Optional array to fill with triangle indices. Will be cleared before use. If not provided, a new array is created.
Returns Description
Array<Int> Array of triangle indices in clockwise order. Each group of 3 indices forms one triangle. * haxe var triangulator = new EarClippingTriangulator(); var vertices = [0,0, 100,0, 100,100, 0,100]; // Square var indices = triangulator.computeTriangles(vertices); // indices = [0,1,2, 0,2,3] (two triangles)
new(): Void

Private Members

CONCAVE: Int
CONVEX: Int
indices: Array<Int>
vertexTypes: Array<Int>
vertices: Array<Float>
vertexCount: Int
triangles: Array<Int>
computeSpannedAreaSign(p1x: Float, p1y: Float, p2x: Float, p2y: Float, p3x: Float, p3y: Float): Int

Computes the sign of the area of the triangle formed by three points.

Uses the cross product to determine orientation:

  • Positive: Counter-clockwise winding (convex in a clockwise polygon)
  • Negative: Clockwise winding (concave in a clockwise polygon)
  • Zero: Collinear points
Name Type Description
p1x Float X coordinate of first point
p1y Float Y coordinate of first point
p2x Float X coordinate of second point
p2y Float Y coordinate of second point
p3x Float X coordinate of third point
p3y Float Y coordinate of third point
Returns Description
Int 1 for positive area, -1 for negative area, 0 for collinear
triangulate(): Void
classifyVertex(index: Int): Int

Determines if a vertex is convex or concave based on the sign of the area spanned by it and its adjacent vertices.

Name Type Description
index Int The vertex index to classify
Returns Description
Int CONVEX (1) if the vertex forms a convex angle, CONCAVE (-1) if it forms a concave angle, or 0 if the vertices are collinear
findEarTip(): Int

Finds a vertex that can be safely removed as an ear tip.

An ear tip is a vertex that:

  1. Is convex (or tangential)
  2. Forms a triangle with its neighbors that contains no other vertices

If no valid ear is found (degenerate polygon), falls back to:

  1. Any convex vertex
  2. The first vertex (if all are concave - shouldn't happen in valid polygons)
Returns Description
Int Index of the ear tip vertex to remove
isEarTip(earTipIndex: Int): Bool

Tests whether a vertex is a valid ear tip that can be clipped.

A vertex is an ear tip if:

  1. It's convex (not concave)
  2. The triangle formed with its neighbors contains no other polygon vertices

The test uses the sign of computed areas to determine if points are inside the triangle. Points exactly on edges are considered inside.

Name Type Description
earTipIndex Int The vertex index to test
Returns Description
Bool true if the vertex is a valid ear tip
cutEarTip(earTipIndex: Int): Void

Removes an ear tip vertex and adds the resulting triangle to the output.

Creates a triangle from the ear tip and its two neighbors, then removes the ear tip vertex from further consideration.

Name Type Description
earTipIndex Int The index of the ear tip vertex to remove
getPreviousIndex(index: Int): Int
Name Type
index Int
Returns
Int
getNextIndex(index: Int): Int
Name Type
index Int
Returns
Int

Metadata

Name Parameters
:allow ceramic.Triangulate