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

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

# 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 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 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 MethodsshowsPrec :: 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 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

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

mergeSortedListsBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a] Source #

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