Containers

Spatial data structures for efficient nearest neighbor queries.

Containers module.

This module provides spatial data structures for efficient nearest neighbor queries, spatial indexing, and tracking containers.

Spatial Index Hierarchy

All spatial index structures inherit from BaseSpatialIndex which defines a common interface for k-nearest neighbor and radius queries:

BaseSpatialIndex (abstract) ├── KDTree - K-dimensional tree (Euclidean space) ├── BallTree - Ball tree variant of KD-tree ├── RTree - Rectangle tree for bounding boxes └── MetricSpatialIndex (abstract)

├── VPTree - Vantage point tree (any metric) └── CoverTree - Cover tree (any metric)

class pytcl.containers.BaseSpatialIndex(data)

Bases: ABC

Abstract base class for spatial indexing data structures.

All spatial index implementations (KDTree, VPTree, RTree, CoverTree) should inherit from this class and implement the required methods.

This provides a consistent interface for: - Building the index from point data - k-nearest neighbor queries - Range/radius queries - Dimension and size introspection

Parameters:

data (array_like) – Data points of shape (n_samples, n_features).

data

The indexed data points.

Type:

ndarray

n_samples

Number of data points.

Type:

int

n_features

Dimensionality of data points.

Type:

int

__init__(data)

abstractmethod query(X, k=1)

Query the index for k nearest neighbors.

Parameters:

• X (array_like) – Query points of shape (n_queries, n_features) or (n_features,).

• k (int, optional) – Number of nearest neighbors to return. Default is 1.

Returns:

result – Named tuple with indices and distances of k nearest neighbors for each query point.

Return type:

NeighborResult

abstractmethod query_radius(X, r)

Query the index for all points within radius r.

Parameters:

• X (array_like) – Query points of shape (n_queries, n_features) or (n_features,).

• r (float) – Search radius.

Returns:

indices – For each query point, a list of indices of data points within distance r.

Return type:

list of list of int

query_ball_point(X, r)

Query the index for all points within radius r.

This is an alias for query_radius() provided for compatibility with scipy.spatial.KDTree.

Parameters:

• X (array_like) – Query points of shape (n_queries, n_features) or (n_features,).

• r (float) – Search radius.

Returns:

indices – For each query point, a list of indices of data points within distance r.

Return type:

list of list of int

See also

query_radius

The underlying implementation.

__len__()

Return number of indexed points.

class pytcl.containers.MetricSpatialIndex(data, metric=None)

Bases: BaseSpatialIndex

Base class for metric space spatial indices.

Extends BaseSpatialIndex with support for custom distance metrics. Used by VP-trees and Cover trees which can work with any metric.

Parameters:

• data (array_like) – Data points of shape (n_samples, n_features).

• metric (callable, optional) – Distance function with signature metric(x, y) -> float. Default is Euclidean distance.

__init__(data, metric=None)

class pytcl.containers.NeighborResult(indices, distances)

Bases: NamedTuple

Unified result type for spatial index queries.

All spatial index implementations (KDTree, BallTree, VPTree, CoverTree, RTree) return this type from their query methods, ensuring a consistent interface across the library.

indices

Indices of the k nearest neighbors in the original data array. For k=1, may be 1D. For k>1, shape is (n_queries, k).

Type:

ndarray of shape (n_queries, k) or (n_queries,)

distances

Distances to the k nearest neighbors. Same shape as indices.

Type:

ndarray of shape (n_queries, k) or (n_queries,)

Examples

>>> from pytcl.containers import KDTree
>>> import numpy as np
>>> points = np.array([[0, 0], [1, 0], [0, 1], [1, 1]])
>>> tree = KDTree(points)
>>> result = tree.query([[0.1, 0.1]], k=2)
>>> result.indices
array([[0, 2]])
>>> result.distances
array([[0.14142136, 0.9       ]])

See also

BaseSpatialIndex

Abstract base class for spatial indices.

indices: ndarray[tuple[Any, ...], dtype[int64]]

Alias for field number 0

distances: ndarray[tuple[Any, ...], dtype[floating]]

Alias for field number 1

pytcl.containers.validate_query_input(X, n_features)

Validate and reshape query input.

Parameters:

• X (array_like) – Query points.

• n_features (int) – Expected number of features.

Returns:

X – Validated query array of shape (n_queries, n_features).

Return type:

ndarray

Raises:

ValueError – If query has wrong number of features.

pytcl.containers.SpatialQueryResult

alias of NeighborResult

pytcl.containers.NearestNeighborResult

alias of NeighborResult

pytcl.containers.VPTreeResult

alias of NeighborResult

pytcl.containers.CoverTreeResult

alias of NeighborResult

class pytcl.containers.KDNode(point, index, split_dim)

Bases: object

A node in the k-d tree.

point

The point stored at this node.

Type:

ndarray

index

Original index of this point in the data array.

Type:

int

split_dim

The dimension used for splitting at this node.

Type:

int

left

Left child (points with smaller split dimension value).

Type:

KDNode or None

right

Right child (points with larger split dimension value).

Type:

KDNode or None

__init__(point, index, split_dim)

point

index

split_dim

left: KDNode | None

right: KDNode | None

class pytcl.containers.KDTree(data, leaf_size=10)

Bases: BaseSpatialIndex

K-D Tree for efficient spatial queries.

A k-d tree recursively partitions space by splitting along different dimensions at each level. This enables O(log n) average-case nearest neighbor queries.

Parameters:

• data (array_like) – Data points of shape (n_samples, n_features).

• leaf_size (int, optional) – Maximum number of points in a leaf node. Default 10.

Examples

>>> import numpy as np
>>> points = np.array([[0, 0], [1, 0], [0, 1], [1, 1]])
>>> tree = KDTree(points)
>>> result = tree.query(np.array([[0.1, 0.1]]), k=2)
>>> result.indices
array([[0, 1]])

Notes

The tree is balanced by choosing the median point along the split dimension at each level, giving O(n log n) construction time.

Query complexity is O(log n) on average for nearest neighbor search, though worst case is O(n) for highly unbalanced queries.

See also

BaseSpatialIndex

Abstract base class defining the spatial index interface.

BallTree

Alternative spatial index using hyperspheres.

__init__(data, leaf_size=10)

query(X, k=1)

Query the tree for k nearest neighbors.

Parameters:

• X (array_like) – Query points of shape (n_queries, n_features) or (n_features,).

• k (int, optional) – Number of nearest neighbors. Default 1.

Returns:

result – Indices and distances of k nearest neighbors for each query.

Return type:

NeighborResult

Examples

>>> tree = KDTree(np.array([[0, 0], [1, 1], [2, 2]]))
>>> result = tree.query([[0.5, 0.5]], k=2)
>>> result.indices
array([[0, 1]])

query_radius(X, r)

Query the tree for all points within radius r.

Parameters:

• X (array_like) – Query points of shape (n_queries, n_features) or (n_features,).

• r (float) – Query radius.

Returns:

indices – For each query, a list of indices of points within radius r.

Return type:

list of lists

Examples

>>> tree = KDTree(np.array([[0, 0], [1, 0], [0, 1], [5, 5]]))
>>> tree.query_radius([[0, 0]], r=1.5)
[[0, 1, 2]]

class pytcl.containers.BallTree(data, leaf_size=10)

Bases: BaseSpatialIndex

Ball Tree for efficient spatial queries.

A ball tree partitions space using hyperspheres (balls), which can be more efficient than k-d trees for high-dimensional data or non-Euclidean metrics.

Parameters:

• data (array_like) – Data points of shape (n_samples, n_features).

• leaf_size (int, optional) – Maximum number of points in a leaf node. Default 10.

Examples

>>> import numpy as np
>>> points = np.array([[0, 0], [1, 0], [0, 1], [1, 1]])
>>> tree = BallTree(points)
>>> result = tree.query(np.array([[0.1, 0.1]]), k=2)

Notes

