# MoonGeo 0.1.0 算法与契约

## 坐标与封装

Point、Segment、BBox、Polygon、MultiPolygon、RTree 和 RegionIndex 以抽象类型导出。Point 构造拒绝非有限数及绝对值超过 1e100 的坐标；BBox 构造拒绝反向端点。平面坐标无坐标系元数据，调用者负责统一投影与单位。Polygon 复制所有输入环，访问器再次复制，防止外部修改几何导致缓存包围盒失效。

## 方向符号

`orientation(a,b,c)` 以 y 轴向上定义 CCW/CW/Collinear。快速计算以 c 为基点的叉积，使用 `1e-14 * (abs(left)+abs(right))` 保守误差界；所有非零坐标差的绝对值至少为 1e-100 才使用快速结果。构造器的上界保证乘积不溢出，下界筛选避免乘积或误差界下溢。此条件比普通 orient2d 一阶误差界保守，筛选不确定时不会把小数值当成共线。

回退把每个输入解码为有符号整数有效位与二进制指数：正规数为 `significand * 2^(exponent_bits-1075)`，次正规数为 `fraction * 2^-1074`。所有非零输入对齐到最小指数，之后用 BigInt 精确相减和相乘。这个路径不依赖已经舍入的差值。符号为输入 Double 所代表的数的精确符号；不是对真实测量坐标的纠错，也不保证其他测量结果精确。

## 线段、环与区域

线段关系分类为 Disjoint、Touch(point)、Cross、Overlap(segment)。重叠端点按 x、y 字典序规范化；零长度线段按点处理。Cross 不构造近似交点，避免把可靠相交结论误称为精确交点坐标。

环接受一个重复的闭合终点，规范化后移除。至少需要三个顶点，拒绝零长度边、全共线、非相邻边相交、重复顶点和相邻边重叠。验证使用 O(n²) 边对检查；这里优先契约完整性，不宣称适合巨大环的高速导入。

Polygon = 外环 + 孔洞。孔洞须严格位于外环内，不能触边、相交、重叠或嵌套。环方向不决定外环／孔洞角色。点定位使用半开 Y 区间，防止射线经过顶点时重复计数；边界首先由可靠方向符号和闭区间判断。EvenOdd 和 NonZero 都可选，简单环下结果一致。边界报告中的 ring=0 指外环，ring=1..n 指孔洞，edge 从 0 起，对应规范化环。

MultiPolygon 的有填充区域不可相交或触碰；一个分量可位于另一分量的孔洞中，因为实际区域仍分离。空 MultiPolygon 可表示空集合，但不能插入索引。

`signed_area` 接受任意点列并返回扇形展开的 shoelace 代数面积，使用局部原点和补偿求和；不同面积的自交双叶不保证面积为零。Polygon 面积为外环面积绝对值减孔洞面积绝对值；质心按面积加权，以外环质心为组合基点减少抵消。测量仍为 Double 近似：下溢可给出零面积，质心缺失则返回 None。原来“零面积时顶点平均”的隐式替代未采用。

距离使用缩放 hypot 和归一化投影，线段相交时距离为零。距离与质心不是精确构造算法；极端尺度差距下不作相对误差保证。

## 动态 R-tree

节点最大容量在 4..128 之间，最小容量为 floor(capacity/2)。叶存放唯一整数 ID 和 BBox，分支存放子节点。选择插入子树时以面积增量最小优先，再以面积打破平局。

溢出使用 Guttman quadratic split：最大空余面积种子、最大增量偏好差选择剩余条目，并强制满足最小占用。分裂会向上递归，必要时建立新根。删除通过 ID 目录获取包围盒，定位实际叶条目；下溢子树移除后收集其叶条目，在剩余树中重新插入，最后允许根下降。这里采用叶条目重插的明确变体，不声称与原论文按层重插的具体树形完全一致。

范围查询为闭包围盒相交，包括触边、零面积条目。返回顺序固定按 ID。重复 ID 报错，不静默覆盖；remove 不存在的 ID 返回 false。节点计数、实际分裂次数、重整次数和查询访问量来自真实遍历。`validate()` 检查最小／最大占用、节点包围盒、叶深一致、重复 ID 与目录一致性。

树高与数据分布有关；重叠严重时查询可退化到 O(n)。二次分裂每次 O(M²)，ID 目录不代替空间遍历。验证器为 O(n)，作为诊断入口而非每次查询的默认开销。没有性能基准或超越同类实现的声明。

## 区域查询

RegionIndex 用 MultiPolygon 总包围盒做候选查询，然后对每个候选的分量进行真实 Polygon 点定位。孔洞、凹形和分量间空隙造成的包围盒误命中保留为 Outside 决策。一个报告包含 revision、候选数、树节点访问数、叶条目检测数、hits 与所有候选的 decisions。

默认命中包括边界；`include_boundary=false` 排除边界 ID，但保留 OnBoundary 和边界段信息。report 的 component 从 0 开始；Outside 的 component 和 boundary 为 None。boundary 是可检查的几何诊断，不是形式化证明。替换先检查新区域有效性，成功新增、替换、删除才增加 revision。结果数组独立于内部目录，修改结果不会改变索引。

首版为单线程内存库，不含序列化、事务并发、全球地理坐标处理、kNN、KD-tree、geohash 或高级拓扑运算。