spart 0.3.0

A collection of space partitioning trees for Rust

Spart (space partitioning trees) is a Rust library that provides implementations of several common space partitioning tree data structures that can be used for indexing 2D and 3D point data to perform fast spatial queries, like k-nearest neighbor (kNN) and range search.

The library also includes Python bindings (see pyspart), so it can easily be used in Python applications.

At the moment, the following tree data structures and features are supported:

[!IMPORTANT] Spart is in early development, so bugs and breaking API changes are expected. Please use the issues page to report bugs or request features.

Installation

cargo add spart

Spart requires Rust 1.83.0 or later.

Python Bindings

You can install the Python bindings for Spart using pip:

pip install pyspart

Check out the pyspart directory for more information about using Spart from Python.

Documentation

For the Rust API documentation, see docs.rs/spart.

Basic Concepts

The basic building blocks of Spart are point and tree.

Point

A point is a tuple of coordinates plus an optional data payload of any type. There are two types of points: Point2D and Point3D.

Example of 2D and 3D points:

use spart::geometry::{Point2D, Point3D};

fn main() {
    // There are two ways to create a point.

    // 1. Using the `new` method:
    let point_2d = Point2D::new(1.0, 2.0, Some("A 2D Point"));
    let point_3d = Point3D::new(1.0, 2.0, 3.0, Some("A 3D Point"));

    // 2. Using a struct literal:
    let point_2d_literal = Point2D {
        x: 1.0,
        y: 2.0,
        data: Some("A 2D Point"),
    };
    let point_3d_literal = Point3D {
        x: 1.0,
        y: 2.0,
        z: 3.0,
        data: Some("A 3D Point"),
    };
}

Tree

A tree is a spatial data structure that indexes points and provides methods for querying them.

Currently, the following trees are implemented:

• Quadtree (2D)
• Octree (3D)
• Kd-tree (2D and 3D)
• R-tree (2D and 3D)
• R*-tree (2D and 3D)

A tree provides at least the following methods:

• new: creates a new tree given the following parameters:
  • The bounding area of the tree (for Quadtree and Octree only)
  • The number of dimensions (for Kd-tree only)
  • The maximum capacity of points per node (for Quadtree, Octree, and R-tree)
• insert: inserts a point into the tree.
• insert_bulk: inserts multiple points into the tree at once.
  • This is generally more efficient than inserting points one by one.
• delete: removes a point from the tree.
• knn_search: finds the k nearest neighbors to a query point.
  • The inputs are the query point and the number of neighbors to find.
• range_search: finds all points within a given range of a query point.
  • The inputs are the query point and the range within which to search.

[!NOTE] Currently, the following properties hold for all trees:

• Duplicates are allowed: inserting a duplicate point will add another copy to the tree.
• Searches return duplicates: both knn_search and range_search can return duplicate points if they were previously inserted.
• Deletion removes one instance: if there are duplicate points, the delete operation removes only one instance of the point from the tree.
• A knn_search with k=0 will return an empty list.
• A knn_search with k greater than the number of points in the tree will return all points.
• A range_search with a radius of 0 will return only points with the exact same coordinates.

The distance metric used for nearest neighbor and range searches is the Euclidean distance by default. However, you can use a custom distance metric by implementing the DistanceMetric trait.

For example, here is how you can define and use the Manhattan distance:

use spart::geometry::{Point2D, DistanceMetric};

// 1. Define a struct for your distance metric.
struct ManhattanDistance;

// 2. Implement the `DistanceMetric` trait for your point type.
impl<T> DistanceMetric<Point2D<T>> for ManhattanDistance {
    fn distance_sq(p1: &Point2D<T>, p2: &Point2D<T>) -> f64 {
        ((p1.x - p2.x).abs() + (p1.y - p2.y).abs()).powi(2)
    }
}

// 3. Use it in a search function.
// tree.knn_search::<ManhattanDistance>(&query_point, 1);

Serialization

Spart trees can be serialized and deserialized using the serde feature.

To enable serialization in Rust, you need to enable the serde feature in your Cargo.toml file:

[dependencies]
spart = { version = "0.3.0", features = ["serde"] }

Then, you can use bincode (or any other serde-compatible library) to serialize and deserialize the tree. For example, you can save and load a tree to and from a file:

use spart::geometry::{Point2D, Rectangle};
use spart::quadtree::Quadtree;
use std::fs::File;
use std::io::{Read, Write};

fn main() {
    let boundary = Rectangle {
        x: 0.0,
        y: 0.0,
        width: 100.0,
        height: 100.0,
    };
    let mut qt = Quadtree::new(&boundary, 4).unwrap();
    qt.insert(Point2D::new(10.0, 20.0, Some("point1".to_string())));
    qt.insert(Point2D::new(50.0, 50.0, Some("point2".to_string())));

    // Serialize the tree to a file
    let encoded: Vec<u8> = bincode::serialize(&qt).unwrap();
    let mut file = File::create("tree.spart").unwrap();
    file.write_all(&encoded).unwrap();

    // Deserialize the tree from a file
    let mut file = File::open("tree.spart").unwrap();
    let mut encoded = Vec::new();
    file.read_to_end(&mut encoded).unwrap();
    let decoded: Quadtree<String> = bincode::deserialize(&encoded[..]).unwrap();
}

Debugging Mode

You can enable debugging mode for Spart by setting the DEBUG_SPART environment variable to true or 1.

# Enable debugging mode on Linux and macOS
export DEBUG_SPART=true

# Enable debugging mode on Windows (PowerShell)
$env:DEBUG_SPART = "true"

[!NOTE] When debugging mode is enabled, Spart will be very verbose. It is recommended to use this only for debugging purposes.

Examples

• For Rust examples, see the examples directory.
• For Python examples, see pyspart/examples.

Feature Roadmap

• Core Data Structures

  • Quadtree (2D)
  • Octree (3D)
  • Kd-tree (2D and 3D)
  • R-tree (2D and 3D)
  • R*-tree (2D and 3D)

• Supported Geometries and Queries

  • Point data (Point2D, Point3D)
  • kNN search
  • Circular or Spherical range search
  • Rectangular/Cuboid range search (range_search_bbox)
  • update method for moving points (currently needs delete + insert)
  • Support for storing non-point geometries (for example, lines, polygons)
  • Advanced intersection queries (like finding all stored items that intersect a given polygon)

• Performance and Optimization

  • Bulk loading implementations for faster tree construction
  • Thread-safety for concurrent reads (like &Tree accessible from multiple threads)
  • Arena allocation for tree nodes to improve cache locality
  • SIMD-accelerated distance and intersection calculations if possible

• API and Developer Experience

  • Simple API for tree creation and manipulation
  • Serialization and deserialization via serde
  • Custom distance metric support
  • Public iterators for tree traversal (something like tree.iter())
  • Tree diagnostic methods (height(), node_count(), etc.)
  • Replace internal panics with Result-based error handling (for example, for invalid dimensions)

• Ecosystem and Bindings

  • Python bindings (pyspart) for all tree types
  • Full feature parity for Python bindings (like bulk loading for all trees)
  • WebAssembly support for browser and serverless environments

• Benchmarks

  • Benchmarks for comparing the performance of tree implementations and operations
  • Benchmarks for comparing the performance against other similar libraries

Contributing

See CONTRIBUTING.md for details on how to make a contribution.

License

Spart is available under the terms of either of the following licenses:

• MIT License (LICENSE-MIT)
• Apache License, Version 2.0 (LICENSE-APACHE)

Acknowledgements

• The logo is from SVG Repo.