Ball trees have O(n log n) construction and O(log n) average-case query time. They can outperform k-d trees in high dimensions.

See also

BaseSpatialIndex

Abstract base class defining the spatial index interface.

KDTree

Alternative spatial index using axis-aligned splits.

__init__(data, leaf_size=10)

query(X, k=1)

Query the tree for k nearest neighbors.

Parameters:

• X (array_like) – Query points of shape (n_queries, n_features) or (n_features,).

• k (int, optional) – Number of nearest neighbors. Default 1.

Returns:

result – Indices and distances of k nearest neighbors.

Return type:

NeighborResult

query_radius(X, r)

Query the tree for all points within radius r.

Parameters:

• X (array_like) – Query points of shape (n_queries, n_features) or (n_features,).

• r (float) – Query radius.

Returns:

indices – For each query, a list of indices of points within radius r.

Return type:

list of lists

class pytcl.containers.BoundingBox(min_coords, max_coords)

Bases: NamedTuple

Axis-aligned bounding box.

min_coords

Minimum coordinates in each dimension.

Type:

ndarray

max_coords

Maximum coordinates in each dimension.

Type:

ndarray

min_coords: ndarray[tuple[Any, ...], dtype[floating]]

Alias for field number 0

max_coords: ndarray[tuple[Any, ...], dtype[floating]]

Alias for field number 1

property center: ndarray[tuple[Any, ...], dtype[floating]]

Center point of the bounding box.

property dimensions: ndarray[tuple[Any, ...], dtype[floating]]

Size in each dimension.

property volume: float

Volume (area in 2D) of the bounding box.

contains_point(point)

Check if box contains a point.

intersects(other)

Check if this box intersects another.

contains_box(other)

Check if this box fully contains another.

pytcl.containers.merge_boxes(boxes)

Compute minimum bounding box containing all boxes.

pytcl.containers.box_from_point(point)

Create a zero-volume bounding box from a point.

pytcl.containers.box_from_points(points)

Create minimum bounding box containing all points.

class pytcl.containers.RTreeNode(is_leaf=True)

Bases: object

Node in an R-tree.

bbox

Bounding box of this node.

Type:

BoundingBox

is_leaf

Whether this is a leaf node.

Type:

bool

children

Child nodes (for internal nodes).

Type:

list

entries

(bbox, data_index) pairs (for leaf nodes).

Type:

list

__init__(is_leaf=True)

is_leaf

children: List[RTreeNode]

entries: List[Tuple[BoundingBox, int]]

bbox: BoundingBox | None

parent: RTreeNode | None

update_bbox()

Update bounding box to contain all children/entries.

class pytcl.containers.RTreeResult(indices, boxes)

Bases: NamedTuple

Result of R-tree query.

indices

Indices of matching entries.

Type:

list

boxes

Bounding boxes of matching entries.

Type:

list

indices: List[int]

Alias for field number 0

boxes: List[BoundingBox]

Alias for field number 1

class pytcl.containers.RTree(max_entries=10, min_entries=None)

Bases: object

R-tree for spatial indexing of bounding boxes.

An R-tree groups nearby objects and represents them with their minimum bounding rectangle. This allows efficient spatial queries.

Unlike KDTree and BallTree which only index points, RTree can index bounding boxes of arbitrary size. It also supports dynamic insertion.

Parameters:

• max_entries (int, optional) – Maximum entries per node. Default 10.

• min_entries (int, optional) – Minimum entries per node (except root). Default max_entries // 2.

n_entries

Number of entries in the tree.

Type:

int

n_features

Dimensionality of the data (set after first insertion).

Type:

int

Examples

>>> tree = RTree()
>>> tree.insert(BoundingBox(np.array([0, 0]), np.array([1, 1])), 0)
>>> tree.insert(BoundingBox(np.array([2, 2]), np.array([3, 3])), 1)
>>> query_box = BoundingBox(np.array([0.5, 0.5]), np.array([2.5, 2.5]))
>>> result = tree.query_intersect(query_box)

Notes

This implementation uses a simplified insertion algorithm. For production use, consider using R*-tree or packed R-tree variants.

See also

KDTree

Point-based spatial index using axis-aligned splits.

BallTree

Point-based spatial index using hyperspheres.

__init__(max_entries=10, min_entries=None)

n_features: int | None

classmethod from_points(data, max_entries=10, min_entries=None)

Create an RTree from point data.

This factory method provides an interface similar to KDTree and BallTree, allowing RTree to be used interchangeably for point queries.

Parameters:

• data (array_like) – Data points of shape (n_samples, n_features).

• max_entries (int, optional) – Maximum entries per node. Default 10.

• min_entries (int, optional) – Minimum entries per node. Default max_entries // 2.

Returns:

tree – RTree with all points inserted.

Return type:

RTree

Examples

>>> points = np.array([[0, 0], [1, 0], [0, 1], [1, 1]])
>>> tree = RTree.from_points(points)
>>> result = tree.query([[0.1, 0.1]], k=2)

insert(bbox, data_index=None)

Insert a bounding box into the tree.

Parameters:

• bbox (BoundingBox) – Bounding box to insert.

• data_index (int, optional) – Index to associate with this box. If None, uses next available.

Returns:

index – Index of the inserted entry.

Return type:

int

insert_point(point, data_index=None)

Insert a point as a zero-volume bounding box.

insert_points(points)

Insert multiple points.

query(X, k=1)

Query the tree for k nearest neighbors.

This method provides API compatibility with KDTree and BallTree.

Parameters:

• X (array_like) – Query points of shape (n_queries, n_features) or (n_features,).

• k (int, optional) – Number of nearest neighbors. Default 1.

Returns:

result – Indices and distances of k nearest neighbors for each query.

Return type:

NeighborResult

Examples

>>> tree = RTree.from_points(np.array([[0, 0], [1, 1], [2, 2]]))
>>> result = tree.query([[0.5, 0.5]], k=2)
>>> result.indices
array([[0, 1]])

query_radius(X, r)

Query the tree for all points within radius r.

This method provides API compatibility with KDTree and BallTree.

Parameters:

• X (array_like) – Query points of shape (n_queries, n_features) or (n_features,).

• r (float) – Query radius.

Returns:

indices – For each query, a list of indices of points within radius r.

Return type:

list of lists

Examples

>>> tree = RTree.from_points(np.array([[0, 0], [1, 0], [0, 1], [5, 5]]))
>>> tree.query_radius([[0, 0]], r=1.5)
[[0, 1, 2]]

query_ball_point(X, r)

Query the tree for all points within radius r.

This is an alias for query_radius() provided for compatibility with scipy.spatial.KDTree.

Parameters:

• X (array_like) – Query points of shape (n_queries, n_features) or (n_features,).

• r (float) – Search radius.

Returns:

indices – For each query point, a list of indices of data points within distance r.

Return type:

list of list of int

See also

query_radius

The underlying implementation.

query_intersect(query_bbox)

Find all entries intersecting a query box.

Parameters:

query_bbox (BoundingBox) – Query bounding box.

Returns:

result – Indices and boxes of intersecting entries.

Return type:

RTreeResult

query_contains(query_bbox)

Find all entries contained within a query box.

Parameters:

query_bbox (BoundingBox) – Query bounding box.

Returns:

result – Indices and boxes of contained entries.

Return type:

RTreeResult

query_point(point)

Find all entries containing a point.

Parameters:

point (array_like) – Query point.

Returns:

result – Indices and boxes of entries containing the point.

Return type:

RTreeResult

nearest(query_point, k=1)

Find k nearest entries to a query point.

Parameters:

• query_point (array_like) – Query point.

• k (int, optional) – Number of nearest neighbors. Default 1.

Returns:

• indices (list) – Indices of nearest entries.

• distances (list) – Distances to nearest entries.

Return type:

Tuple[List[int], List[float]]

class pytcl.containers.VPNode(index, radius=0.0)

Bases: object

Node in a VP-tree.

index

Index of the vantage point in the original data.

Type:

int

