Module algorithms 

Convex hull algorithm implementations

This module provides different algorithms for computing convex hulls, each with their own strengths and use cases.

Available Algorithms

QHull

• Module: qhull
• Dimensions: Any (1D, 2D, 3D, nD)
• Time Complexity: O(n log n) for 2D, O(n^⌊d/2⌋) for d dimensions
• Use Case: General purpose, robust for all dimensions
• Features: Handles degenerate cases well, provides facet equations

Graham Scan

• Module: graham_scan
• Dimensions: 2D only
• Time Complexity: O(n log n)
• Use Case: Educational, guaranteed output order
• Features: Simple to understand, produces vertices in counterclockwise order

Jarvis March (Gift Wrapping)

• Module: jarvis_march
• Dimensions: 2D only
• Time Complexity: O(nh) where h is the number of hull vertices
• Use Case: When hull has few vertices (h << n)
• Features: Output-sensitive, good for small hulls

Special Cases

• Module: special_cases
• Purpose: Handle degenerate cases (collinear points, identical points, etc.)
• Features: Robust handling of edge cases that might break standard algorithms

Examples

Using QHull (Recommended)

use scirs2_spatial::convex_hull::algorithms::qhull::compute_qhull;
use scirs2_core::ndarray::array;

let points = array![[0.0, 0.0], [1.0, 0.0], [0.0, 1.0], [0.5, 0.5]];
let hull = compute_qhull(&points.view()).unwrap();
println!("Hull has {} vertices", hull.vertex_indices().len());

Using Graham Scan for 2D

use scirs2_spatial::convex_hull::algorithms::graham_scan::compute_graham_scan;
use scirs2_core::ndarray::array;

let points = array![[0.0, 0.0], [1.0, 0.0], [0.0, 1.0], [0.5, 0.5]];
let hull = compute_graham_scan(&points.view()).unwrap();
println!("Hull vertices: {:?}", hull.vertex_indices());

Using Jarvis March for Small Hulls

use scirs2_spatial::convex_hull::algorithms::jarvis_march::compute_jarvis_march;
use scirs2_core::ndarray::array;

let points = array![[0.0, 0.0], [1.0, 0.0], [0.0, 1.0], [0.5, 0.5]];
let hull = compute_jarvis_march(&points.view()).unwrap();
println!("Hull computed with {} vertices", hull.vertex_indices().len());

Handling Special Cases

use scirs2_spatial::convex_hull::algorithms::special_cases::handle_degenerate_case;
use scirs2_core::ndarray::array;

// Collinear points
let collinear = array![[0.0, 0.0], [1.0, 0.0], [2.0, 0.0]];
if let Some(result) = handle_degenerate_case(&collinear.view()) {
    let hull = result.unwrap();
    println!("Handled degenerate case with {} vertices", hull.vertex_indices().len());
}

Algorithm Selection Guidelines

• For general use: Use QHull - it’s robust and handles all dimensions
• For 2D educational purposes: Use Graham Scan for its simplicity
• For 2D with small expected hulls: Use Jarvis March for output-sensitive performance
• For edge cases: All algorithms automatically fall back to special case handlers

Performance Characteristics

Algorithm	2D Time	3D Time	nD Time	Space	Robustness
QHull	O(n log n)	O(n log n)	O(n^⌊d/2⌋)	O(n)	High
Graham Scan	O(n log n)	N/A	N/A	O(n)	Medium
Jarvis March	O(nh)	N/A	N/A	O(n)	Medium

Where:

• n = number of input points
• h = number of hull vertices
• d = dimension

Re-exports

pub use graham_scan::compute_graham_scan;

pub use jarvis_march::compute_jarvis_march;

pub use qhull::compute_qhull;

pub use special_cases::handle_degenerate_case;

pub use special_cases::has_all_identical_points;

pub use special_cases::is_all_collinear;

Modules

graham_scan

Graham scan algorithm implementation for 2D convex hull computation

jarvis_march

Jarvis march (Gift Wrapping) algorithm implementation for 2D convex hull computation

qhull

QHull algorithm implementation for convex hull computation

special_cases

Special case handlers for convex hull computation

Enums

AlgorithmComplexity

Algorithm performance characteristics for selection guidance

Functions

get_algorithm_complexity

Get performance characteristics for each algorithm

recommend_algorithm

Recommend the best algorithm for given constraints