Triangulating CAD Polygons with Earcut in Python

CAD faces arrive as closed rings — an outer boundary plus zero or more interior holes — that must be decomposed into triangles before they can enter a mesh, a glTF buffer, or a WebGL draw call. The most robust Python route is ear-clipping triangulation: mapbox_earcut.triangulate_float64(verts, ring_end_indices) turns a flat vertex array and a set of ring boundaries into a triangle index list, handling concave outlines and holes that naive fan triangulation corrupts. This page is part of the Geometry Mesh Conversion workflow within the broader Python Parsing & Geometry Extraction pipeline, and it pairs directly with Converting CAD Polylines to GeoJSON, which produces the closed rings this stage consumes.

How Earcut Handles CAD Polygons with Holes

Ear-clipping repeatedly removes “ears” — triangles formed by three consecutive vertices that contain no other vertex — until the polygon is fully triangulated. The mapbox_earcut package binds the same z-order-optimized C++ implementation that powers Mapbox GL, so it stays fast on the thousand-vertex outlines that hatch boundaries and building footprints produce. It accepts a single flattened vertex array and a list of ring end indices: the cumulative vertex count at which each ring ends. The first ring is always the exterior; every subsequent ring is treated as a hole.

Critically, earcut identifies holes by position in ring_end_indices, not by winding direction. Winding still matters for the output: the triangle vertex order it emits follows the input, so an exterior ring wound clockwise yields inward-facing normals. For meshes destined for a renderer that back-face culls, normalize orientation first — exterior counter-clockwise, holes clockwise.

The diagram below shows the flattening step that most implementations get wrong: rings are concatenated head-to-tail into one buffer, and only the boundary offsets are handed to earcut.

ezdxf ships the same algorithm through ezdxf.math.triangulation.mapbox_earcut_2d(exterior, holes=None), which returns triangles as 3-tuples of Vec2 objects — convenient when you are already traversing DXF entities and do not want to manage NumPy index buffers. Note that in current ezdxf (1.x) this function lives in the ezdxf.math.triangulation submodule and is not re-exported at ezdxf.math top level, and there is no separate ear_clipping_2d helper. What earcut does not do is validate topology: it will happily triangulate a self-intersecting bow-tie ring into overlapping triangles. Validity is your responsibility, and that is where shapely earns its place.

Production-Ready Script

The script takes an exterior ring and a list of hole rings, repairs them with shapely, normalizes winding, flattens to the earcut input layout, triangulates, and optionally returns a trimesh.Trimesh.

# mapbox_earcut>=1.0.0, ezdxf>=1.1.0, shapely>=2.0.0, numpy>=1.24.0, Python 3.9+
# trimesh>=4.0.0 is optional (only for the mesh return path)
from __future__ import annotations

import numpy as np
import mapbox_earcut as earcut
from shapely.geometry import Polygon
from shapely.geometry.polygon import orient
from shapely.validation import make_valid


def triangulate_face(
    exterior: list[tuple[float, float]],
    holes: list[list[tuple[float, float]]] | None = None,
    z: float = 0.0,
    as_trimesh: bool = False,
):
    """Triangulate a CAD face (outer ring + holes) into vertices and faces.

    Returns (vertices Nx3 float64, faces Mx3 int64). If as_trimesh is True,
    returns a trimesh.Trimesh instead. Raises ValueError on empty or
    non-triangulable input.
    """
    holes = holes or []

    # 1. Validate and repair the ring set BEFORE triangulation.
    poly = Polygon(exterior, holes)
    if not poly.is_valid:
        repaired = make_valid(poly)
        # make_valid can return a MultiPolygon or GeometryCollection;
        # keep the largest polygon component as the face boundary.
        poly = _largest_polygon(repaired)
    if poly.is_empty or poly.area == 0.0:
        raise ValueError("Face has zero area after validity repair.")

    # 2. Normalize winding: exterior CCW (sign=1.0), interiors CW.
    poly = orient(poly, sign=1.0)

    # 3. Flatten rings into one vertex array + cumulative ring end indices.
    rings = [list(poly.exterior.coords)[:-1]]  # drop the closing duplicate
    rings += [list(r.coords)[:-1] for r in poly.interiors]

    verts_2d = np.array(
        [pt for ring in rings for pt in ring], dtype=np.float64
    )
    ring_end_indices = np.cumsum([len(r) for r in rings]).astype(np.uint32)

    if len(verts_2d) < 3:
        raise ValueError("Fewer than three vertices; nothing to triangulate.")

    # 4. Ear-clip. Result is a flat uint32 array; every 3 entries = 1 triangle.
    tri_index = earcut.triangulate_float64(verts_2d, ring_end_indices)
    if tri_index.size == 0:
        raise ValueError("Earcut produced no triangles (degenerate ring).")
    faces = tri_index.reshape(-1, 3).astype(np.int64)

    # 5. Lift back to 3D.
    verts_3d = np.column_stack([verts_2d, np.full(len(verts_2d), z)])

    if as_trimesh:
        import trimesh  # deferred import so the core path has no hard dep
        return trimesh.Trimesh(vertices=verts_3d, faces=faces, process=False)
    return verts_3d, faces


