SciRS2 Spatial

scirs2-spatial is the spatial algorithms and computational geometry crate for the SciRS2 scientific computing library. It provides spatial data structures, distance metrics, geometric algorithms, geospatial utilities, and path planning tools modeled after SciPy's spatial module.

What scirs2-spatial Provides

Use scirs2-spatial when you need to:

• Query nearest neighbors efficiently in 2D, 3D, or high-dimensional spaces
• Compute pairwise distance matrices with many distance metrics
• Build Voronoi diagrams, Delaunay triangulations, or convex hulls
• Work with geospatial data (geodesic distances, map projections, Moran's I)
• Perform spatial joins or grid-based indexing
• Analyze trajectories or point clouds
• Plan paths in continuous space (A*, RRT)
• Apply 3D transformations (quaternions, rigid transforms, SLERP)

Features (v0.3.0)

Spatial Data Structures

• KD-Tree: Efficient k-nearest neighbor and radius search in any dimension
• Ball Tree: Optimized for high-dimensional data (>10D)
• R-Tree*: Improved R-tree variant for spatial indexing of 2D/3D bounding boxes
• Octree: 3D spatial partitioning for point clouds
• Quadtree: 2D spatial partitioning
• Grid Index: Hash-grid for fast spatial lookup at fixed resolution

Distance Metrics (20+ metrics)

• Euclidean, Manhattan (L1), Chebyshev (L-inf), Minkowski
• Mahalanobis (covariance-weighted)
• Cosine, correlation, Canberra
• Hamming, Jaccard, Bray-Curtis
• SIMD-accelerated computation for f32 and f64
• Pairwise distance matrices (pdist, cdist, squareform)

Set-Based Distances

• Hausdorff distance (directed and symmetric)
• Wasserstein distance (Earth Mover's Distance)
• Gromov-Hausdorff distance (metric space comparison)

Computational Geometry

• Convex hull (2D and 3D) with degenerate case handling
• Delaunay triangulation with numerical stability
• Voronoi diagrams via Fortune's sweep line algorithm
• Alpha shapes and halfspace intersection
• Polygon operations (point-in-polygon, area, centroid, boolean ops)
• 3D convex hull (incremental algorithm)

Geospatial Data

• Geodesic distance calculations (Haversine, Vincenty)
• Map projections (Mercator, Lambert, equirectangular)
• Geographic coordinate system conversions (WGS84, UTM)
• Topography analysis (slope, aspect, curvature)
• Spatial statistics: Moran's I (spatial autocorrelation), Ripley's K function

Spatial Join Operations

• Point-in-polygon join
• Distance-based spatial join
• Nearest-neighbor spatial join between two datasets

Voronoi Diagrams

• Fortune's sweep line algorithm for exact 2D Voronoi
• Handles degenerate inputs (collinear points, coincident points)
• Furthest-site Voronoi variant

Trajectory Analysis

• Trajectory smoothing and simplification (Ramer-Douglas-Peucker)
• Frechet distance between trajectories
• Dynamic time warping (DTW) for trajectory similarity
• Speed, acceleration, and curvature analysis

Point Cloud Processing

• Normal estimation via PCA
• Outlier removal (statistical, radius-based)
• Voxel grid downsampling
• Point cloud registration (ICP - see scirs2-vision for full pipeline)

Path Planning

• A* on grids and continuous spaces
• RRT (Rapidly-exploring Random Tree)
• RRT* (asymptotically optimal)
• Probabilistic Roadmap Method (PRM)
• Visibility graphs
• Dubins and Reeds-Shepp paths for car-like robots

3D Transformations

• Rotation representations: quaternions, rotation matrices, Euler angles
• Rigid body transforms and pose composition
• Spherical coordinate transformations
• SLERP rotation interpolation and rotation splines
• Procrustes analysis (shape alignment)

Spatial Interpolation

• Kriging (Simple and Ordinary)
• Inverse Distance Weighting (IDW)
• Radial Basis Functions (RBF)
• Natural neighbor interpolation
• Shepard's method

Geometric Algorithms

• Sweep line algorithms for line segment intersection
• Point location in planar subdivisions
• Arrangement computation
• Simplification of polylines and polygons (Visvalingam-Whyatt)

Collision Detection

• Primitive shape collision (circles, spheres, AABB, OBB)
• Continuous collision detection (swept volumes)
• Broad-phase (BVH) and narrow-phase algorithms

Installation

[dependencies]
scirs2-spatial = "0.3.0"

For parallel processing:

[dependencies]
scirs2-spatial = { version = "0.3.0", features = ["parallel"] }

Quick Start

KD-Tree Nearest Neighbor Search

use scirs2_spatial::KDTree;
use scirs2_core::ndarray::array;
use scirs2_core::error::CoreResult;

fn kdtree_example() -> CoreResult<()> {
    let points = array![
        [2.0f64, 3.0],
        [5.0, 4.0],
        [9.0, 6.0],
        [4.0, 7.0],
        [8.0, 1.0],
    ];

    let tree = KDTree::new(&points)?;

    // Single nearest neighbor
    let (indices, distances) = tree.query(&[6.0, 5.0], 1)?;
    println!("Nearest: index={}, dist={}", indices[0], distances[0]);

    // k nearest neighbors
    let (indices, distances) = tree.query(&[6.0, 5.0], 3)?;
    println!("3-nearest indices: {:?}", indices);

    // Radius search
    let (indices, distances) = tree.query_radius(&[6.0, 5.0], 3.0)?;
    println!("Points within radius 3: {}", indices.len());

    Ok(())
}

Distance Metrics

use scirs2_spatial::distance;
use scirs2_core::error::CoreResult;

fn distance_example() -> CoreResult<()> {
    let p1 = [1.0f64, 2.0, 3.0];
    let p2 = [4.0, 5.0, 6.0];

    let euclidean = distance::euclidean(&p1, &p2);
    let manhattan = distance::manhattan(&p1, &p2);
    let cosine = distance::cosine(&p1, &p2);

    println!("Euclidean: {:.4}", euclidean);
    println!("Manhattan: {:.4}", manhattan);
    println!("Cosine: {:.4}", cosine);

    Ok(())
}

Pairwise Distance Matrix

use scirs2_spatial::distance;
use scirs2_core::ndarray::array;
use scirs2_core::error::CoreResult;

fn cdist_example() -> CoreResult<()> {
    let set_a = array![[0.0f64, 0.0], [1.0, 0.0], [0.0, 1.0]];
    let set_b = array![[1.0f64, 1.0], [2.0, 2.0]];

    let dist_matrix = distance::cdist(&set_a.view(), &set_b.view(), "euclidean")?;
    println!("Distance matrix shape: {:?}", dist_matrix.shape());

    Ok(())
}

Voronoi Diagram

use scirs2_spatial::voronoi::Voronoi;
use scirs2_core::ndarray::array;
use scirs2_core::error::CoreResult;

fn voronoi_example() -> CoreResult<()> {
    let points = array![
        [0.0f64, 0.0],
        [1.0, 0.0],
        [0.5, 0.866],
        [0.5, 0.5],
    ];

    let vor = Voronoi::new(&points.view(), false)?;
    println!("Voronoi vertices: {}", vor.vertices().len());
    println!("Ridge count: {}", vor.ridge_points().len());

    Ok(())
}

Geospatial Distance

use scirs2_spatial::geo::{haversine_distance, vincenty_distance};
use scirs2_core::error::CoreResult;

fn geo_example() -> CoreResult<()> {
    // Tokyo coordinates
    let lat1 = 35.6762_f64;
    let lon1 = 139.6503_f64;
    // New York coordinates
    let lat2 = 40.7128_f64;
    let lon2 = -74.0060_f64;

    let dist_km = haversine_distance(lat1, lon1, lat2, lon2);
    println!("Haversine distance: {:.1} km", dist_km / 1000.0);

    Ok(())
}

Spatial Statistics (Moran's I)

use scirs2_spatial::advanced_spatial_stats::morans_i;
use scirs2_core::error::CoreResult;

fn spatial_stats_example() -> CoreResult<()> {
    // let values = ...;  // observed values at each location
    // let weights = ...; // spatial weights matrix (e.g., contiguity or distance-based)
    // let (i_stat, p_value) = morans_i(&values, &weights)?;
    // println!("Moran's I = {:.4}, p = {:.4}", i_stat, p_value);
    Ok(())
}

R*-Tree Spatial Index

use scirs2_spatial::rtree::RStarTree;
use scirs2_core::error::CoreResult;

fn rtree_example() -> CoreResult<()> {
    let mut rtree = RStarTree::new();
    // Insert bounding boxes (min_x, min_y, max_x, max_y) with IDs
    // rtree.insert([0.0, 0.0, 1.0, 1.0], 0)?;
    // rtree.insert([1.5, 1.5, 2.5, 2.5], 1)?;

    // Query intersecting bounding boxes
    // let results = rtree.search([0.5, 0.5, 2.0, 2.0])?;
    Ok(())
}

Feature Flags

Performance

• SIMD-accelerated distance metrics (Euclidean, Manhattan, Chebyshev): up to 2x speedup for f32
• 1.5-25 million distance calculations per second (hardware dependent)
• KD-Tree: 20K+ nearest-neighbor queries per second (10K point dataset)
• Linear memory scaling with point count

Documentation

Full API reference: docs.rs/scirs2-spatial

Compatibility

The API is modeled after SciPy's scipy.spatial module. Key equivalents:

License

Licensed under the Apache License 2.0. See LICENSE for details.