#Moon Geometry

纯 MoonBit 计算几何库 | 2026 MoonBit 十月赛参赛项目 Pure MoonBit computational geometry library | 2026 MoonBit October Hackathon entry

#特性 | Features

• 基础几何类型 | Basic types: Point2D / Point3D / Segment / Line / Polygon / Triangle / Circle / Rectangle
• 凸包 | Convex hull: Graham scan, Andrew's monotone chain (O(n log n)) | Graham 扫描法、Andrew 单调链法
• 多边形操作 | Polygon ops: area (Shoelace), perimeter, centroid, point-in-polygon, convexity, orientation, Douglas-Peucker | 面积、周长、质心、点在多边形内、凸性判断、方向判定、Douglas-Peucker 简化
• Delaunay 三角剖分 | Delaunay triangulation: Bowyer-Watson incremental insertion (O(n²) expected) | Bowyer-Watson 增量插入法
• Voronoi 图 | Voronoi diagram: Delaunay duality, circumcenters as vertices | Delaunay 对偶，外心为顶点
• 几何变换 | Transforms: translate, rotate, scale, affine, mirror, shear | 平移、旋转、缩放、仿射、镜像、剪切
• 距离计算 | Distance: point-to-segment/polygon, segment-to-segment, polygon-to-polygon | 点到线段/多边形、线段间、多边形间
• 包围体 | Bounding: AABB, min-area bounding rect (rotating calipers), bounding circle | 轴对齐包围盒、最小面积包围矩形、包围圆
• 圆相交 | Circle intersection: circle-segment, circle-circle, circle-line, circle-polygon | 圆与线段/圆/直线/多边形相交
• 多边形三角剖分 | Polygon triangulation: ear clipping for simple polygons | ear clipping 简单多边形三角剖分
• Minkowski 运算 | Minkowski ops: sum/difference of convex polygons, collision detection | 凸多边形 Minkowski 和/差、碰撞检测
• 旋转卡壳 | Rotating calipers: convex polygon diameter, width, farthest pair, min-perimeter rect | 凸多边形直径、宽度、最远点对、最小周长矩形
• 椭圆几何 | Ellipse: area, perimeter, eccentricity, foci, contains, line intersection | 面积、周长、离心率、焦点、包含、直线相交
• 贝塞尔曲线 | Bezier: quadratic/cubic eval, derivative, length, bbox, subdivide | 二次/三次求值、导数、弧长、包围盒、细分
• 几何拟合 | Fitting: least-squares line/circle fit, orthogonal regression, centroid | 最小二乘直线/圆拟合、正交回归、质心
• 扫描线 | Sweep line: segment intersection detection, simple polygon test | 线段相交检测、简单多边形检测
• 凸多边形操作 | Convex polygon: O(log n) point query, tangent, SAT intersect, support function | O(log n) 点查询、切线、SAT 相交、支持函数
• 统一导入 | Unified import: import "walkzzz/moon-geometry" re-exports all APIs | 单包导入重导出全部 API
• 纯 MoonBit 零依赖 | Pure MoonBit, zero deps: no C FFI, single codebase for all targets | 无 C FFI，四目标共用代码库
• 退化情况全覆盖 | Full degenerate coverage: collinear, coincident, empty, single/two-point | 共线点、重合点、空输入、单点/两点退化
• 统一公差体系 | Tolerance system: configurable ToleranceCtx for distance/angle/area, default/strict/loose presets | 可配置 ToleranceCtx 公差上下文，预设 default/strict/loose
• 退化构型鲁棒性 | Degenerate robustness: detect collinear/overlap/zero-area/self-intersect/small-angle, remove coincident points | 检测共线/重叠/零面积/自交/极小角度，移除重合点
• 拓扑一致性验证 | Topology validation: closed manifold check, non-manifold edges, dangling edges, isolated vertices, normal consistency | 闭合流形检测、非流形边、悬挂边、孤立顶点、法向一致性
• 增量计算 | Incremental computation: incremental Delaunay with dynamic insert/remove, supports interactive editing | 增量 Delaunay 动态插入/删除，支持交互式编辑

