u-geometry

Domain-agnostic computational geometry library

Overview

u-geometry provides fundamental geometric primitives, transformations, polygon operations, collision detection, and spatial indexing. It contains no domain-specific concepts — nesting, packing, routing, etc. are defined by consumers.

Modules

| Module | Description | |--------|-------------| | primitives | Core types: Point2, Vector2, Segment2, AABB2, Point3, Vector3, AABB3 | | polygon | Polygon operations: area, centroid, convex hull, winding order, containment | | transform | Rigid transformations: Transform2D, Transform3D | | robust | Numerically robust geometric predicates (Shewchuk adaptive precision) | | collision | SAT-based collision detection (2D convex polygons), AABB overlap (2D and 3D) | | minkowski | Minkowski sum and No-Fit Polygon (NFP) for convex polygons | | spatial_index | Linear-scan spatial indices for 2D and 3D AABB queries | | nalgebra_types | Re-exports of commonly used nalgebra types for version consistency |

Features

• serde — Enable serde serialization for geometric types (includes nalgebra/serde-serialize)

Quick Start

[dependencies]
u-geometry = { git = "https://github.com/iyulab/u-geometry" }

# with serde support
u-geometry = { git = "https://github.com/iyulab/u-geometry", features = ["serde"] }

use u_geometry::primitives::{Point2, AABB2};
use u_geometry::polygon::Polygon2D;
use u_geometry::collision::sat_overlap;

// Points and AABBs
let p = Point2::new(1.0, 2.0);
let aabb = AABB2::new(Point2::new(0.0, 0.0), Point2::new(10.0, 10.0));
assert!(aabb.contains(&p));

// Polygon operations
let polygon = Polygon2D::new(vec![
    Point2::new(0.0, 0.0),
    Point2::new(4.0, 0.0),
    Point2::new(4.0, 3.0),
    Point2::new(0.0, 3.0),
]);
assert!((polygon.area() - 12.0).abs() < 1e-10);

Build & Test

cargo build
cargo test
cargo bench  # criterion benchmarks

Academic References

• de Berg, Cheong, van Kreveld, Overmars (2008), Computational Geometry
• Shewchuk (1997), Adaptive Precision Floating-Point Arithmetic
• O'Rourke (1998), Computational Geometry in C
• Ericson (2005), Real-Time Collision Detection

Dependencies

• nalgebra 0.33 — Linear algebra
• robust 1.1 — Robust geometric predicates
• serde 1.0 — Serialization (optional)

License

MIT License — see LICENSE.

Related

• u-numflow — Mathematical primitives
• u-metaheur — Metaheuristic optimization (GA, SA, ALNS, CP)
• u-schedule — Scheduling framework
• u-nesting — 2D/3D nesting and bin packing