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.

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

TypeScript

Every exported function declares its return type, and the declarations are generated from the same structs the binding serialises, so they cannot drift from what it actually returns:

export function convex_hull(points: any): Point2D[];

An absent optional value is declared T | undefined, which is what the binding sends. Nothing needs an as cast -- and a wrong assumption about a result's shape is a compile error rather than something that fails at run time.

Inputs are still any: they are validated at the boundary, and a rejected one says what was wrong.

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 }

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

u-geometry 0.1.6