Safe Haskell	Safe-Inferred
Language	GHC2021

AtCoder.Extra.KdTree

Contents

K-dimensional tree
Constructors

Description

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

Points are fixed on build.
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.

Constraints

$|\mathrm{xs}| = |\mathrm{ys}|$ .

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

Key	Shortcut
s	Open this search box
esc	Close this search box
↓,ctrl + j	Move down in search results
↑,ctrl + k	Move up in search results
↵	Go to active search result