Class EarClipping
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
polygonIReadOnlyList<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
polygonIReadOnlyList<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
outerIReadOnlyList<Vector2>The outside, in order, without repeating the first corner. Either winding is accepted.
holesIReadOnlyList<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
outerfollowed 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.