Module halfspace 

Halfspace intersection and convex polytope construction

This module provides algorithms for computing the intersection of halfspaces to construct convex polytopes. Halfspace intersection is the dual problem to convex hull computation and is fundamental in computational geometry.

Theory

A halfspace in d-dimensional space is defined by a linear inequality: a₁x₁ + a₂x₂ + … + aₐxₐ ≤ b

The intersection of multiple halfspaces forms a convex polytope. This module implements algorithms to:

• Compute the vertices of the polytope
• Extract faces and facets
• Handle degenerate cases
• Check feasibility

Examples

// Define halfspaces for a unit square: x ≥ 0, y ≥ 0, x ≤ 1, y ≤ 1
let halfspaces = vec![
    Halfspace::new(array![-1.0, 0.0], 0.0),   // -x ≤ 0  =>  x ≥ 0
    Halfspace::new(array![0.0, -1.0], 0.0),   // -y ≤ 0  =>  y ≥ 0
    Halfspace::new(array![1.0, 0.0], 1.0),    //  x ≤ 1
    Halfspace::new(array![0.0, 1.0], 1.0),    //  y ≤ 1
];

let intersection = HalfspaceIntersection::new(&halfspaces, None)?;

// Get the vertices of the resulting polytope
let vertices = intersection.vertices();
println!("Polytope vertices: {:?}", vertices);

// Check if the polytope is bounded
println!("Is bounded: {}", intersection.is_bounded());

Structs

Halfspace

Representation of a halfspace: a·x ≤ b

HalfspaceIntersection

Result of halfspace intersection computation