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

Documentation

Classical divide and conquer algorithm to compute the closest pair among \(n\) points.

running time: \(O(n)\)

type CP q r = Top (SP (Two q) r) Source #

the closest pair and its (squared) distance

data CCP p r Source #

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)

Constructors

CCP (NonEmpty (Point 2 r :+ p)) !(CP (Point 2 r :+ p) r)

Instances

(Eq r, Eq p) => Eq (CCP p r) Source #
Instance details Defined in Algorithms.Geometry.ClosestPair.DivideAndConquer Methods (==) :: CCP p r -> CCP p r -> Bool # (/=) :: CCP p r -> CCP p r -> Bool #
(Show r, Show p) => Show (CCP p r) Source #
Instance details Defined in Algorithms.Geometry.ClosestPair.DivideAndConquer Methods showsPrec :: Int -> CCP p r -> ShowS # show :: CCP p r -> String # showList :: [CCP p r] -> ShowS #
(Num r, Ord r) => Semigroup (CCP p r) Source #
Instance details Defined in Algorithms.Geometry.ClosestPair.DivideAndConquer Methods (<>) :: CCP p r -> CCP p r -> CCP p r # sconcat :: NonEmpty (CCP p r) -> CCP p r # stimes :: Integral b => b -> CCP p r -> CCP p r #

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