rtree: Rectangle tree for fast point cloud data query

moraine.api.rtree (source). Every name is also moraine.<name> (import moraine as mr).

HilbertRtree

HilbertRtree(bounds_tree: ndarray, n_points: int, page_size=512)

This class provides a read-only Hilbert R-tree for spatial indexing.

See Hilbert_R-tree for more info on the Hilbert R-tree.

This implementation stores the R-tree as an array representation of a binary tree. See Binary_tree for more info on the array representation of a binary tree.

Note that HilbertRtree should not be instantiated directly, but always through the module-level function build and load.

Parameters:

Name	Type	Description	Default
bounds_tree	ndarray	an array representation of a binary tree. shape [n_pages, 4]. Every row is a bounding box of a node: [x0, y0, xm, ym]	required
n_points	int	number of total points	required
page_size	default: 512	number of points in every leaf node.	512

build classmethod

build(x: ndarray, y: ndarray, page_size=512)

classmethod to build a HilbertRtree.

Parameters:

Name	Type	Description	Default
x	ndarray	x coordinates, e.g., lon, shape [n_points,]	required
y	ndarray	y coordinates, e.g., lat, shape [n_points,]	required
page_size	default: 512	number of points in every leaf node. should be same as pc_chunk_size.	512

save

save(path: str)

Save the HilbertRtree.

Parameters:

Name	Type	Description	Default
path	str	zarr path	required

load classmethod

load(zarr_path: str)

classmethod to load the saved HilbertRtree.

Parameters:

Name	Type	Description	Default
zarr_path	str	zarr path	required

maybe_covered_ranges

maybe_covered_ranges(bounds: tuple | list) -> tuple

Get the ranges that may be within the query box.

Parameters:

Name	Type	Description	Default
bounds	tuple | list	data query bounding box, [x0, y0, xm, ym]	required

Returns:

Type	Description
tuple	array of ranges that may be covered by the query bounding box, shape[n_range, 2]. Every row [start, stop] is the range of query data Bool array indicating if fully convered, shape[n_range,]. True: fully covered (every point in this range are in the box). False: some of points may be in the box.

bbox_query

bbox_query(bounds: tuple | list, x: ndarray | Array, y: ndarray | Array)

get the index of points that are in the bounding box.

Parameters:

Name	Type	Description	Default
bounds	tuple | list	data query bounding box, [x0, y0, xm, ym]	required
x	ndarray | Array	x coordinate	required
y	ndarray | Array	y coordinate	required

Examples

Run when this manual is built; the output follows each snippet.

import numpy as np
import moraine as mr

rng = np.random.default_rng(0)
x, y = rng.random(3000), rng.random(3000)                        # e.g. longitude, latitude of points
tree = mr.HilbertRtree.build(x, y, page_size=64)                 # page_size: points per leaf (the chunk size of the point cloud)
idx = tree.bbox_query([0.2, 0.2, 0.4, 0.4], x, y)                # indices of the points in the box [x0, y0, xm, ym]
print(len(idx), idx[:5])
print(np.all((x[idx] >= 0.2) & (x[idx] <= 0.4) & (y[idx] >= 0.2) & (y[idx] <= 0.4)))

112 [18 41 44 64 68]
True

tree.save(path) / HilbertRtree.load(path) keep the tree as a zarr array next to a point cloud; the viewer uses it to read only the points on screen.