Safe Haskell	None
Language	GHC2021

AtCoder.Extra.KdTree

Contents

K-dimensional tree
Constructors

Description

Static, \(k\)-dimensional tree \((k = 2)\).

Points are fixed on build and cannot be moved or added later.
Multiple points can exist at the same coordinate.

Examples

Expand

>>> import AtCoder.Extra.KdTree qualified as KT
>>> import Data.Vector.Unboxed qualified as VU
>>> let xys = VU.fromList [(0, 0), (1, 1), (4, 2)]
>>> let kt = KT.build2 xys
>>> -- Find point indices in [0, 2) x [0, 2) with maximum capacity 3
>>> KT.findPointsIn kt 0 2 0 2 3
[0,1]

>>> KT.findNearestPoint kt 3 3
Just 2

Since: 1.2.2.0

Synopsis

data KdTree = KdTree {
- nKt :: !Int
- incRectsKt :: !(Vector (Int, Int, Int, Int))
- dataKt :: !(Vector Int)
}
build :: HasCallStack => Vector Int -> Vector Int -> KdTree
build2 :: HasCallStack => Vector (Int, Int) -> KdTree
findPointsIn :: HasCallStack => KdTree -> Int -> Int -> Int -> Int -> Int -> Vector Int
findNearestPoint :: HasCallStack => KdTree -> Int -> Int -> Maybe Int

K-dimensional tree

data KdTree Source #

Static, \(k\)-dimensional tree \((k = 2)\).

Since: 1.2.2.0

Constructors

KdTree
Fields nKt :: !Int The number of points in the \(k\)-d tree. Since: 1.2.2.0 incRectsKt :: !(Vector (Int, Int, Int, Int)) Rectangle information: inclusive (closed) ranges \([x_1, x_2) \times [y_1, y_2)\). Since: 1.2.2.0 dataKt :: !(Vector Int) Maps rectangle index to original point index. Since: 1.2.2.0

Constructors

build Source #

Arguments

:: HasCallStack
=> Vector Int	\(x\) coordnates
-> Vector Int	\(y\) coordnates
-> KdTree	`KdTree`

\(O(n \log n)\) Creates a KdTree from \(x\) and \(y\) vectors.

Constraints

\(|\mathrm{xs}| = |\mathrm{ys}|\).

Since: 1.2.2.0

build2 Source #

Arguments

:: HasCallStack
=> Vector (Int, Int)	\(x, y\) coordnates
-> KdTree	`KdTree`

\(O(n \log n)\) Creates KdTree from a \((x, y)\) vector.

Since: 1.2.2.0

findPointsIn Source #

Arguments

:: HasCallStack
=> KdTree	`KdTree`
-> Int	\(x_1\)
-> Int	\(x_2\)
-> Int	\(y_1\)
-> Int	\(y_2\)
-> Int	Maximum number of points in \([x_1, x_2) \times [y_1, y_2)\).
-> Vector Int	Point indices in \([x_1, x_2) \times [y_1, y_2)\).

\(O(n)\) Collects points in \([x_1, x_2) \times [y_1, y_2)\).

Since: 1.2.2.0

findNearestPoint Source #

Arguments

:: HasCallStack
=> KdTree	`KdTree`
-> Int	\(x\)
-> Int	\(y\)
-> Maybe Int	The nearest point index.

\(O(\log n)\), only if the points are randomly distributed. Returns the index of the nearest point, or Nothing if the KdTree has no point.

Since: 1.2.2.0