earcutx

mapbox_earcut

Python bindings for the C++ implementation of the Mapbox Earcut library, which provides very fast and quite robust triangulation of 2D polygons.

Original code: earcut.hpp

Original description:

The library implements a modified ear slicing algorithm, optimized by z-order curve hashing and extended to handle holes, twisted polygons, degeneracies and self-intersections in a way that doesn't guarantee correctness of triangulation, but attempts to always produce acceptable results for practical data like geographical shapes.

Provided functions (depending on dtype of vertex data):

triangulate_float32
triangulate_float64
triangulate_int32
triangulate_int64

Example:

import mapbox_earcut as earcut
import numpy as np

# A Nx2 array of vertices. Must be 2D.
verts = np.array([[0, 0], [1, 0], [1, 1]]).reshape(-1, 2)

# An array of end-indices for each ring.
# The first ring is the outer contour of the polygon.
# Subsequent ones are holes.
# This implies that the last index must always be equal to the size of verts!
rings = np.array([3])

result = earcut.triangulate_float32(verts, rings)

# Result is an np.ndarray with dtype np.uint32 and shape (3,)
# containing indices into the verts array.

print(verts[result])
# [[1 0]
#  [1 1]
#  [0 0]]