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

Copyright(C) Frank Staals
Licensesee the LICENSE file
MaintainerFrank Staals
Safe HaskellNone
LanguageHaskell2010

Algorithms.Geometry.SmallestEnclosingBall.RandomizedIncrementalConstruction

Description

An randomized algorithm to compute the smallest enclosing disk of a set of \(n\) points in \(\mathbb{R}^2\). The expected running time is \(O(n)\).

Synopsis

Documentation

smallestEnclosingDisk :: (Ord r, Fractional r, RandomGen g) => g -> [Point 2 r :+ p] -> DiskResult p r Source #

O(n) expected time algorithm to compute the smallest enclosing disk of a set of points. we need at least two points. implemented using randomized incremental construction

smallestEnclosingDisk' :: (Ord r, Fractional r) => (Point 2 r :+ p) -> (Point 2 r :+ p) -> [Point 2 r :+ p] -> DiskResult p r Source #

Smallest enclosing disk.

smallestEnclosingDiskWithPoint :: (Ord r, Fractional r) => (Point 2 r :+ p) -> NonEmpty (Point 2 r :+ p) -> DiskResult p r Source #

Smallest enclosing disk, given that p should be on it.

smallestEnclosingDiskWithPoints :: (Ord r, Fractional r) => (Point 2 r :+ p) -> (Point 2 r :+ p) -> [Point 2 r :+ p] -> DiskResult p r Source #

Smallest enclosing disk, given that p and q should be on it

initial :: Fractional r => (Point 2 r :+ p) -> (Point 2 r :+ p) -> DiskResult p r Source #

Constructs the initial DiskResult from two points