Algorithms.Geometry.PolygonTriangulation.EarClip

Ear clipping triangulation algorithms. The baseline algorithm runs in \( O(n^2) \) but has a low constant factor overhead. The z-order hashed variant runs in \( O(n \log n) \).

References:

1. https://en.wikipedia.org/wiki/Polygon_triangulation#Ear_clipping_method
2. https://en.wikipedia.org/wiki/Z-order_curve

Documentation

earClip :: (Num r, Ord r) => SimplePolygon p r -> [(Int, Int, Int)]

\( O(n^2) \)

Returns triangular faces using absolute polygon point indices.

earClipRandom :: (Num r, Ord r) => SimplePolygon p r -> [(Int, Int, Int)]

\( O(n^2) \)

Returns triangular faces using absolute polygon point indices.

earClipHashed :: Real r => SimplePolygon p r -> [(Int, Int, Int)]

\( O(n \log n) \) expected time.

Returns triangular faces using absolute polygon point indices.

earClipRandomHashed :: Real r => SimplePolygon p r -> [(Int, Int, Int)]

\( O(n \log n) \) expected time.

Returns triangular faces using absolute polygon point indices.

zHash :: V2 Word -> Word

O(1) Z-Order hash the first half-world of each coordinate.

zUnHash :: Word -> V2 Word

O(1) Reverse z-order hash.