Triangulation

compas_model.geometry.triangulation

Classes

EarcutResult dataclass

EarcutResult(
    vertices: tuple[Point, ...],
    triangles: tuple[tuple[int, int, int], ...],
    ring_ends: tuple[int, ...],
)

Result of tolerance-aware polygon ear clipping.

Parameters:

• vertices (tuple[Point, ...]) –

  Cleaned three-dimensional polygon vertices. Exterior vertices are followed by the vertices of every hole.

• triangles (tuple[tuple[int, int, int], ...]) –

  Triangle indices into vertices.

• ring_ends (tuple[int, ...]) –

  Exclusive end index of each ring in vertices.

Functions:

triangulate_polygon_earcut

triangulate_polygon_earcut(
    exterior: Iterable[Sequence[float]],
    holes: Iterable[Iterable[Sequence[float]]] | None = None,
    tolerance: float = 1e-09,
) -> EarcutResult

Triangulate a planar polygon with optional holes using Mapbox Earcut.

Parameters:

• exterior (Iterable[Sequence[float]]) –

  Exterior polygon ring in three-dimensional coordinates.

• holes (Iterable[Iterable[Sequence[float]]] | None, default: None ) –

  Optional interior polygon rings.

• tolerance (float, default: 1e-09 ) –

  Distance used to remove consecutive duplicate and collinear vertices before triangulation.

Returns:

• EarcutResult –

  Cleaned vertices, triangle indices, and ring end indices.

Raises:

• ValueError –

  If the tolerance is negative, a ring is degenerate, the projected polygon is invalid, or triangulation does not cover its area.

Notes

The rings are projected along the dominant component of the exterior's Newell normal. Mapbox Earcut accepts either winding direction. Its output is verified against the area of the projected Shapely polygon because Earcut prioritises practical robustness over guaranteed correctness for arbitrary invalid input.