u-geometry 0.1.4

Domain-agnostic computational geometry: primitives, polygons, NFP, collision detection, spatial indexing.
Documentation

u-geometry

Domain-agnostic computational geometry library

Crates.io docs.rs CI License

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.

npm (WebAssembly)

npm install @iyulab/u-geometry

The package resolves per environment via a conditional exports map:

Environment Entry
Bundlers (webpack, Vite, …) ESM + WebAssembly ESM-integration (default condition)
Node.js — require(), ESM import, CJS TS runners (tsx, ts-node) CJS glue loading the wasm from the filesystem (node condition) — no loader hooks or flags

API

All functions take native JS objects/arrays (not JSON strings). A point is { "x": number, "y": number }; a polygon is an array of points.

Function Signature Returns
polygon_area(points) Point[] → number Unsigned area of a simple polygon
convex_hull(points) Point[] → Point[] Convex hull, CCW order
point_in_polygon(point, polygon) (Point, Point[]) → boolean Point inside or on boundary
polygons_intersect(polyA, polyB) (Point[], Point[]) → boolean Exact overlap for convex or concave polygons
polygon_bounds(points) Point[] → AABB Axis-aligned bounding box
transform_points(points, tx, ty, angle) (Point[], number, number, number) → Point[] Rigid transform (rotation in radians about origin, then translate) 
import init, {
  polygons_intersect, polygon_bounds, transform_points,
} from '@iyulab/u-geometry';
await init();

const a = [{x:0,y:0},{x:2,y:0},{x:2,y:2},{x:0,y:2}];
const b = [{x:1,y:1},{x:3,y:1},{x:3,y:3},{x:1,y:3}];

polygons_intersect(a, b);              // true  — interiors overlap
polygon_bounds(a);                     // { min:{x:0,y:0}, max:{x:2,y:2} }
transform_points(a, 10, 5, Math.PI/2); // a rotated 90° CCW, then translated by (10,5)

Semantics of polygons_intersect — exact for simple polygons, convex or concave. Polygons that merely abut (share an edge or vertex) are not overlapping, and a part nested inside another's concave notch is correctly reported as not overlapping — unlike a convex-hull (SAT) test. Ideal for nesting/packing placement self-checks. Holes are not considered.

JSON schema

Point ::= { "x": number, "y": number }
AABB  ::= { "min": Point, "max": Point }

Related