Algorithms.Geometry.ClosestPair.DivideAndConquer

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

Documentation

closestPair :: (Ord r, Num r) => LSeq 2 (Point 2 r :+ p) -> Two (Point 2 r :+ p)

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)

the closest pair and its (squared) distance

data CCP p r

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)

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)

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)

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

mergeSortedBy :: (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a -> NonEmpty a

Given an ordering and two nonempty sequences ordered according to that ordering, merge them

mergePairs

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

Given some function that decides when to keep things while maintaining some state.

minBy :: Ord b => (a -> b) -> a -> a -> a

returns the minimum element according to some function.

getDist :: CP a r -> Top r

Get the distance of a (candidate) closest pair