hgeometry-0.12.0.4: Geometric Algorithms, Data structures, and Data types.
Copyright (C) David Himmelstrup see the LICENSE file David Himmelstrup None Haskell2010

Algorithms.Geometry.PolygonTriangulation.EarClip

Description

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:

Synopsis

# Documentation

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

$$O(n^2)$$

Returns triangular faces using absolute polygon point indices.

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

$$O(n^2)$$

Returns triangular faces using absolute polygon point indices.

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

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

Returns triangular faces using absolute polygon point indices.

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

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

Returns triangular faces using absolute polygon point indices.

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

O(1) Reverse z-order hash.