radius

Median distance to vantage point (splitting threshold).

Type:

float

left

Left subtree (points closer than radius).

Type:

VPNode or None

right

Right subtree (points farther than radius).

Type:

VPNode or None

__init__(index, radius=0.0)

index

radius

left: VPNode | None

right: VPNode | None

class pytcl.containers.VPTree(data, metric=None)

Bases: MetricSpatialIndex

Vantage Point Tree for metric space nearest neighbor search.

A VP-tree recursively partitions space by selecting a vantage point and dividing remaining points into those closer than a threshold (median distance) and those farther.

Parameters:

• data (array_like) – Data points of shape (n_samples, n_features).

• metric (callable, optional) – Distance function metric(x, y) -> float. Default is Euclidean distance.

Examples

>>> import numpy as np
>>> points = np.random.rand(100, 3)
>>> tree = VPTree(points)
>>> result = tree.query(points[:5], k=3)
>>> result.indices.shape
(5, 3)

Notes

VP-trees can use any metric distance function, making them useful for non-Euclidean spaces (e.g., edit distance for strings, geodesic distance on manifolds).

Query complexity is O(log n) on average but can degrade to O(n) for pathological distance distributions.

See also

MetricSpatialIndex

Abstract base class for metric-based spatial indices.

CoverTree

Alternative metric space index with theoretical guarantees.

__init__(data, metric=None)

query(X, k=1)

Query the tree for k nearest neighbors.

Parameters:

• X (array_like) – Query points of shape (n_queries, n_features) or (n_features,).

• k (int, optional) – Number of nearest neighbors. Default 1.

Returns:

result – Indices and distances of k nearest neighbors.

Return type:

NeighborResult

query_radius(X, r)

Find all points within radius r of query points.

Parameters:

• X (array_like) – Query points.

• r (float) – Query radius.

Returns:

indices – For each query, list of indices within radius.

Return type:

list of lists

class pytcl.containers.CoverTreeNode(index, level)

Bases: object

Node in a Cover tree.

index

Index of the point in the original data.

Type:

int

level

Level in the tree (determines covering radius 2^level).

Type:

int

children

Children organized by level.

Type:

dict

__init__(index, level)

index

level

children: dict[int, List[CoverTreeNode]]

add_child(level, child)

Add a child at the specified level.

class pytcl.containers.CoverTree(data, metric=None, base=2.0)

Bases: MetricSpatialIndex

Cover Tree for metric space nearest neighbor search.

A cover tree maintains a hierarchy of nested coverings of the data, where points at level i are a subset of points at level i-1 and cover all points within distance 2^i.

Parameters:

• data (array_like) – Data points of shape (n_samples, n_features).

• metric (callable, optional) – Distance function metric(x, y) -> float. Default is Euclidean distance.

• base (float, optional) – Base for the exponential scale. Default 2.0.

Examples

>>> import numpy as np
>>> points = np.random.rand(100, 3)
>>> tree = CoverTree(points)
>>> result = tree.query(points[:5], k=3)

Notes

Cover trees provide theoretical guarantees based on the expansion constant of the data. For well-distributed data, queries are efficient even in high dimensions.

The implementation uses a simplified version of the original algorithm for clarity.

See also

MetricSpatialIndex

Abstract base class for metric-based spatial indices.

VPTree

Alternative metric space index using vantage points.

__init__(data, metric=None, base=2.0)

root: CoverTreeNode | None

query(X, k=1)

Query the tree for k nearest neighbors.

Parameters:

• X (array_like) – Query points of shape (n_queries, n_features) or (n_features,).

• k (int, optional) – Number of nearest neighbors. Default 1.

Returns:

result – Indices and distances of k nearest neighbors.

Return type:

NeighborResult

query_radius(X, r)

Find all points within radius r of query points.

Parameters:

• X (array_like) – Query points.

• r (float) – Query radius.

Returns:

indices – For each query, list of indices within radius.

Return type:

list of lists

class pytcl.containers.TrackList(tracks=None)

Bases: object

Collection of tracks with query and filter capabilities.

Provides: - Filtering by status, time, region - Iteration and indexing - Batch state extraction - Statistics computation

Parameters:

tracks (Iterable[Track], optional) – Initial tracks to add to the list.

Examples

>>> import numpy as np
>>> from pytcl.trackers.multi_target import Track, TrackStatus
>>> # Create some tracks
>>> t1 = Track(id=0, state=np.array([1, 0, 2, 0]),
...            covariance=np.eye(4), status=TrackStatus.CONFIRMED,
...            hits=5, misses=0, time=1.0)
>>> t2 = Track(id=1, state=np.array([5, 0, 6, 0]),
...            covariance=np.eye(4), status=TrackStatus.TENTATIVE,
...            hits=2, misses=1, time=1.0)
>>> # Create track list
>>> tracks = TrackList([t1, t2])
>>> len(tracks)
2
>>> # Filter by status
>>> confirmed = tracks.confirmed
>>> len(confirmed)
1
>>> # Get positions
>>> positions = tracks.positions(indices=(0, 2))
>>> positions.shape
(2, 2)

__init__(tracks=None)

Initialize track list.

classmethod from_tracker(tracker)

Create a TrackList from a MultiTargetTracker.

Parameters:

tracker (MultiTargetTracker) – The tracker to extract tracks from.

Returns:

A new TrackList containing the tracker’s current tracks.

Return type:

TrackList

__len__()

Return number of tracks.

__iter__()

Iterate over tracks.

__getitem__(idx)

Get track by index or slice.

Parameters:

idx (int or slice) – Index or slice to retrieve.

Returns:

Single track if int, TrackList if slice.

Return type:

Track or TrackList

__contains__(track_id)

Check if track ID exists in list.

__repr__()

String representation.

get_by_id(track_id)

Get track by ID.

Parameters:

track_id (int) – Track ID to find.

Returns:

The track if found, None otherwise.

Return type:

Track or None

get_by_ids(track_ids)

Get multiple tracks by their IDs.

Parameters:

track_ids (Iterable[int]) – Track IDs to find.

Returns:

New TrackList containing the found tracks.

Return type:

TrackList

filter_by_status(status)

Filter tracks by status.

Parameters:

status (TrackStatus) – Status to filter by.

Returns:

New TrackList containing only tracks with the given status.

Return type:

TrackList

filter_by_time(min_time=None, max_time=None)

Filter tracks by time range.

Parameters:

• min_time (float, optional) – Minimum time (inclusive).

• max_time (float, optional) – Maximum time (inclusive).

Returns:

New TrackList containing tracks within the time range.

Return type:

TrackList

filter_by_region(center, radius, state_indices=(0, 2))

Filter tracks by spatial region.

Parameters:

• center (array_like) – Center point [x, y].

• radius (float) – Radius of the region.

• state_indices (tuple of int, optional) – Indices of x and y in state vector (default: (0, 2)).

Returns:

New TrackList containing tracks within the region.

Return type:

TrackList

filter_by_predicate(predicate)

Filter tracks using a custom predicate.

Parameters:

predicate (callable) – Function that takes a Track and returns True to include it.

Returns:

New TrackList containing tracks that pass the predicate.

Return type:

TrackList

property confirmed: TrackList

Get confirmed tracks only.

property tentative: TrackList

Get tentative tracks only.

property track_ids: List[int]

Get list of all track IDs.

states()

Extract all track states as array.

Returns:

Array of shape (n_tracks, state_dim) containing all states.

Return type:

ndarray

covariances()

Extract all track covariances as array.

Returns:

Array of shape (n_tracks, state_dim, state_dim).

Return type:

ndarray

positions(indices=(0, 2))

Extract track positions.

Parameters:

indices (tuple of int, optional) – Indices of x and y in state vector (default: (0, 2)).

Returns:

Array of shape (n_tracks, 2) containing positions.

Return type:

ndarray

stats()

Compute statistics about the track list.

Returns:

Statistics about the tracks.

Return type:

TrackListStats

