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

Copyright(C) Frank Staals
Licensesee the LICENSE file
MaintainerFrank Staals
Safe HaskellNone
LanguageHaskell2010

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

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 #

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

mergePairs Source #

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.

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

returns the minimum element according to some function.

getDist :: CP a r -> Top r Source #

Get the distance of a (candidate) closest pair