| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| Language | Haskell2010 |
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
- smallestEnclosingDisk :: (Ord r, Fractional r, RandomGen g) => g -> [Point 2 r :+ p] -> DiskResult p r
- smallestEnclosingDisk' :: (Ord r, Fractional r) => (Point 2 r :+ p) -> (Point 2 r :+ p) -> [Point 2 r :+ p] -> DiskResult p r
- smallestEnclosingDiskWithPoint :: (Ord r, Fractional r) => (Point 2 r :+ p) -> NonEmpty (Point 2 r :+ p) -> DiskResult p r
- smallestEnclosingDiskWithPoints :: (Ord r, Fractional r) => (Point 2 r :+ p) -> (Point 2 r :+ p) -> [Point 2 r :+ p] -> DiskResult p r
- initial :: Fractional r => (Point 2 r :+ p) -> (Point 2 r :+ p) -> DiskResult p r
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