add(track)

Add a track and return a new TrackList.

Parameters:

track (Track) – Track to add.

Returns:

New TrackList with the track added.

Return type:

TrackList

remove(track_id)

Remove a track by ID and return a new TrackList.

Parameters:

track_id (int) – ID of track to remove.

Returns:

New TrackList without the specified track.

Return type:

TrackList

merge(other)

Merge with another TrackList.

Parameters:

other (TrackList) – TrackList to merge with.

Returns:

New TrackList containing tracks from both lists.

Return type:

TrackList

Notes

Duplicate track IDs are not handled specially - both tracks will be included. Use get_by_id on the result to access specific tracks.

copy()

Create a copy of this TrackList.

Returns:

A new TrackList with the same tracks.

Return type:

TrackList

class pytcl.containers.TrackQuery(tracks, indices)

Bases: NamedTuple

Result of a track list query.

tracks

List of tracks matching the query.

Type:

List[Track]

indices

Original indices of the matching tracks.

Type:

List[int]

tracks: List[Track]

Alias for field number 0

indices: List[int]

Alias for field number 1

class pytcl.containers.TrackListStats(n_tracks, n_confirmed, n_tentative, n_deleted, mean_hits, mean_misses)

Bases: NamedTuple

Statistics about a track list.

n_tracks

Total number of tracks.

Type:

int

n_confirmed

Number of confirmed tracks.

Type:

int

n_tentative

Number of tentative tracks.

Type:

int

n_deleted

Number of deleted tracks.

Type:

int

mean_hits

Average number of hits per track.

Type:

float

mean_misses

Average number of misses per track.

Type:

float

n_tracks: int

Alias for field number 0

n_confirmed: int

Alias for field number 1

n_tentative: int

Alias for field number 2

n_deleted: int

Alias for field number 3

mean_hits: float

Alias for field number 4

mean_misses: float

Alias for field number 5

class pytcl.containers.Measurement(value, time, covariance=None, sensor_id=0, id=-1)

Bases: NamedTuple

Single measurement with metadata.

value

Measurement vector.

Type:

ndarray

time

Time of measurement.

Type:

float

covariance

Measurement covariance matrix.

Type:

ndarray, optional

sensor_id

ID of the sensor that produced this measurement.

Type:

int

id

Unique measurement identifier.

Type:

int

value: ndarray[tuple[Any, ...], dtype[float64]]

Alias for field number 0

time: float

Alias for field number 1

covariance: ndarray[tuple[Any, ...], dtype[float64]] | None

Alias for field number 2

sensor_id: int

Alias for field number 3

id: int

Alias for field number 4

class pytcl.containers.MeasurementSet(measurements=None)

Bases: object

Collection of measurements with time and spatial indexing.

Provides: - Time-windowed queries - Spatial region queries - Sensor filtering - Batch value extraction

Parameters:

measurements (Iterable[Measurement], optional) – Initial measurements to add.

Examples

>>> import numpy as np
>>> # Create measurements
>>> m1 = Measurement(value=np.array([1.0, 2.0]), time=0.0, id=0)
>>> m2 = Measurement(value=np.array([3.0, 4.0]), time=0.0, id=1)
>>> m3 = Measurement(value=np.array([5.0, 6.0]), time=1.0, id=2)
>>> # Create measurement set
>>> mset = MeasurementSet([m1, m2, m3])
>>> len(mset)
3
>>> # Filter by time
>>> at_t0 = mset.at_time(0.0)
>>> len(at_t0)
2
>>> # Get values
>>> values = mset.values()
>>> values.shape
(3, 2)

__init__(measurements=None)

Initialize measurement set.

classmethod from_arrays(values, times, covariances=None, sensor_ids=None)

Create MeasurementSet from arrays.

Parameters:

• values (array_like) – Array of shape (n_meas, meas_dim) containing measurement values.

• times (array_like) – Array of length n_meas containing measurement times.

• covariances (array_like, optional) – Array of shape (n_meas, meas_dim, meas_dim) containing covariances.

• sensor_ids (array_like, optional) – Array of length n_meas containing sensor IDs.

Returns:

New MeasurementSet containing the measurements.

Return type:

MeasurementSet

__len__()

Return number of measurements.

__iter__()

Iterate over measurements.

__getitem__(idx)

Get measurement by index or slice.

Parameters:

idx (int or slice) – Index or slice to retrieve.

Returns:

Single measurement if int, MeasurementSet if slice.

Return type:

Measurement or MeasurementSet

__repr__()

String representation.

at_time(time, tolerance=1e-09)

Get measurements at a specific time.

Parameters:

• time (float) – Time to query.

• tolerance (float, optional) – Tolerance for time matching (default: 1e-9).

Returns:

Measurements at the specified time.

Return type:

MeasurementSet

in_time_window(start, end)

Get measurements in a time window.

Parameters:

• start (float) – Start time (inclusive).

• end (float) – End time (inclusive).

Returns:

Measurements within the time window.

Return type:

MeasurementSet

in_region(center, radius)

Get measurements within a spatial region.

Parameters:

• center (array_like) – Center point of the region.

• radius (float) – Radius of the region.

Returns:

Measurements within the region.

Return type:

MeasurementSet

by_sensor(sensor_id)

Get measurements from a specific sensor.

Parameters:

sensor_id (int) – Sensor ID to filter by.

Returns:

Measurements from the specified sensor.

Return type:

MeasurementSet

nearest_to(point, k=1)

Find k nearest measurements to a point.

Parameters:

• point (array_like) – Query point.

• k (int, optional) – Number of nearest neighbors (default: 1).

Returns:

Query result with measurements and indices.

Return type:

MeasurementQuery

Notes

This method builds a spatial index on first call if not already built.

property times: ndarray[tuple[Any, ...], dtype[float64]]

Get unique measurement times.

property sensors: List[int]

Get unique sensor IDs.

property time_range: Tuple[float, float]

Get time range of measurements.

Returns:

(min_time, max_time) or (0.0, 0.0) if empty.

Return type:

tuple of float

values()

Extract all measurement values as array.

Returns:

Array of shape (n_meas, meas_dim).

Return type:

ndarray

values_at_time(time, tolerance=1e-09)

Extract measurement values at a specific time.

Parameters:

• time (float) – Time to query.

• tolerance (float, optional) – Tolerance for time matching (default: 1e-9).

Returns:

Array of shape (n_meas_at_time, meas_dim).

Return type:

ndarray

add(measurement)

Add a measurement and return a new MeasurementSet.

Parameters:

measurement (Measurement) – Measurement to add.

Returns:

New MeasurementSet with the measurement added.

Return type:

MeasurementSet

add_batch(measurements)

Add multiple measurements and return a new MeasurementSet.

Parameters:

measurements (Iterable[Measurement]) – Measurements to add.

Returns:

New MeasurementSet with the measurements added.

Return type:

MeasurementSet

merge(other)

Merge with another MeasurementSet.

Parameters:

other (MeasurementSet) – MeasurementSet to merge with.

Returns:

New MeasurementSet containing measurements from both.

Return type:

MeasurementSet

copy()

Create a copy of this MeasurementSet.

Returns:

A new MeasurementSet with the same measurements.

Return type:

MeasurementSet

build_spatial_index()

Build spatial index for efficient nearest neighbor queries.

The index is built from measurement values. This is called automatically by nearest_to() if needed.

class pytcl.containers.MeasurementQuery(measurements, indices)

Bases: NamedTuple

Result of a measurement set query.

measurements

List of measurements matching the query.

Type:

List[Measurement]

indices

Original indices of the matching measurements.

Type:

List[int]

measurements: List[Measurement]

Alias for field number 0

indices: List[int]

Alias for field number 1

class pytcl.containers.TrackCluster(id, track_ids, centroid, covariance, time)

Bases: NamedTuple

A cluster of related tracks.

id

Unique cluster identifier.

Type:

int

track_ids

Immutable tuple of track IDs in this cluster.

