Expand description
Spatial algorithms module
This module provides implementations of various spatial algorithms,
similar to SciPy’s spatial module.
§Overview
- Distance computations and metrics
- KD-trees for efficient nearest neighbor searches
- Ball trees for high-dimensional nearest neighbor searches
- Voronoi diagrams and Delaunay triangulation
- Convex hulls
- Set-based distances (Hausdorff, Wasserstein)
- Polygon operations
- Spatial transformations
- Path planning algorithms
§Features
- Efficient nearest-neighbor queries with KD-Tree and Ball Tree data structures
- Comprehensive set of distance metrics (Euclidean, Manhattan, Minkowski, etc.)
- Distance matrix computations (similar to SciPy’s cdist and pdist)
- Convex hull computation using the Qhull library
- Delaunay triangulation for 2D and higher dimensions
- Customizable distance metrics for spatial data structures
- Advanced query capabilities (k-nearest neighbors, radius search)
- Set-based distances (Hausdorff, Wasserstein)
- Polygon operations (point-in-polygon, area, centroid)
- Path planning algorithms (A*, RRT, visibility graphs)
§Examples
§Distance Metrics
use scirs2_spatial::distance::euclidean;
let point1 = &[1.0, 2.0, 3.0];
let point2 = &[4.0, 5.0, 6.0];
let dist = euclidean(point1, point2);
println!("Euclidean distance: {}", dist);§KD-Tree for Nearest Neighbor Searches
use scirs2_spatial::KDTree;
use ndarray::array;
// Create points
let points = array![[0.0, 0.0], [1.0, 0.0], [0.0, 1.0], [1.0, 1.0]];
// Build KD-Tree
let kdtree = KDTree::new(&points).unwrap();
// Find 2 nearest neighbors to [0.5, 0.5]
let (indices, distances) = kdtree.query(&[0.5, 0.5], 2).unwrap();
println!("Indices of 2 nearest points: {:?}", indices);
println!("Distances to 2 nearest points: {:?}", distances);
// Find all points within radius 0.7
let (idx_radius, dist_radius) = kdtree.query_radius(&[0.5, 0.5], 0.7).unwrap();
println!("Found {} points within radius 0.7", idx_radius.len());§Distance Matrices
use scirs2_spatial::distance::{pdist, euclidean};
use ndarray::array;
// Create points
let points = array![[0.0, 0.0], [1.0, 0.0], [0.0, 1.0]];
// Calculate pairwise distance matrix
let dist_matrix = pdist(&points, euclidean);
println!("Distance matrix shape: {:?}", dist_matrix.shape());§Convex Hull
use scirs2_spatial::convex_hull::ConvexHull;
use ndarray::array;
// Create points
let points = array![[0.0, 0.0], [1.0, 0.0], [0.0, 1.0], [0.5, 0.5]];
// Compute convex hull
let hull = ConvexHull::new(&points.view()).unwrap();
// Get the hull vertices
let vertices = hull.vertices();
println!("Hull vertices: {:?}", vertices);
// Check if a point is inside the hull
let is_inside = hull.contains(&[0.25, 0.25]).unwrap();
println!("Is point [0.25, 0.25] inside? {}", is_inside);§Delaunay Triangulation
use scirs2_spatial::delaunay::Delaunay;
use ndarray::array;
// Create points
let points = array![[0.0, 0.0], [1.0, 0.0], [0.0, 1.0], [1.0, 1.0]];
// Compute Delaunay triangulation
let tri = Delaunay::new(&points).unwrap();
// Get the simplices (triangles in 2D)
let simplices = tri.simplices();
println!("Triangles: {:?}", simplices);
// Find which triangle contains a point
if let Some(idx) = tri.find_simplex(&[0.25, 0.25]) {
println!("Point [0.25, 0.25] is in triangle {}", idx);
}§Set-Based Distances
use scirs2_spatial::set_distance::hausdorff_distance;
use ndarray::array;
// Create two point sets
let set1 = array![[0.0, 0.0], [1.0, 0.0], [0.0, 1.0]];
let set2 = array![[0.0, 0.5], [1.0, 0.5], [0.5, 1.0]];
// Compute the Hausdorff distance
let dist = hausdorff_distance(&set1.view(), &set2.view(), None);
println!("Hausdorff distance: {}", dist);§Polygon Operations
use scirs2_spatial::polygon::{point_in_polygon, polygon_area, polygon_centroid};
use ndarray::array;
// Create a polygon (square)
let polygon = array![[0.0, 0.0], [1.0, 0.0], [1.0, 1.0], [0.0, 1.0]];
// Check if a point is inside
let inside = point_in_polygon(&[0.5, 0.5], &polygon.view());
println!("Is point [0.5, 0.5] inside? {}", inside);
// Calculate polygon area
let area = polygon_area(&polygon.view());
println!("Polygon area: {}", area);
// Calculate centroid
let centroid = polygon_centroid(&polygon.view());
println!("Polygon centroid: ({}, {})", centroid[0], centroid[1]);§Ball Tree for Nearest Neighbor Searches
use scirs2_spatial::BallTree;
use ndarray::array;
// Create points
let points = array![[0.0, 0.0], [1.0, 0.0], [0.0, 1.0], [1.0, 1.0]];
// Build Ball Tree
let ball_tree = BallTree::with_euclidean_distance(&points.view(), 2).unwrap();
// Find 2 nearest neighbors to [0.5, 0.5]
let (indices, distances) = ball_tree.query(&[0.5, 0.5], 2, true).unwrap();
println!("Indices of 2 nearest points: {:?}", indices);
println!("Distances to 2 nearest points: {:?}", distances.unwrap());
// Find all points within radius 0.7
let (idx_radius, dist_radius) = ball_tree.query_radius(&[0.5, 0.5], 0.7, true).unwrap();
println!("Found {} points within radius 0.7", idx_radius.len());§A* Pathfinding
use scirs2_spatial::pathplanning::GridAStarPlanner;
// Create a grid with some obstacles (true = obstacle, false = free space)
let grid = vec![
vec![false, false, false, false, false],
vec![false, false, false, false, false],
vec![false, true, true, true, false], // A wall of obstacles
vec![false, false, false, false, false],
vec![false, false, false, false, false],
];
// Create an A* planner with the grid
let planner = GridAStarPlanner::new(grid, false);
// Find a path from top-left to bottom-right
let start = [0, 0];
let goal = [4, 4];
let path = planner.find_path(start, goal).unwrap().unwrap();
println!("Found a path with {} steps:", path.len() - 1);
for (i, pos) in path.nodes.iter().enumerate() {
println!(" Step {}: {:?}", i, pos);
}§RRT Pathfinding
use scirs2_spatial::pathplanning::{RRTConfig, RRT2DPlanner};
// Create a configuration for RRT
let config = RRTConfig {
max_iterations: 1000,
step_size: 0.3,
goal_bias: 0.1,
seed: Some(42),
use_rrt_star: false,
neighborhood_radius: None,
bidirectional: false,
};
// Define obstacles as polygons
let obstacles = vec![
// Rectangle obstacle
vec![[3.0, 2.0], [3.0, 4.0], [4.0, 4.0], [4.0, 2.0]],
];
// Create RRT planner
let mut planner = RRT2DPlanner::new(
config,
obstacles,
[0.0, 0.0], // Min bounds
[10.0, 10.0], // Max bounds
0.1, // Collision checking step size
).unwrap();
// Find a path from start to goal
let start = [1.0, 3.0];
let goal = [8.0, 3.0];
let goal_threshold = 0.5;
let path = planner.find_path(start, goal, goal_threshold).unwrap().unwrap();
println!("Found a path with {} segments:", path.len() - 1);
for (i, pos) in path.nodes.iter().enumerate() {
println!(" Point {}: [{:.2}, {:.2}]", i, pos[0], pos[1]);
}Re-exports§
pub use error::SpatialError;pub use error::SpatialResult;pub use distance::canberra;pub use distance::cdist;pub use distance::chebyshev;pub use distance::correlation;pub use distance::cosine;pub use distance::euclidean;pub use distance::is_valid_condensed_distance_matrix;pub use distance::jaccard;pub use distance::manhattan;pub use distance::minkowski;pub use distance::pdist;pub use distance::sqeuclidean;pub use distance::squareform;pub use distance::squareform_to_condensed;pub use distance::ChebyshevDistance;pub use distance::Distance;pub use distance::EuclideanDistance;pub use distance::ManhattanDistance;pub use distance::MinkowskiDistance;pub use kdtree::KDTree;pub use kdtree::Rectangle;pub use kdtree_optimized::KDTreeOptimized;pub use balltree::BallTree;pub use delaunay::Delaunay;pub use voronoi::voronoi;pub use voronoi::Voronoi;pub use spherical_voronoi::SphericalVoronoi;pub use procrustes::procrustes;pub use procrustes::procrustes_extended;pub use procrustes::ProcrustesParams;pub use convex_hull::convex_hull;pub use convex_hull::ConvexHull;pub use set_distance::directed_hausdorff;pub use set_distance::gromov_hausdorff_distance;pub use set_distance::hausdorff_distance;pub use set_distance::wasserstein_distance;pub use polygon::convex_hull_graham;pub use polygon::is_simple_polygon;pub use polygon::point_in_polygon;pub use polygon::point_on_boundary;pub use polygon::polygon_area;pub use polygon::polygon_centroid;pub use polygon::polygon_contains_polygon;pub use rtree::RTree;pub use rtree::Rectangle as RTreeRectangle;pub use octree::BoundingBox;pub use octree::Octree;pub use quadtree::BoundingBox2D;pub use quadtree::Quadtree;pub use interpolate::IDWInterpolator;pub use interpolate::NaturalNeighborInterpolator;pub use interpolate::RBFInterpolator;pub use interpolate::RBFKernel;pub use pathplanning::astar::AStarPlanner;pub use pathplanning::astar::ContinuousAStarPlanner;pub use pathplanning::astar::GridAStarPlanner;pub use pathplanning::astar::Node;pub use pathplanning::astar::Path;pub use pathplanning::rrt::RRT2DPlanner;pub use pathplanning::rrt::RRTConfig;pub use pathplanning::rrt::RRTPlanner;pub use collision::shapes::Box2D;pub use collision::shapes::Box3D;pub use collision::shapes::Circle;pub use collision::shapes::LineSegment2D;pub use collision::shapes::LineSegment3D;pub use collision::shapes::Sphere;pub use collision::shapes::Triangle2D;pub use collision::shapes::Triangle3D;pub use collision::narrowphase::box2d_box2d_collision;pub use collision::narrowphase::box3d_box3d_collision;pub use collision::narrowphase::circle_box2d_collision;pub use collision::narrowphase::circle_circle_collision;pub use collision::narrowphase::point_box2d_collision;pub use collision::narrowphase::point_box3d_collision;pub use collision::narrowphase::point_circle_collision;pub use collision::narrowphase::point_sphere_collision;pub use collision::narrowphase::point_triangle2d_collision;pub use collision::narrowphase::ray_box3d_collision;pub use collision::narrowphase::ray_sphere_collision;pub use collision::narrowphase::ray_triangle3d_collision;pub use collision::narrowphase::sphere_box3d_collision;pub use collision::narrowphase::sphere_sphere_collision;pub use collision::continuous::continuous_sphere_sphere_collision;
Modules§
- balltree
- Ball tree for efficient nearest neighbor searches
- collision
- Collision detection algorithms for various geometric primitives
- convex_
hull - Convex hull algorithms
- delaunay
- Delaunay triangulation algorithms
- distance
- Distance metrics for spatial data
- error
- Error types for the SciRS2 spatial module
- interpolate
- Spatial interpolation methods
- kdtree
- KD-Tree for efficient nearest neighbor searches
- kdtree_
optimized - KD-Tree optimizations for common spatial operations
- octree
- Octree data structure for 3D space
- pathplanning
- Path planning algorithms
- polygon
- Polygon operations module
- procrustes
- Procrustes analysis
- quadtree
- Quadtree data structure for 2D space
- rtree
- R-tree implementation for efficient spatial indexing
- set_
distance - Set-based distance metrics
- spherical_
voronoi - SphericalVoronoi Implementation
- transform
- Spatial transformations module
- voronoi
- Voronoi diagrams