| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| Language | Haskell2010 |
Algorithms.Geometry.ClosestPair.DivideAndConquer
Description
Classical \(O(n\log n)\) time divide and conquer algorithm to compute the closest pair among a set of \(n\) points in \(\mathbb{R}^2\).
Synopsis
- closestPair :: (Ord r, Num r) => LSeq 2 (Point 2 r :+ p) -> Two (Point 2 r :+ p)
- type CP q r = Top (SP (Two q) r)
- data CCP p r = CCP (NonEmpty (Point 2 r :+ p)) !(CP (Point 2 r :+ p) r)
- mergeSortedBy :: (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a -> NonEmpty a
- mergePairs :: forall p r. (Ord r, Num r) => CP (Point 2 r :+ p) r -> NonEmpty (Point 2 r :+ p) -> NonEmpty (Point 2 r :+ p) -> CP (Point 2 r :+ p) r
- runWhile :: s -> [a] -> (s -> a -> Bool) -> (s -> a -> s) -> s
- minBy :: Ord b => (a -> b) -> a -> a -> a
- getDist :: CP a r -> Top r
Documentation
closestPair :: (Ord r, Num r) => LSeq 2 (Point 2 r :+ p) -> Two (Point 2 r :+ p) Source #
Classical divide and conquer algorithm to compute the closest pair among \(n\) points.
running time: \(O(n)\)
Type used in the closest pair computation. The fields represent the points ordered on increasing y-order and the closest pair (if we know it)
mergeSortedBy :: (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a -> NonEmpty a Source #
Given an ordering and two nonempty sequences ordered according to that ordering, merge them
Arguments
| :: (Ord r, Num r) | |
| => CP (Point 2 r :+ p) r | current closest pair and its dist |
| -> NonEmpty (Point 2 r :+ p) | pts on the left |
| -> NonEmpty (Point 2 r :+ p) | pts on the right |
| -> CP (Point 2 r :+ p) r |
Function that does the actual merging work
runWhile :: s -> [a] -> (s -> a -> Bool) -> (s -> a -> s) -> s Source #
Given some function that decides when to keep things while maintaining some state.