hgeometry-0.12.0.4: Geometric Algorithms, Data structures, and Data types.

Algorithms.Geometry.ConvexHull.Naive

Description

Synopsis

# Documentation

type ConvexHull d p r = [Triangle 3 p r] Source #

lowerHull' :: forall r p. (Ord r, Fractional r, Show r) => NonEmpty (Point 3 r :+ p) -> ConvexHull 3 p r Source #

Computes the lower hull without its vertical triangles.

pre: The points are in general position. In particular, no four points should be coplanar.

running time: $$O(n^4)$$

lowerHullAll :: forall r p. (Ord r, Fractional r, Show r) => NonEmpty (Point 3 r :+ p) -> ConvexHull 3 p r Source #

Generates a set of triangles to be used to construct a complete convex hull. In particular, it may contain vertical triangles.

pre: The points are in general position. In particular, no four points should be coplanar.

running time: $$O(n^4)$$

isValidTriangle :: (Num r, Ord r) => Triangle 3 p r -> [Point 3 r :+ q] -> Maybe (Point 3 r :+ q) Source #

Tests if this is a valid triangle for the lower envelope. That is, if all point lie above the plane through these points. Returns a Maybe; if the result is a Nothing the triangle is valid, if not it returns a counter example.

>>> let t = (Triangle (ext origin) (ext $Point3 1 0 0) (ext$ Point3 0 1 0))
>>> isValidTriangle t [ext $Point3 5 5 0] Nothing >>> let t = (Triangle (ext origin) (ext$ Point3 1 0 0) (ext $Point3 0 1 0)) >>> isValidTriangle t [ext$ Point3 5 5 (-10)]
Just (Point3 5 5 (-10) :+ ())


upperHalfSpaceOf :: (Ord r, Num r) => Triangle 3 p r -> HalfSpace 3 r Source #

Computes the halfspace above the triangle.

>>> upperHalfSpaceOf (Triangle (ext $origin) (ext$ Point3 10 0 0) (ext \$ Point3 0 10 0))
HalfSpace {_boundingPlane = HyperPlane {_inPlane = Point3 0 0 0, _normalVec = Vector3 0 0 100}}