Type:

Tuple[int, …]

centroid

Cluster center position.

Type:

ndarray

covariance

Cluster spread covariance matrix.

Type:

ndarray

time

Time at which cluster was computed.

Type:

float

id: int

Alias for field number 0

track_ids: Tuple[int, ...]

Alias for field number 1

centroid: ndarray[tuple[Any, ...], dtype[float64]]

Alias for field number 2

covariance: ndarray[tuple[Any, ...], dtype[float64]]

Alias for field number 3

time: float

Alias for field number 4

class pytcl.containers.ClusterSet(clusters=None)

Bases: object

Collection of track clusters.

Provides: - Cluster creation from tracks - Cluster queries - Cluster merging/splitting

Parameters:

clusters (Iterable[TrackCluster], optional) – Initial clusters to add.

Examples

>>> import numpy as np
>>> from pytcl.trackers.multi_target import Track, TrackStatus
>>> from pytcl.containers.track_list import TrackList
>>> # Create some tracks in two groups
>>> t1 = Track(id=0, state=np.array([0, 0, 0, 0]),
...            covariance=np.eye(4), status=TrackStatus.CONFIRMED,
...            hits=5, misses=0, time=1.0)
>>> t2 = Track(id=1, state=np.array([1, 0, 1, 0]),
...            covariance=np.eye(4), status=TrackStatus.CONFIRMED,
...            hits=5, misses=0, time=1.0)
>>> t3 = Track(id=2, state=np.array([10, 0, 10, 0]),
...            covariance=np.eye(4), status=TrackStatus.CONFIRMED,
...            hits=5, misses=0, time=1.0)
>>> tracks = TrackList([t1, t2, t3])
>>> # Cluster using DBSCAN
>>> clusters = cluster_tracks_dbscan(tracks, eps=5.0, min_samples=2)

__init__(clusters=None)

Initialize cluster set.

classmethod from_tracks(tracks, method='dbscan', **kwargs)

Create a ClusterSet by clustering tracks.

Parameters:

• tracks (TrackList) – Tracks to cluster.

• method (str) – Clustering method: ‘dbscan’ or ‘kmeans’.

• **kwargs (Any) – Additional arguments passed to the clustering function. For DBSCAN: eps, min_samples, state_indices For K-means: n_clusters, state_indices, rng

Returns:

New ClusterSet containing the computed clusters.

Return type:

ClusterSet

Examples

>>> clusters = ClusterSet.from_tracks(tracks, method='dbscan', eps=2.0)
>>> clusters = ClusterSet.from_tracks(tracks, method='kmeans', n_clusters=3)

__len__()

Return number of clusters.

__iter__()

Iterate over clusters.

__getitem__(idx)

Get cluster by index or slice.

Parameters:

idx (int or slice) – Index or slice to retrieve.

Returns:

Single cluster if int, ClusterSet if slice.

Return type:

TrackCluster or ClusterSet

__contains__(cluster_id)

Check if cluster ID exists in set.

__repr__()

String representation.

get_cluster(cluster_id)

Get cluster by ID.

Parameters:

cluster_id (int) – Cluster ID to find.

Returns:

The cluster if found, None otherwise.

Return type:

TrackCluster or None

get_cluster_for_track(track_id)

Get the cluster containing a specific track.

Parameters:

track_id (int) – Track ID to find.

Returns:

The cluster containing the track, or None if not found.

Return type:

TrackCluster or None

clusters_in_region(center, radius)

Get clusters with centroids within a spatial region.

Parameters:

• center (array_like) – Center point [x, y].

• radius (float) – Radius of the region.

Returns:

Clusters within the region.

Return type:

list of TrackCluster

property cluster_ids: List[int]

Get list of all cluster IDs.

property n_tracks_total: int

Get total number of tracks across all clusters.

cluster_stats(cluster_id, tracks=None, state_indices=(0, 2), velocity_indices=(1, 3))

Compute statistics for a cluster.

Parameters:

• cluster_id (int) – ID of the cluster.

• tracks (TrackList, optional) – TrackList containing the tracks. Required for velocity coherence.

• state_indices (tuple of int, optional) – Indices of x and y in state vector (default: (0, 2)).

• velocity_indices (tuple of int, optional) – Indices of vx and vy in state vector (default: (1, 3)).

Returns:

Statistics for the cluster, or None if cluster not found.

Return type:

ClusterStats or None

all_stats(tracks=None, state_indices=(0, 2), velocity_indices=(1, 3))

Compute statistics for all clusters.

Parameters:

• tracks (TrackList, optional) – TrackList containing the tracks.

• state_indices (tuple of int, optional) – Indices of x and y in state vector (default: (0, 2)).

• velocity_indices (tuple of int, optional) – Indices of vx and vy in state vector (default: (1, 3)).

Returns:

Mapping from cluster ID to ClusterStats.

Return type:

dict

add_cluster(cluster)

Add a cluster and return a new ClusterSet.

Parameters:

cluster (TrackCluster) – Cluster to add.

Returns:

New ClusterSet with the cluster added.

Return type:

ClusterSet

remove_cluster(cluster_id)

Remove a cluster by ID and return a new ClusterSet.

Parameters:

cluster_id (int) – ID of cluster to remove.

Returns:

New ClusterSet without the specified cluster.

Return type:

ClusterSet

merge_clusters(id1, id2, new_id=None)

Merge two clusters into one.

Parameters:

• id1 (int) – ID of first cluster.

• id2 (int) – ID of second cluster.

• new_id (int, optional) – ID for the merged cluster. Defaults to id1.

Returns:

New ClusterSet with merged cluster.

Return type:

ClusterSet

Raises:

ValueError – If either cluster ID is not found.

split_cluster(cluster_id, track_ids_1, track_ids_2, new_id_1=None, new_id_2=None, tracks=None, state_indices=(0, 2))

Split a cluster into two.

Parameters:

• cluster_id (int) – ID of cluster to split.

• track_ids_1 (Iterable[int]) – Track IDs for first new cluster.

• track_ids_2 (Iterable[int]) – Track IDs for second new cluster.

• new_id_1 (int, optional) – ID for first new cluster. Defaults to cluster_id.

• new_id_2 (int, optional) – ID for second new cluster. Defaults to max(cluster_ids) + 1.

• tracks (TrackList, optional) – TrackList for computing centroids. If None, uses existing centroid.

• state_indices (tuple of int, optional) – Indices of x and y in state vector (default: (0, 2)).

Returns:

New ClusterSet with split clusters.

Return type:

ClusterSet

Raises:

ValueError – If cluster ID is not found.

copy()

Create a copy of this ClusterSet.

Returns:

A new ClusterSet with the same clusters.

Return type:

ClusterSet

class pytcl.containers.ClusterStats(n_tracks, mean_separation, max_separation, velocity_coherence)

Bases: NamedTuple

Statistics for a cluster.

n_tracks

Number of tracks in the cluster.

Type:

int

mean_separation

Average distance between tracks and centroid.

Type:

float

max_separation

Maximum distance from any track to centroid.

Type:

float

velocity_coherence

Measure of how aligned velocities are (0-1). 1.0 means perfectly aligned, 0.0 means random directions.

Type:

float

n_tracks: int

Alias for field number 0

mean_separation: float

Alias for field number 1

max_separation: float

Alias for field number 2

velocity_coherence: float

Alias for field number 3

pytcl.containers.cluster_tracks_dbscan(tracks, eps, min_samples=2, state_indices=(0, 2))

Cluster tracks using DBSCAN algorithm.

Parameters:

• tracks (TrackList) – Tracks to cluster.

• eps (float) – Maximum distance between two tracks to be considered neighbors.

• min_samples (int, optional) – Minimum number of tracks to form a cluster (default: 2).

• state_indices (tuple of int, optional) – Indices of x and y in state vector (default: (0, 2)).

Returns:

Set of track clusters.

Return type:

ClusterSet

