u-geometry 0.1.0

Domain-agnostic computational geometry: primitives, polygons, NFP, collision detection, spatial indexing.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

# u-geometry

**Domain-agnostic computational geometry library**

[![Crates.io](https://img.shields.io/crates/v/u-geometry.svg)](https://crates.io/crates/u-geometry)
[![docs.rs](https://docs.rs/u-geometry/badge.svg)](https://docs.rs/u-geometry)
[![CI](https://github.com/iyulab/u-geometry/actions/workflows/ci.yml/badge.svg)](https://github.com/iyulab/u-geometry/actions/workflows/ci.yml)
[![License](https://img.shields.io/badge/license-MIT-blue.svg)](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

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

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

```rust
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

```bash
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](LICENSE).

## Related

- [u-numflow](https://github.com/iyulab/u-numflow) — Mathematical primitives
- [u-metaheur](https://github.com/iyulab/u-metaheur) — Metaheuristic optimization (GA, SA, ALNS, CP)
- [u-schedule](https://github.com/iyulab/u-schedule) — Scheduling framework
- [u-nesting](https://github.com/iyulab/U-Nesting) — 2D/3D nesting and bin packing