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 = "0.6"

# with serde support
u-geometry = { version = "0.6", features = ["serde"] }

use u_geometry::collision::polygons_intersect;
use u_geometry::polygon::{area, contains_point, convex_hull};
use u_geometry::primitives::{Point2, AABB2};

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

// Polygons are slices of (x, y) vertices
let rect = [(0.0, 0.0), (4.0, 0.0), (4.0, 3.0), (0.0, 3.0)];
assert!((area(&rect) - 12.0).abs() < 1e-10);
assert!(contains_point(&rect, (1.0, 1.0)));
assert_eq!(convex_hull(&rect).len(), 4);

// Exact overlap test for convex or concave polygons
let shifted = [(2.0, 1.0), (6.0, 1.0), (6.0, 4.0), (2.0, 4.0)];
assert!(polygons_intersect(&rect, &shifted));

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 |

A browser without a bundler is not supported: the package loads its .wasm file with an ES module import, which browsers refuse (application/wasm is not a module script type), so <script type="module"> from a CDN fails, and CDN re-bundling services fail on the same import. Use a bundler or Node.

TypeScript

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

export function convex_hull(points: Point2D[]): 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.

The same holds on the way in: a point given as [x, y] instead of { x, y } does not compile. The binding still validates every input at the boundary, for JavaScript callers and for values that reach it through a cast, 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 | | boundary_distance(polyA, polyB) | (Point[], Point[]) → number | Minimum distance between the two boundaries (clearance); 0 when they touch or cross | | 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) | | codes() | () → Codes | Every refusal code and the fields that can come with it: { refusals: [{ code, fields }], violations: [] }, built from the table the refusals come from (the table under Errors explains each) |

import {
  polygons_intersect, boundary_distance, polygon_bounds, transform_points,
} from '@iyulab/u-geometry';

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
boundary_distance(a, transform_points(a, 3, 0, 0)); // 1 — the gap between side-by-side squares
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 }

Errors. A refusal throws an Error whose message is readable text and which carries a code naming the reason and the parameter it is about:

import { polygon_bounds } from '@iyulab/u-geometry';

try {
  polygon_bounds([]);
} catch (err) {
  console.log(err.code, err.parameter); // empty_input points
}

| code | Fields | Meaning | |---|---|---| | malformed_input | parameter, index (inside an array) | An argument of the wrong shape or type, or a JSON string | | empty_input | parameter | polygon_bounds given no points | | value_not_finite | parameter, index | A NaN or ±Infinity anywhere in an argument — parameter is the path to it, index its position in that array, or null | | internal | — | A result the package could not hand back — a fault in the package, not in the input; please report it |

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