pytcl.containers.cluster_tracks_kmeans(tracks, n_clusters, state_indices=(0, 2), rng=None)

Cluster tracks using K-means algorithm.

Parameters:

• tracks (TrackList) – Tracks to cluster.

• n_clusters (int) – Number of clusters to form.

• state_indices (tuple of int, optional) – Indices of x and y in state vector (default: (0, 2)).

• rng (numpy.random.Generator, optional) – Random number generator for reproducibility.

Returns:

Set of track clusters.

Return type:

ClusterSet

pytcl.containers.compute_cluster_centroid(tracks, state_indices=(0, 2))

Compute the centroid of a group of tracks.

Parameters:

• tracks (Iterable[Track]) – Tracks to compute centroid for.

• state_indices (tuple of int, optional) – Indices of x and y in state vector (default: (0, 2)).

Returns:

centroid – Centroid position [x, y].

Return type:

ndarray

Examples

>>> from pytcl.trackers.multi_target import Track
>>> import numpy as np
>>> # Create sample tracks with [x, vx, y, vy] state vectors
>>> track1 = Track(state=np.array([0.0, 1.0, 0.0, 1.0]))
>>> track2 = Track(state=np.array([2.0, 1.0, 2.0, 1.0]))
>>> track3 = Track(state=np.array([4.0, 1.0, 4.0, 1.0]))
>>> tracks = [track1, track2, track3]
>>> centroid = compute_cluster_centroid(tracks)
>>> centroid
array([2., 2.])

See also

compute_cluster_covariance

Compute covariance of track positions.

K-D Tree

K-dimensional tree for spatial queries.

K-D Tree implementation.

A k-dimensional tree (k-d tree) is a space-partitioning data structure for organizing points in k-dimensional space. Useful for efficient nearest neighbor searches in tracking applications.

References

[1]

J. L. Bentley, “Multidimensional binary search trees used for associative searching,” Communications of the ACM, 1975.

[2]

J. H. Friedman, J. L. Bentley, R. A. Finkel, “An Algorithm for Finding Best Matches in Logarithmic Expected Time,” ACM TOMS, 1977.

class pytcl.containers.kd_tree.KDNode(point, index, split_dim)

Bases: object

A node in the k-d tree.

point

The point stored at this node.

Type:

ndarray

index

Original index of this point in the data array.

Type:

int

split_dim

The dimension used for splitting at this node.

Type:

int

left

Left child (points with smaller split dimension value).

Type:

KDNode or None

right

Right child (points with larger split dimension value).

Type:

KDNode or None

__init__(point, index, split_dim)

point

index

split_dim

left: KDNode | None

right: KDNode | None

class pytcl.containers.kd_tree.NeighborResult(indices, distances)

Bases: NamedTuple

Unified result type for spatial index queries.

All spatial index implementations (KDTree, BallTree, VPTree, CoverTree, RTree) return this type from their query methods, ensuring a consistent interface across the library.

indices

Indices of the k nearest neighbors in the original data array. For k=1, may be 1D. For k>1, shape is (n_queries, k).

Type:

ndarray of shape (n_queries, k) or (n_queries,)

distances

Distances to the k nearest neighbors. Same shape as indices.

Type:

ndarray of shape (n_queries, k) or (n_queries,)

Examples

>>> from pytcl.containers import KDTree
>>> import numpy as np
>>> points = np.array([[0, 0], [1, 0], [0, 1], [1, 1]])
>>> tree = KDTree(points)
>>> result = tree.query([[0.1, 0.1]], k=2)
>>> result.indices
array([[0, 2]])
>>> result.distances
array([[0.14142136, 0.9       ]])

See also

BaseSpatialIndex

Abstract base class for spatial indices.

indices: ndarray[tuple[Any, ...], dtype[int64]]

Alias for field number 0

distances: ndarray[tuple[Any, ...], dtype[floating]]

Alias for field number 1

pytcl.containers.kd_tree.NearestNeighborResult

alias of NeighborResult

class pytcl.containers.kd_tree.KDTree(data, leaf_size=10)

Bases: BaseSpatialIndex

K-D Tree for efficient spatial queries.

A k-d tree recursively partitions space by splitting along different dimensions at each level. This enables O(log n) average-case nearest neighbor queries.

Parameters:

• data (array_like) – Data points of shape (n_samples, n_features).

• leaf_size (int, optional) – Maximum number of points in a leaf node. Default 10.

Examples

>>> import numpy as np
>>> points = np.array([[0, 0], [1, 0], [0, 1], [1, 1]])
>>> tree = KDTree(points)
>>> result = tree.query(np.array([[0.1, 0.1]]), k=2)
>>> result.indices
array([[0, 1]])

Notes

The tree is balanced by choosing the median point along the split dimension at each level, giving O(n log n) construction time.

Query complexity is O(log n) on average for nearest neighbor search, though worst case is O(n) for highly unbalanced queries.

See also

BaseSpatialIndex

Abstract base class defining the spatial index interface.

BallTree

Alternative spatial index using hyperspheres.

__init__(data, leaf_size=10)

query(X, k=1)

Query the tree for k nearest neighbors.

Parameters:

• X (array_like) – Query points of shape (n_queries, n_features) or (n_features,).

• k (int, optional) – Number of nearest neighbors. Default 1.

Returns:

result – Indices and distances of k nearest neighbors for each query.

Return type:

NeighborResult

Examples

>>> tree = KDTree(np.array([[0, 0], [1, 1], [2, 2]]))
>>> result = tree.query([[0.5, 0.5]], k=2)
>>> result.indices
array([[0, 1]])

query_radius(X, r)

Query the tree for all points within radius r.

Parameters:

• X (array_like) – Query points of shape (n_queries, n_features) or (n_features,).

• r (float) – Query radius.

Returns:

indices – For each query, a list of indices of points within radius r.

Return type:

list of lists

Examples

>>> tree = KDTree(np.array([[0, 0], [1, 0], [0, 1], [5, 5]]))
>>> tree.query_radius([[0, 0]], r=1.5)
[[0, 1, 2]]

class pytcl.containers.kd_tree.BallTree(data, leaf_size=10)

Bases: BaseSpatialIndex

Ball Tree for efficient spatial queries.

A ball tree partitions space using hyperspheres (balls), which can be more efficient than k-d trees for high-dimensional data or non-Euclidean metrics.

Parameters:

• data (array_like) – Data points of shape (n_samples, n_features).

• leaf_size (int, optional) – Maximum number of points in a leaf node. Default 10.

Examples

>>> import numpy as np
>>> points = np.array([[0, 0], [1, 0], [0, 1], [1, 1]])
>>> tree = BallTree(points)
>>> result = tree.query(np.array([[0.1, 0.1]]), k=2)

Notes

Ball trees have O(n log n) construction and O(log n) average-case query time. They can outperform k-d trees in high dimensions.

See also

BaseSpatialIndex

Abstract base class defining the spatial index interface.

KDTree

Alternative spatial index using axis-aligned splits.

__init__(data, leaf_size=10)

query(X, k=1)

Query the tree for k nearest neighbors.

Parameters:

• X (array_like) – Query points of shape (n_queries, n_features) or (n_features,).

• k (int, optional) – Number of nearest neighbors. Default 1.

Returns:

result – Indices and distances of k nearest neighbors.

Return type:

NeighborResult

query_radius(X, r)

Query the tree for all points within radius r.

Parameters:

• X (array_like) – Query points of shape (n_queries, n_features) or (n_features,).

• r (float) – Query radius.

Returns:

indices – For each query, a list of indices of points within radius r.

Return type:

list of lists

Ball Tree

Ball tree for metric space queries.

R-Tree

R-tree for spatial indexing.

R-tree implementation for spatial indexing of bounding boxes.

R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles, or polygons.

References

[1]

A. Guttman, “R-trees: A Dynamic Index Structure for Spatial Searching,” ACM SIGMOD, 1984.

[2]

