hgeometry-0.12.0.0: Geometric Algorithms, Data structures, and Data types.
Copyright(C) David Himmelstrup
Licensesee the LICENSE file
MaintainerDavid Himmelstrup
Safe HaskellNone
LanguageHaskell2010

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:

  1. https://en.wikipedia.org/wiki/Polygon_triangulation#Ear_clipping_method
  2. https://en.wikipedia.org/wiki/Z-order_curve
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.

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.