hgeometry-0.12.0.4: 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 \log 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

Instances details
 (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

 :: forall p r. (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