Algorithms.Geometry.ConvexHull.Naive

Documentation

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

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

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

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)

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

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}}