def _largest_polygon(geom) -> Polygon:
    """Return the largest Polygon component from a repaired geometry."""
    if geom.geom_type == "Polygon":
        return geom
    polys = [g for g in getattr(geom, "geoms", []) if g.geom_type == "Polygon"]
    if not polys:
        raise ValueError("Repair produced no polygonal geometry.")
    return max(polys, key=lambda g: g.area)


if __name__ == "__main__":
    # Square 10x10 with a central 4x4 hole.
    outer = [(0, 0), (10, 0), (10, 10), (0, 10)]
    hole = [(3, 3), (7, 3), (7, 7), (3, 7)]
    verts, faces = triangulate_face(outer, [hole])
    print(f"{len(verts)} vertices, {len(faces)} triangles")
    print(faces)

Key implementation notes:

• triangulate_float64 needs float64 input. Passing a float32 array raises a type error from the binding. Build the vertex array with dtype=np.float64 explicitly; DXF coordinates are doubles, so this also avoids silent precision loss.
• ring_end_indices are cumulative and exclusive. For a 4-vertex outer ring and a 4-vertex hole, the array is [4, 8], not [0, 4] or [3, 7]. Use np.cumsum over per-ring vertex counts and never include the ring’s closing duplicate point.
• Drop the closing coordinate. Shapely rings repeat the first point at the end; earcut expects open rings, so coords[:-1] prevents a zero-length final edge that becomes a degenerate ear.
• Winding sets the output normal. shapely.geometry.polygon.orient(poly, sign=1.0) forces a counter-clockwise exterior and clockwise holes, so the reshaped faces have consistent, outward-facing winding for trimesh.fix_normals() or glTF back-face culling.
• process=False on trimesh.Trimesh keeps earcut’s topology intact instead of letting trimesh re-merge vertices, which matters when you later map per-vertex attributes back to source ring indices.

Compatibility Matrix

For the algorithm’s guarantees and limits, see the Mapbox earcut reference, whose “not guaranteed correct but always acceptable” contract is worth reading before relying on it for survey-grade areas.

Fallback Strategies

Earcut failures in production trace to four recurring ring defects. Handle them in this order.

1. Invalid or self-touching exterior rings. A ring that touches itself at a single vertex (a “pinch”) is invalid, and earcut will emit overlapping triangles. Detect with polygon.is_valid and repair with make_valid(). Because make_valid can split a pinched ring into a MultiPolygon, keep the largest component (as _largest_polygon does) or triangulate each part separately when both carry real area.

2. Wrong hole orientation or containment. If a hole ring is not fully inside the exterior — a common artifact when DWG hatch islands are exported with a shifted origin — the Shapely Polygon constructor still builds an object, but the triangulation is meaningless. Assert containment with poly.exterior.contains(Polygon(hole)) before flattening, and drop or log holes that fail. Orientation itself is normalized by orient(), so never rely on the source file’s winding.

3. Collinear or degenerate vertices. Three collinear points contribute a zero-area ear that earcut skips, but long runs of near-collinear survey vertices inflate the ear search. Simplify with poly.simplify(tolerance, preserve_topology=True) using a tolerance below your feature resolution (for example 1e-4 m for architectural work) to strip redundant vertices before triangulation.

4. Precision snapping for near-coincident points. Vertices that differ by sub-micron amounts create slivers that pass is_valid yet produce needle triangles. Snap coordinates to a grid before building the polygon:

# numpy>=1.24.0
def snap(coords, tol: float = 1e-6):
    """Round ring coordinates to a tolerance grid to collapse near-duplicates."""
    arr = np.asarray(coords, dtype=np.float64)
    return np.round(arr / tol) * tol

This mirrors the tolerance-based vertex snapping used across the Python Parsing & Geometry Extraction pipeline and keeps earcut output free of zero-area faces that would later fail trimesh.is_watertight.

FAQ

Related Pages

• Geometry Mesh Conversion — parent workflow covering coordinate normalization, topology repair, and mesh export that surrounds this triangulation step
• Converting CAD Polylines to GeoJSON — sibling guide that extracts the closed LWPOLYLINE rings this page triangulates
• Converting 3DFACE Entities to OBJ Meshes — sibling guide for the already-faceted DXF geometry that needs no ear-clipping
• Python Parsing & Geometry Extraction — top-level pipeline covering DXF, IFC, and DWG ingestion feeding this mesh stage
• Reading 3D Solids with ezdxf Python — cross-topic reference for the parametric solids that must be faceted before triangulation applies