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
104

//! Voronoi diagram trait.
//!
//! Computes the Voronoi diagram (dual of Delaunay triangulation) of a point set.
//! The Voronoi diagram partitions space into regions where each region contains
//! all points closer to one generator than any other.
use crate::DType;

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

use super::delaunay::Delaunay;

/// Voronoi diagram result.
#[derive(Debug, Clone)]
pub struct Voronoi<R: Runtime<DType = DType>> {
    /// Generator points (original input) `[n, d]`.
    pub points: Tensor<R>,

    /// Voronoi vertices `[n_vertices, d]`.
    /// These are the circumcenters of the Delaunay simplices.
    pub vertices: Tensor<R>,

    /// For each Voronoi region (generator), indices of vertices forming the region.
    /// Stored in CSR-like format.
    /// - ridge_vertices: concatenated vertex indices for all ridges
    /// - ridge_points: for each ridge, the two generator points it separates `[n_ridges, 2]`
    pub ridge_vertices: Tensor<R>,

    /// For each ridge, the two generator points it separates `[n_ridges, 2]` (I64 dtype).
    pub ridge_points: Tensor<R>,

    /// For each generator, indices of ridges forming its region boundary.
    /// Stored as (indices, indptr) in CSR-like format.
    pub regions_indices: Tensor<R>,
    pub regions_indptr: Tensor<R>,

    /// Point indices with unbounded regions `[n_unbounded]` (I64 dtype).
    /// Regions extending to infinity.
    pub point_region: Tensor<R>,
}

/// Algorithmic contract for Voronoi diagram operations.
///
/// All backends implementing Voronoi algorithms MUST implement this trait.
pub trait VoronoiAlgorithms<R: Runtime<DType = DType>> {
    /// Compute the Voronoi diagram of a point set.
    ///
    /// # Arguments
    ///
    /// * `points` - Generator points with shape (n, d) where n >= d+1
    ///
    /// # Returns
    ///
    /// Voronoi structure containing vertices, regions, and ridges.
    ///
    /// # Algorithm
    ///
    /// The Voronoi diagram is computed as the dual of the Delaunay triangulation:
    /// 1. Compute Delaunay triangulation
    /// 2. For each Delaunay simplex, compute circumcenter (Voronoi vertex)
    /// 3. Connect circumcenters of adjacent simplices (Voronoi edges)
    /// 4. Handle unbounded regions at the convex hull boundary
    ///
    /// # Examples
    ///
    /// ```
    /// # use numr::runtime::cpu::{CpuClient, CpuDevice};
    /// # use numr::tensor::Tensor;
    /// use solvr::spatial::VoronoiAlgorithms;
    /// # let device = CpuDevice::new();
    /// # let client = CpuClient::new(device.clone());
    /// # let points = Tensor::from_slice(&[
    /// #     0.0, 0.0,
    /// #     1.0, 0.0,
    /// #     0.5, 1.0,
    /// # ], &[3, 2], &device);
    /// let vor = client.voronoi(&points)?;
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    fn voronoi(&self, points: &Tensor<R>) -> Result<Voronoi<R>>;

    /// Compute the Voronoi diagram from an existing Delaunay triangulation.
    ///
    /// More efficient when you already have the Delaunay triangulation.
    fn voronoi_from_delaunay(&self, tri: &Delaunay<R>) -> Result<Voronoi<R>>;

    /// Find which Voronoi region contains each query point.
    ///
    /// # Arguments
    ///
    /// * `vor` - The Voronoi diagram
    /// * `query` - Query points with shape (m, d)
    ///
    /// # Returns
    ///
    /// Tensor `[m]` (I64 dtype) with generator (region) indices.
    fn voronoi_find_region(&self, vor: &Voronoi<R>, query: &Tensor<R>) -> Result<Tensor<R>>;
}

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