Module computational_geometry 

Computational geometry algorithms

This module provides a collection of fundamental computational geometry algorithms including sweep line intersection detection, bounding rectangle computation, Fortune’s algorithm for Voronoi diagrams, and incremental 3D convex hull construction.

Modules

• sweep_line - Bentley-Ottmann sweep line algorithm for line segment intersections
• bounding - Minimum bounding rectangles, AABB, polygon perimeter/area utilities
• fortune_voronoi - Fortune’s sweep line algorithm for Voronoi diagram construction
• incremental_hull_3d - Incremental 3D convex hull using DCEL data structure

Examples

Line Segment Intersection Detection

use scirs2_spatial::computational_geometry::sweep_line::{Segment2D, find_all_intersections};

let segments = vec![
    Segment2D::new(0.0, 0.0, 2.0, 2.0),
    Segment2D::new(0.0, 2.0, 2.0, 0.0),
];

let intersections = find_all_intersections(&segments).expect("Operation failed");
assert_eq!(intersections.len(), 1);

Bounding Rectangle

use scirs2_spatial::computational_geometry::bounding::{axis_aligned_bounding_box, polygon_perimeter};
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 aabb = axis_aligned_bounding_box(&points.view()).expect("Operation failed");
assert!((aabb.area() - 1.0).abs() < 1e-10);

Fortune’s Voronoi

use scirs2_spatial::computational_geometry::fortune_voronoi::fortune_voronoi_2d;

let sites = vec![[0.0, 0.0], [1.0, 0.0], [0.5, 1.0]];
let diagram = fortune_voronoi_2d(&sites).expect("Operation failed");
assert_eq!(diagram.num_sites(), 3);

3D Convex Hull

use scirs2_spatial::computational_geometry::incremental_hull_3d::IncrementalHull3D;

let points = vec![
    [0.0, 0.0, 0.0], [1.0, 0.0, 0.0],
    [0.0, 1.0, 0.0], [0.0, 0.0, 1.0],
];
let hull = IncrementalHull3D::new(&points).expect("Operation failed");
assert_eq!(hull.num_faces(), 4);

Re-exports

pub use bounding::axis_aligned_bounding_box;

pub use bounding::convex_hull_area;

pub use bounding::convex_hull_area_perimeter;

pub use bounding::convex_hull_perimeter;

pub use bounding::is_convex;

pub use bounding::minimum_bounding_rectangle;

pub use bounding::point_set_diameter;

pub use bounding::point_set_width;

pub use bounding::polygon_perimeter;

pub use bounding::signed_polygon_area;

pub use bounding::OrientedBoundingRect;

pub use bounding::AABB;

pub use sweep_line::count_intersections;

pub use sweep_line::find_all_intersections;

pub use sweep_line::find_all_intersections_brute_force;

pub use sweep_line::has_any_intersection;

pub use sweep_line::segment_intersection;

pub use sweep_line::Intersection;

pub use sweep_line::Segment2D;

pub use fortune_voronoi::fortune_voronoi_2d;

pub use fortune_voronoi::fortune_voronoi_from_array;

pub use fortune_voronoi::VoronoiCell;

pub use fortune_voronoi::VoronoiDiagram;

pub use fortune_voronoi::VoronoiEdge;

pub use fortune_voronoi::VoronoiVertex;

pub use incremental_hull_3d::HullFace;

pub use incremental_hull_3d::IncrementalHull3D;

Modules

bounding

Minimum bounding rectangle and computational geometry utilities

fortune_voronoi

Fortune’s sweep line algorithm for Voronoi diagram construction

incremental_hull_3d

Incremental 3D convex hull algorithm

sweep_line

Bentley-Ottmann sweep line algorithm for detecting line segment intersections