Copyright | (C) Frank Staals |
---|---|

License | see the LICENSE file |

Maintainer | Frank Staals |

Safe Haskell | None |

Language | Haskell2010 |

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
- mergeSortedBy :: (a -> a -> Ordering) -> NonEmpty a -> NonEmpty a -> NonEmpty a
- mergeSortedListsBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a]

# 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 used in the closest pair computation. The fields represent the points ordered on increasing y-order and the closest pair (if we know it)

:: (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