#安装 | Installation

moon add walkzzz/moon-geometry

#项目结构 | Project Structure

base/          # (32) Core types & robust arithmetic | 基础类型与鲁棒算术
geometry/      # (65) Convex hull, polygon, triangulation, computational geometry | 凸包、多边形、三角剖分、计算几何
transform/     # (19) Geometric transforms & differential geometry | 几何变换与微分几何
spatial/       # (30) Spatial data structures & distance metrics | 空间数据结构与距离度量
curves/        # (27) Curves, splines & algebraic geometry | 曲线、样条与代数几何
mesh/          # (27) Mesh processing & topological data analysis | 网格处理与拓扑数据分析
numerics/      # (24) Numerical optimization & PDE solvers | 数值优化与偏微分方程求解
applied/       # (29) Robotics, ML, point cloud & statistics | 机器人、机器学习、点云与统计
io/            # (18) File I/O & graphics rendering | 文件输入输出与图形渲染
testing/       # (12) Testing infrastructure & utilities | 测试基础设施与工具

#快速示例 | Quick Example

// 1. 凸包计算 | Convex hull
let points = [
  @moon_geometry.Point2D::new(0.0, 0.0),
  @moon_geometry.Point2D::new(4.0, 0.0),
  @moon_geometry.Point2D::new(4.0, 4.0),
  @moon_geometry.Point2D::new(0.0, 4.0),
  @moon_geometry.Point2D::new(2.0, 2.0),  // 内部点 | interior point
]
let hull = @moon_geometry.convex_hull_andrew(points)  // 凸包顶点（逆时针）

// 2. 多边形面积 | Polygon area
let polygon = [
  @moon_geometry.Point2D::new(0.0, 0.0),
  @moon_geometry.Point2D::new(4.0, 0.0),
  @moon_geometry.Point2D::new(4.0, 4.0),
  @moon_geometry.Point2D::new(0.0, 4.0),
]
let area = @moon_geometry.polygon_area(polygon)  // 16.0

// 3. Delaunay 三角剖分 | Delaunay triangulation
let tri = @moon_geometry.delaunay_triangulation(points)

// 4. 几何变换 | Transform
let affine = @moon_geometry.Affine2::new(
  1.0, 0.0, 0.0,  // a, b, c
  0.0, 1.0, 0.0,  // d, e, f
)
let transformed = affine.apply(@moon_geometry.Point2D::new(1.0, 1.0))

// 5. 距离计算 | Distance
let dist = @moon_geometry.Point2D::new(0.0, 0.0).dist(
  @moon_geometry.Point2D::new(3.0, 4.0)
)  // 5.0

// 6. 点在多边形内 | Point in polygon
let inside = @moon_geometry.point_in_polygon(
  @moon_geometry.Point2D::new(2.0, 2.0),
  polygon
)  // true

// 7. Trait 多态 | Trait polymorphism (Measurable)
let circle = @moon_geometry.Circle::new(
  @moon_geometry.Point2D::new(0.0, 0.0),
  5.0
)
let circle_area = circle.area()  // 78.54...

// 8. 形式化验证 | Proof-carrying code
// dist 函数带有非负性契约: proof_ensure: result => result >= 0.0

#API 概览 | API Overview

#测试 | Tests

moon test                          # 全部 2307 测试 | all 2307 tests
moon test --target native          # 四目标分别验证 | verify each backend
moon test --target wasm-gc
moon test --target js
moon test --target wasm

#使用场景 | Use Cases

#Trait 系统 | Trait System

#形式化验证 | Formal Verification

#交付路线图 | Roadmap

#设计参考 | Design References

• CGAL — 算法参考 | algorithm reference
• Shapely — API 设计参考 | API design reference
• scipy.spatial — Delaunay/Voronoi 对照验证 | validation

#许可证 | License