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

Features

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

Quick Start

[dependencies]
u-geometry = "0.2"

# with serde support
u-geometry = { version = "0.2", 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:

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.

import {
  polygons_intersect, 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
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
}

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