hgeometry-0.12.0.1: Geometric Algorithms, Data structures, and Data types.
Copyright(C) Frank Staals
Licensesee the LICENSE file
MaintainerFrank Staals
Safe HaskellNone
LanguageHaskell2010

Data.Geometry.PrioritySearchTree

Description

Implements a linear size data structure for three-sided range queries in \(\mathbb{R}^2\). See

McCreight, Edward (May 1985). "Priority search trees". SIAM Journal on Scientific Computing. 14 (2): 257-276.

for more details.

Synopsis

Documentation

newtype PrioritySearchTree p r Source #

A priority search tree storing points in (mathbb{R}^2) that have an additional payload of type p.

Constructors

PrioritySearchTree 

Fields

Instances

Instances details
Bifunctor PrioritySearchTree Source # 
Instance details

Defined in Data.Geometry.PrioritySearchTree

Methods

bimap :: (a -> b) -> (c -> d) -> PrioritySearchTree a c -> PrioritySearchTree b d #

first :: (a -> b) -> PrioritySearchTree a c -> PrioritySearchTree b c #

second :: (b -> c) -> PrioritySearchTree a b -> PrioritySearchTree a c #

(Eq r, Eq p) => Eq (PrioritySearchTree p r) Source # 
Instance details

Defined in Data.Geometry.PrioritySearchTree

(Show r, Show p) => Show (PrioritySearchTree p r) Source # 
Instance details

Defined in Data.Geometry.PrioritySearchTree

createTree :: Ord r => NonEmpty (Point 2 r :+ p) -> PrioritySearchTree p r Source #

Creates a Priority Search Tree for 3-sided range queries of the form \([x_l,x_r] \times [y,\infty)\).

the base tree will be static.

pre: all points have unique x-coordinates

running time: \(O(n\log n)\)

queryRange :: Ord r => (Range r, r) -> PrioritySearchTree p r -> [Point 2 r :+ p] Source #

Given a three sided range \([x_l,x_r],y\) report all points in the range \([x_l,x_r] \times [y,\infty)\). The points are reported in decreasing order of \(y\)-coordinate.

running time: \(O(\log n + k)\), where \(k\) is the number of reported points.