solvr 0.2.0

Advanced computing library for real-world problem solving - optimization, differential equations, interpolation, statistics, and more
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

//! Convex hull trait.
//!
//! Computes the convex hull of a set of points. Uses Graham scan for 2D
//! and Quickhull for 3D and higher dimensions.
use crate::DType;

use numr::error::Result;
use numr::runtime::Runtime;
use numr::tensor::Tensor;

/// Convex hull result.
#[derive(Debug, Clone)]
pub struct ConvexHull<R: Runtime<DType = DType>> {
    /// Original points `[n, d]`.
    pub points: Tensor<R>,

    /// Vertex indices on the hull boundary `[n_vertices]` (I64 dtype).
    /// For 2D: ordered counterclockwise.
    /// For 3D+: unordered set of vertices on hull.
    pub vertices: Tensor<R>,

    /// Simplices (facets) of the hull `[n_simplices, d]` (I64 dtype).
    /// For 2D: edges as pairs of vertex indices.
    /// For 3D: triangular faces as triples of vertex indices.
    /// For nD: (n-1)-simplices as n-tuples of vertex indices.
    pub simplices: Tensor<R>,

    /// For 3D+: neighboring simplex indices `[n_simplices, d]` (I64 dtype).
    /// `neighbors[i, j]` is the simplex sharing facet opposite to vertex j.
    /// -1 indicates no neighbor (boundary).
    pub neighbors: Option<Tensor<R>>,

    /// Equations of the hyperplanes for each simplex `[n_simplices, d+1]`.
    /// For each simplex, (A, b) where Ax + b = 0 defines the hyperplane.
    /// The first d values are the normal A, the last is the offset b.
    pub equations: Option<Tensor<R>>,

    /// Volume (2D: area, 3D: volume) of the convex hull.
    pub volume: f64,

    /// Surface area of the convex hull.
    /// For 2D: perimeter.
    /// For 3D: surface area.
    pub area: f64,
}

/// Algorithmic contract for convex hull operations.
///
/// All backends implementing convex hull algorithms MUST implement this trait.
pub trait ConvexHullAlgorithms<R: Runtime<DType = DType>> {
    /// Compute the convex hull of a point set.
    ///
    /// # Arguments
    ///
    /// * `points` - Point set with shape (n, d) where n >= d+1
    ///
    /// # Returns
    ///
    /// ConvexHull structure containing vertices, simplices, and geometry info.
    ///
    /// # Algorithm
    ///
    /// - 2D: Graham scan - O(n log n)
    /// - 3D+: Quickhull - O(n log n) average, O(n²) worst case
    ///
    /// # Examples
    ///
    /// ```
    /// # use numr::runtime::cpu::{CpuClient, CpuDevice};
    /// # use numr::tensor::Tensor;
    /// use solvr::spatial::ConvexHullAlgorithms;
    /// # let device = CpuDevice::new();
    /// # let client = CpuClient::new(device.clone());
    /// // 2D point set
    /// # let points = Tensor::from_slice(&[
    /// #     0.0, 0.0,
    /// #     1.0, 0.0,
    /// #     1.0, 1.0,
    /// #     0.0, 1.0,
    /// #     0.5, 0.5,
    /// # ], &[5, 2], &device);
    /// let hull = client.convex_hull(&points)?;
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    fn convex_hull(&self, points: &Tensor<R>) -> Result<ConvexHull<R>>;

    /// Test if points are inside the convex hull.
    ///
    /// # Arguments
    ///
    /// * `hull` - The convex hull
    /// * `points` - Test points with shape (m, d)
    ///
    /// # Returns
    ///
    /// Boolean tensor `[m]` where true indicates the point is inside or on the hull.
    fn convex_hull_contains(&self, hull: &ConvexHull<R>, points: &Tensor<R>) -> Result<Tensor<R>>;
}

#[cfg(test)]
mod tests {
    // Tests will be in the implementation files
}