scirs2_spatial/computational_geometry/
mod.rs

1//! Computational geometry algorithms
2//!
3//! This module provides a collection of fundamental computational geometry algorithms
4//! including sweep line intersection detection, bounding rectangle computation,
5//! Fortune's algorithm for Voronoi diagrams, and incremental 3D convex hull construction.
6//!
7//! # Modules
8//!
9//! - [`sweep_line`] - Bentley-Ottmann sweep line algorithm for line segment intersections
10//! - [`bounding`] - Minimum bounding rectangles, AABB, polygon perimeter/area utilities
11//! - [`fortune_voronoi`] - Fortune's sweep line algorithm for Voronoi diagram construction
12//! - [`incremental_hull_3d`] - Incremental 3D convex hull using DCEL data structure
13//!
14//! # Examples
15//!
16//! ## Line Segment Intersection Detection
17//!
18//! ```
19//! use scirs2_spatial::computational_geometry::sweep_line::{Segment2D, find_all_intersections};
20//!
21//! let segments = vec![
22//!     Segment2D::new(0.0, 0.0, 2.0, 2.0),
23//!     Segment2D::new(0.0, 2.0, 2.0, 0.0),
24//! ];
25//!
26//! let intersections = find_all_intersections(&segments).expect("Operation failed");
27//! assert_eq!(intersections.len(), 1);
28//! ```
29//!
30//! ## Bounding Rectangle
31//!
32//! ```
33//! use scirs2_spatial::computational_geometry::bounding::{axis_aligned_bounding_box, polygon_perimeter};
34//! use scirs2_core::ndarray::array;
35//!
36//! let points = array![[0.0, 0.0], [1.0, 0.0], [1.0, 1.0], [0.0, 1.0]];
37//! let aabb = axis_aligned_bounding_box(&points.view()).expect("Operation failed");
38//! assert!((aabb.area() - 1.0).abs() < 1e-10);
39//! ```
40//!
41//! ## Fortune's Voronoi
42//!
43//! ```
44//! use scirs2_spatial::computational_geometry::fortune_voronoi::fortune_voronoi_2d;
45//!
46//! let sites = vec![[0.0, 0.0], [1.0, 0.0], [0.5, 1.0]];
47//! let diagram = fortune_voronoi_2d(&sites).expect("Operation failed");
48//! assert_eq!(diagram.num_sites(), 3);
49//! ```
50//!
51//! ## 3D Convex Hull
52//!
53//! ```
54//! use scirs2_spatial::computational_geometry::incremental_hull_3d::IncrementalHull3D;
55//!
56//! let points = vec![
57//!     [0.0, 0.0, 0.0], [1.0, 0.0, 0.0],
58//!     [0.0, 1.0, 0.0], [0.0, 0.0, 1.0],
59//! ];
60//! let hull = IncrementalHull3D::new(&points).expect("Operation failed");
61//! assert_eq!(hull.num_faces(), 4);
62//! ```
63
64pub mod bounding;
65pub mod fortune_voronoi;
66pub mod incremental_hull_3d;
67pub mod sweep_line;
68
69// Re-export key types for convenience
70pub use bounding::{
71    axis_aligned_bounding_box, convex_hull_area, convex_hull_area_perimeter, convex_hull_perimeter,
72    is_convex, minimum_bounding_rectangle, point_set_diameter, point_set_width, polygon_perimeter,
73    signed_polygon_area, OrientedBoundingRect, AABB,
74};
75
76pub use sweep_line::{
77    count_intersections, find_all_intersections, find_all_intersections_brute_force,
78    has_any_intersection, segment_intersection, Intersection, Segment2D,
79};
80
81pub use fortune_voronoi::{
82    fortune_voronoi_2d, fortune_voronoi_from_array, VoronoiCell, VoronoiDiagram, VoronoiEdge,
83    VoronoiVertex,
84};
85
86pub use incremental_hull_3d::{HullFace, IncrementalHull3D};
scirs2_spatial/computational_geometry/mod.rs

scirs2_spatial/computational_geometry/
mod.rs
