Module convex_hull

scirs2_spatial

Module convex_hull 

Source
Expand description

Convex hull algorithms and utilities

This module provides comprehensive convex hull computation capabilities, supporting multiple algorithms and dimensions. It includes geometric property calculations and robust point containment testing.

§Overview

A convex hull is the smallest convex set that contains all given points. This module provides:

  • Multiple algorithms: QHull (nD), Graham Scan (2D), Jarvis March (2D)
  • Geometric properties: Volume, surface area, compactness measures
  • Point queries: Containment testing, distance calculations
  • Robust handling: Special cases, degenerate inputs, numerical precision

§Quick Start

§Basic Usage

use scirs2_spatial::convex_hull::{ConvexHull, convex_hull};
use scirs2_core::ndarray::array;

// Create points for the convex hull
let points = array![[0.0, 0.0], [1.0, 0.0], [0.0, 1.0], [0.5, 0.5]];

// Compute convex hull (automatic algorithm selection)
let hull = ConvexHull::new(&points.view()).unwrap();

// Or use the convenience function
let hull_vertices = convex_hull(&points.view()).unwrap();

// Access hull properties
println!("Hull vertices: {:?}", hull.vertices());
println!("Hull volume: {}", hull.volume().unwrap());
println!("Hull surface area: {}", hull.area().unwrap());

// Test point containment
let is_inside = hull.contains(&[0.25, 0.25]).unwrap();
println!("Point inside: {}", is_inside);

§Algorithm Selection

use scirs2_spatial::convex_hull::{ConvexHull, ConvexHullAlgorithm, convex_hull_with_algorithm};
use scirs2_core::ndarray::array;

let points = array![[0.0, 0.0], [1.0, 0.0], [0.0, 1.0], [0.5, 0.5]];

// Use specific algorithm
let hull = ConvexHull::new_with_algorithm(&points.view(), ConvexHullAlgorithm::GrahamScan).unwrap();

// Or use convenience function
let hull_vertices = convex_hull_with_algorithm(&points.view(), ConvexHullAlgorithm::JarvisMarch).unwrap();

§Comprehensive Analysis

use scirs2_spatial::convex_hull::{ConvexHull, analyze_hull};
use scirs2_core::ndarray::array;

let points = array![[0.0, 0.0], [1.0, 0.0], [1.0, 1.0], [0.0, 1.0]];
let hull = ConvexHull::new(&points.view()).unwrap();

// Get comprehensive analysis
let analysis = analyze_hull(&hull).unwrap();
println!("Hull Analysis: {:#?}", analysis);

§Module Organization

  • core - Core ConvexHull struct and basic functionality
  • algorithms - Algorithm implementations (QHull, Graham Scan, Jarvis March)
  • geometry - Geometric utility functions for different dimensions
  • properties - Volume, surface area, and containment calculations

§Algorithm Guide

  • Dimensions: 1D, 2D, 3D, nD
  • Time Complexity: O(n log n) for 2D/3D, O(n^⌊d/2⌋) for higher dimensions
  • Features: Robust, handles degenerate cases, provides facet equations
  • Use when: General-purpose convex hull computation

§Graham Scan (2D only)

  • Dimensions: 2D only
  • Time Complexity: O(n log n)
  • Features: Simple, produces vertices in counterclockwise order
  • Use when: Educational purposes, guaranteed vertex ordering needed

§Jarvis March / Gift Wrapping (2D only)

  • Dimensions: 2D only
  • Time Complexity: O(nh) where h is number of hull vertices
  • Features: Output-sensitive, good for sparse hulls
  • Use when: Hull has few vertices compared to input size

§Performance Tips

  1. Use QHull for general cases - it’s the most robust and efficient
  2. For 2D with small hulls - consider Jarvis March for output-sensitive performance
  3. For large datasets - consider preprocessing to remove interior points
  4. For high dimensions - expect exponential complexity, consider approximations

§Error Handling

The module handles various error conditions gracefully:

  • Insufficient points for given dimension
  • Algorithm/dimension mismatches
  • Degenerate point configurations
  • Numerical precision issues

Re-exports§

pub use core::ConvexHull;
pub use core::ConvexHullAlgorithm;
pub use algorithms::compute_graham_scan;
pub use algorithms::compute_jarvis_march;
pub use algorithms::compute_qhull;
pub use algorithms::get_algorithm_complexity;
pub use algorithms::recommend_algorithm;
pub use geometry::compute_polygon_area;
pub use geometry::compute_polygon_perimeter;
pub use geometry::compute_polyhedron_volume;
pub use geometry::cross_product_2d;
pub use geometry::cross_product_3d;
pub use geometry::tetrahedron_volume;
pub use geometry::triangle_area_3d;
pub use properties::analyze_hull;
pub use properties::check_point_containment;
pub use properties::compute_surface_area;
pub use properties::compute_volume;
pub use properties::get_hull_statistics;

Modules§

advanced
Extended analysis and statistics for debugging and research
algorithms
Convex hull algorithm implementations
core
Core ConvexHull structure and basic methods
geometry
Geometric utility functions for convex hull computations
properties
Convex hull properties and analysis

Functions§

convex_hull
Compute the convex hull of a set of points using the default algorithm
convex_hull_with_algorithm
Compute the convex hull of a set of points using a specific algorithm