Copyright	(C) David Himmelstrup
License	see the LICENSE file
Maintainer	David Himmelstrup
Safe Haskell	None
Language	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

earClip :: (Num r, Ord r) => SimplePolygon p r -> [(Int, Int, Int)]
earClipRandom :: (Num r, Ord r) => SimplePolygon p r -> [(Int, Int, Int)]
earClipHashed :: Real r => SimplePolygon p r -> [(Int, Int, Int)]
earClipRandomHashed :: Real r => SimplePolygon p r -> [(Int, Int, Int)]
zHash :: V2 Word -> Word
zUnHash :: Word -> V2 Word

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.

zHash :: V2 Word -> Word Source #

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

zUnHash :: Word -> V2 Word Source #

O(1) Reverse z-order hash.

Key	Shortcut
s	Open this search box
esc	Close this search box
↓,ctrl + j	Move down in search results
↑,ctrl + k	Move up in search results
↵	Go to active search result