N. Beckmann et al., “The R*-tree: An Efficient and Robust Access Method for Points and Rectangles,” ACM SIGMOD, 1990.

class pytcl.containers.rtree.NeighborResult(indices, distances)

Bases: NamedTuple

Unified result type for spatial index queries.

All spatial index implementations (KDTree, BallTree, VPTree, CoverTree, RTree) return this type from their query methods, ensuring a consistent interface across the library.

indices

Indices of the k nearest neighbors in the original data array. For k=1, may be 1D. For k>1, shape is (n_queries, k).

Type:

ndarray of shape (n_queries, k) or (n_queries,)

distances

Distances to the k nearest neighbors. Same shape as indices.

Type:

ndarray of shape (n_queries, k) or (n_queries,)

Examples

>>> from pytcl.containers import KDTree
>>> import numpy as np
>>> points = np.array([[0, 0], [1, 0], [0, 1], [1, 1]])
>>> tree = KDTree(points)
>>> result = tree.query([[0.1, 0.1]], k=2)
>>> result.indices
array([[0, 2]])
>>> result.distances
array([[0.14142136, 0.9       ]])

See also

BaseSpatialIndex

Abstract base class for spatial indices.

indices: ndarray[tuple[Any, ...], dtype[int64]]

Alias for field number 0

distances: ndarray[tuple[Any, ...], dtype[floating]]

Alias for field number 1

pytcl.containers.rtree.SpatialQueryResult

alias of NeighborResult

class pytcl.containers.rtree.BoundingBox(min_coords, max_coords)

Bases: NamedTuple

Axis-aligned bounding box.

min_coords

Minimum coordinates in each dimension.

Type:

ndarray

max_coords

Maximum coordinates in each dimension.

Type:

ndarray

min_coords: ndarray[tuple[Any, ...], dtype[floating]]

Alias for field number 0

max_coords: ndarray[tuple[Any, ...], dtype[floating]]

Alias for field number 1

property center: ndarray[tuple[Any, ...], dtype[floating]]

Center point of the bounding box.

property dimensions: ndarray[tuple[Any, ...], dtype[floating]]

Size in each dimension.

property volume: float

Volume (area in 2D) of the bounding box.

contains_point(point)

Check if box contains a point.

intersects(other)

Check if this box intersects another.

contains_box(other)

Check if this box fully contains another.

pytcl.containers.rtree.merge_boxes(boxes)

Compute minimum bounding box containing all boxes.

pytcl.containers.rtree.box_from_point(point)

Create a zero-volume bounding box from a point.

pytcl.containers.rtree.box_from_points(points)

Create minimum bounding box containing all points.

class pytcl.containers.rtree.RTreeNode(is_leaf=True)

Bases: object

Node in an R-tree.

bbox

Bounding box of this node.

Type:

BoundingBox

is_leaf

Whether this is a leaf node.

Type:

bool

children

Child nodes (for internal nodes).

Type:

list

entries

(bbox, data_index) pairs (for leaf nodes).

Type:

list

__init__(is_leaf=True)

is_leaf

children: List[RTreeNode]

entries: List[Tuple[BoundingBox, int]]

bbox: BoundingBox | None

parent: RTreeNode | None

update_bbox()

Update bounding box to contain all children/entries.

class pytcl.containers.rtree.RTreeResult(indices, boxes)

Bases: NamedTuple

Result of R-tree query.

indices

Indices of matching entries.

Type:

list

boxes

Bounding boxes of matching entries.

Type:

list

indices: List[int]

Alias for field number 0

boxes: List[BoundingBox]

Alias for field number 1

class pytcl.containers.rtree.RTree(max_entries=10, min_entries=None)

Bases: object

R-tree for spatial indexing of bounding boxes.

An R-tree groups nearby objects and represents them with their minimum bounding rectangle. This allows efficient spatial queries.

Unlike KDTree and BallTree which only index points, RTree can index bounding boxes of arbitrary size. It also supports dynamic insertion.

Parameters:

• max_entries (int, optional) – Maximum entries per node. Default 10.

• min_entries (int, optional) – Minimum entries per node (except root). Default max_entries // 2.

n_entries

Number of entries in the tree.

Type:

int

n_features

Dimensionality of the data (set after first insertion).

Type:

int

Examples

>>> tree = RTree()
>>> tree.insert(BoundingBox(np.array([0, 0]), np.array([1, 1])), 0)
>>> tree.insert(BoundingBox(np.array([2, 2]), np.array([3, 3])), 1)
>>> query_box = BoundingBox(np.array([0.5, 0.5]), np.array([2.5, 2.5]))
>>> result = tree.query_intersect(query_box)

Notes

This implementation uses a simplified insertion algorithm. For production use, consider using R*-tree or packed R-tree variants.

See also

KDTree

Point-based spatial index using axis-aligned splits.

BallTree

Point-based spatial index using hyperspheres.

__init__(max_entries=10, min_entries=None)

n_features: int | None

classmethod from_points(data, max_entries=10, min_entries=None)

Create an RTree from point data.

This factory method provides an interface similar to KDTree and BallTree, allowing RTree to be used interchangeably for point queries.

Parameters:

• data (array_like) – Data points of shape (n_samples, n_features).

• max_entries (int, optional) – Maximum entries per node. Default 10.

• min_entries (int, optional) – Minimum entries per node. Default max_entries // 2.

Returns:

tree – RTree with all points inserted.

Return type:

RTree

Examples

>>> points = np.array([[0, 0], [1, 0], [0, 1], [1, 1]])
>>> tree = RTree.from_points(points)
>>> result = tree.query([[0.1, 0.1]], k=2)

insert(bbox, data_index=None)

Insert a bounding box into the tree.

Parameters:

• bbox (BoundingBox) – Bounding box to insert.

• data_index (int, optional) – Index to associate with this box. If None, uses next available.

Returns:

index – Index of the inserted entry.

Return type:

int

insert_point(point, data_index=None)

Insert a point as a zero-volume bounding box.

insert_points(points)

Insert multiple points.

query(X, k=1)

Query the tree for k nearest neighbors.

This method provides API compatibility with KDTree and BallTree.

Parameters:

• X (array_like) – Query points of shape (n_queries, n_features) or (n_features,).

• k (int, optional) – Number of nearest neighbors. Default 1.

Returns:

result – Indices and distances of k nearest neighbors for each query.

Return type:

NeighborResult

Examples

>>> tree = RTree.from_points(np.array([[0, 0], [1, 1], [2, 2]]))
>>> result = tree.query([[0.5, 0.5]], k=2)
>>> result.indices
array([[0, 1]])

query_radius(X, r)

Query the tree for all points within radius r.

This method provides API compatibility with KDTree and BallTree.

Parameters:

• X (array_like) – Query points of shape (n_queries, n_features) or (n_features,).

• r (float) – Query radius.

Returns:

indices – For each query, a list of indices of points within radius r.

Return type:

list of lists

Examples

>>> tree = RTree.from_points(np.array([[0, 0], [1, 0], [0, 1], [5, 5]]))
>>> tree.query_radius([[0, 0]], r=1.5)
[[0, 1, 2]]

query_ball_point(X, r)

Query the tree for all points within radius r.

This is an alias for query_radius() provided for compatibility with scipy.spatial.KDTree.

Parameters:

• X (array_like) – Query points of shape (n_queries, n_features) or (n_features,).

• r (float) – Search radius.

Returns:

indices – For each query point, a list of indices of data points within distance r.

Return type:

list of list of int

See also

query_radius

The underlying implementation.

query_intersect(query_bbox)

Find all entries intersecting a query box.

Parameters:

query_bbox (BoundingBox) – Query bounding box.

Returns:

result – Indices and boxes of intersecting entries.

Return type:

RTreeResult

query_contains(query_bbox)

Find all entries contained within a query box.

Parameters:

query_bbox (BoundingBox) – Query bounding box.

Returns:

result – Indices and boxes of contained entries.

Return type:

RTreeResult

query_point(point)

Find all entries containing a point.

