Table of Contents

Class EarClipping

Namespace
Stride.CommunityToolkit.Rendering
Assembly
Stride.CommunityToolkit.dll

Triangulates 2D polygons by ear clipping, with or without holes.

public static class EarClipping
Inheritance
EarClipping

Remarks

Ear clipping repeatedly finds a corner whose triangle lies entirely inside the polygon (an "ear"), emits that triangle, and removes the corner - always terminating with n-2 triangles for an n-vertex polygon. It handles any simple polygon, convex or concave.

A polygon with holes is first made simple: each hole is joined to the outside by a bridge, two edges that run between a corner of the hole and a corner of the outside that can see it, and the result is clipped as one polygon. That is how a font's O or B becomes triangles; see Triangulate(IReadOnlyList<Vector2>, IReadOnlyList<IReadOnlyList<Vector2>>). Self-intersecting polygons are not handled by either overload.

The tolerances scale with the polygon: a corner counts as flat, or a point as on a triangle's edge, relative to the polygon's extent, so a glyph a centimetre across triangulates the same way as one a metre across.

Methods

SignedArea(IReadOnlyList<Vector2>)

Returns the polygon's signed area: positive for counter-clockwise winding.

public static float SignedArea(IReadOnlyList<Vector2> polygon)

Parameters

polygon IReadOnlyList<Vector2>

The polygon's corners, in order.

Returns

float

The signed area, by the shoelace formula.

Triangulate(IReadOnlyList<Vector2>)

Triangulates a simple polygon into a list of vertex-index triples.

public static List<int> Triangulate(IReadOnlyList<Vector2> polygon)

Parameters

polygon IReadOnlyList<Vector2>

The polygon's corners, in order, without repeating the first corner at the end. Either winding is accepted.

Returns

List<int>

Indices into polygon, three per triangle, (corner count - 2) triangles in total for a polygon with no flat corners. Triangles are always wound counter-clockwise, whichever way the input was wound.

Exceptions

ArgumentNullException

The polygon is null.

ArgumentException

The polygon has fewer than three corners.

InvalidOperationException

No ear could be found, which means the polygon self-intersects.

Triangulate(IReadOnlyList<Vector2>, IReadOnlyList<IReadOnlyList<Vector2>>)

Triangulates a polygon with holes into a list of vertex-index triples.

public static List<int> Triangulate(IReadOnlyList<Vector2> outer, IReadOnlyList<IReadOnlyList<Vector2>> holes)

Parameters

outer IReadOnlyList<Vector2>

The outside, in order, without repeating the first corner. Either winding is accepted.

holes IReadOnlyList<IReadOnlyList<Vector2>>

The holes, each in order without repeating its first corner, each lying inside the outside and not touching it or each other. Either winding is accepted.

Returns

List<int>

Indices into the corners of outer followed by those of each hole in order, three per triangle, wound counter-clockwise. A polygon of n corners in all with h holes gives up to n + 2h - 2 triangles; a flat corner made by a bridge is clipped without one.

Remarks

Each hole is bridged to the outside at its rightmost corner, towards the first edge a ray to the right meets, the method of Eberly's "Triangulation by Ear Clipping". Holes are bridged rightmost first, so a bridge never crosses a hole bridged later. A hole with fewer than three corners is ignored.

Exceptions

ArgumentNullException

The outside or the holes are null.

ArgumentException

The outside has fewer than three corners.

InvalidOperationException

A hole lies outside the outside, or the polygon self-intersects.