Parameters:

point (array_like) – Query point.

Returns:

result – Indices and boxes of entries containing the point.

Return type:

RTreeResult

nearest(query_point, k=1)

Find k nearest entries to a query point.

Parameters:

• query_point (array_like) – Query point.

• k (int, optional) – Number of nearest neighbors. Default 1.

Returns:

• indices (list) – Indices of nearest entries.

• distances (list) – Distances to nearest entries.

Return type:

Tuple[List[int], List[float]]

VP-Tree

Vantage-point tree for metric spaces.

Vantage Point Tree (VP-tree) implementation.

VP-trees are metric trees that partition data based on distance to selected vantage points. They are effective for nearest neighbor search in metric spaces, particularly with high-dimensional data.

References

[1]

P. N. Yianilos, “Data structures and algorithms for nearest neighbor search in general metric spaces,” SODA 1993.

class pytcl.containers.vptree.NeighborResult(indices, distances)

Bases: NamedTuple

Unified result type for spatial index queries.

All spatial index implementations (KDTree, BallTree, VPTree, CoverTree, RTree) return this type from their query methods, ensuring a consistent interface across the library.

indices

Indices of the k nearest neighbors in the original data array. For k=1, may be 1D. For k>1, shape is (n_queries, k).

Type:

ndarray of shape (n_queries, k) or (n_queries,)

distances

Distances to the k nearest neighbors. Same shape as indices.

Type:

ndarray of shape (n_queries, k) or (n_queries,)

Examples

>>> from pytcl.containers import KDTree
>>> import numpy as np
>>> points = np.array([[0, 0], [1, 0], [0, 1], [1, 1]])
>>> tree = KDTree(points)
>>> result = tree.query([[0.1, 0.1]], k=2)
>>> result.indices
array([[0, 2]])
>>> result.distances
array([[0.14142136, 0.9       ]])

See also

BaseSpatialIndex

Abstract base class for spatial indices.

indices: ndarray[tuple[Any, ...], dtype[int64]]

Alias for field number 0

distances: ndarray[tuple[Any, ...], dtype[floating]]

Alias for field number 1

pytcl.containers.vptree.VPTreeResult

alias of NeighborResult

class pytcl.containers.vptree.VPNode(index, radius=0.0)

Bases: object

Node in a VP-tree.

index

Index of the vantage point in the original data.

Type:

int

radius

Median distance to vantage point (splitting threshold).

Type:

float

left

Left subtree (points closer than radius).

Type:

VPNode or None

right

Right subtree (points farther than radius).

Type:

VPNode or None

__init__(index, radius=0.0)

index

radius

left: VPNode | None

right: VPNode | None

class pytcl.containers.vptree.VPTree(data, metric=None)

Bases: MetricSpatialIndex

Vantage Point Tree for metric space nearest neighbor search.

A VP-tree recursively partitions space by selecting a vantage point and dividing remaining points into those closer than a threshold (median distance) and those farther.

Parameters:

• data (array_like) – Data points of shape (n_samples, n_features).

• metric (callable, optional) – Distance function metric(x, y) -> float. Default is Euclidean distance.

Examples

>>> import numpy as np
>>> points = np.random.rand(100, 3)
>>> tree = VPTree(points)
>>> result = tree.query(points[:5], k=3)
>>> result.indices.shape
(5, 3)

Notes

VP-trees can use any metric distance function, making them useful for non-Euclidean spaces (e.g., edit distance for strings, geodesic distance on manifolds).

Query complexity is O(log n) on average but can degrade to O(n) for pathological distance distributions.

See also

MetricSpatialIndex

Abstract base class for metric-based spatial indices.

CoverTree

Alternative metric space index with theoretical guarantees.

__init__(data, metric=None)

query(X, k=1)

Query the tree for k nearest neighbors.

Parameters:

• X (array_like) – Query points of shape (n_queries, n_features) or (n_features,).

• k (int, optional) – Number of nearest neighbors. Default 1.

Returns:

result – Indices and distances of k nearest neighbors.

Return type:

NeighborResult

query_radius(X, r)

Find all points within radius r of query points.

Parameters:

• X (array_like) – Query points.

• r (float) – Query radius.

Returns:

indices – For each query, list of indices within radius.

Return type:

list of lists

Cover Tree

Cover tree for approximate nearest neighbors.

Cover Tree implementation for nearest neighbor search.

Cover trees are data structures for nearest neighbor search in metric spaces with a theoretical guarantee of O(c^12 log n) query time, where c is the expansion constant of the data.

References

[1]

A. Beygelzimer, S. Kakade, J. Langford, “Cover trees for nearest neighbor,” ICML 2006.

class pytcl.containers.covertree.NeighborResult(indices, distances)

Bases: NamedTuple

Unified result type for spatial index queries.

All spatial index implementations (KDTree, BallTree, VPTree, CoverTree, RTree) return this type from their query methods, ensuring a consistent interface across the library.

indices

Indices of the k nearest neighbors in the original data array. For k=1, may be 1D. For k>1, shape is (n_queries, k).

Type:

ndarray of shape (n_queries, k) or (n_queries,)

distances

Distances to the k nearest neighbors. Same shape as indices.

Type:

ndarray of shape (n_queries, k) or (n_queries,)

Examples

>>> from pytcl.containers import KDTree
>>> import numpy as np
>>> points = np.array([[0, 0], [1, 0], [0, 1], [1, 1]])
>>> tree = KDTree(points)
>>> result = tree.query([[0.1, 0.1]], k=2)
>>> result.indices
array([[0, 2]])
>>> result.distances
array([[0.14142136, 0.9       ]])

See also

BaseSpatialIndex

Abstract base class for spatial indices.

indices: ndarray[tuple[Any, ...], dtype[int64]]

Alias for field number 0

distances: ndarray[tuple[Any, ...], dtype[floating]]

Alias for field number 1

pytcl.containers.covertree.CoverTreeResult

alias of NeighborResult

class pytcl.containers.covertree.CoverTreeNode(index, level)

Bases: object

Node in a Cover tree.

index

Index of the point in the original data.

Type:

int

level

Level in the tree (determines covering radius 2^level).

Type:

int

children

Children organized by level.

Type:

dict

__init__(index, level)

index

level

children: dict[int, List[CoverTreeNode]]

add_child(level, child)

Add a child at the specified level.

class pytcl.containers.covertree.CoverTree(data, metric=None, base=2.0)

Bases: MetricSpatialIndex

Cover Tree for metric space nearest neighbor search.

A cover tree maintains a hierarchy of nested coverings of the data, where points at level i are a subset of points at level i-1 and cover all points within distance 2^i.

Parameters:

• data (array_like) – Data points of shape (n_samples, n_features).

• metric (callable, optional) – Distance function metric(x, y) -> float. Default is Euclidean distance.

• base (float, optional) – Base for the exponential scale. Default 2.0.

Examples

>>> import numpy as np
>>> points = np.random.rand(100, 3)
>>> tree = CoverTree(points)
>>> result = tree.query(points[:5], k=3)

Notes

Cover trees provide theoretical guarantees based on the expansion constant of the data. For well-distributed data, queries are efficient even in high dimensions.

The implementation uses a simplified version of the original algorithm for clarity.

See also

MetricSpatialIndex

Abstract base class for metric-based spatial indices.

VPTree

Alternative metric space index using vantage points.

__init__(data, metric=None, base=2.0)

root: CoverTreeNode | None

query(X, k=1)

Query the tree for k nearest neighbors.

Parameters:

• X (array_like) – Query points of shape (n_queries, n_features) or (n_features,).

• k (int, optional) – Number of nearest neighbors. Default 1.

Returns:

result – Indices and distances of k nearest neighbors.

Return type:

NeighborResult

query_radius(X, r)

Find all points within radius r of query points.

Parameters:

• X (array_like) – Query points.

• r (float) – Query radius.

Returns:

indices – For each query, list of indices within radius.

Return type:

list of lists