# 整数几何与输入契约 ## 范围与预检 `Point64` 始终保存完整 Int64。几何入口和重复点整理入口只接受 `[-1_000_000_000, 1_000_000_000]` 内的 x、y，含两个端点。校验直接比较上下界，在减法、乘法、绝对值、复制或输出数组分配之前完成；不会将数据转成 Double、截断或钳制。 所有新增公开计算与整理函数返回 `Result[..., ClipError]`，并接受可选的 `limits` 参数。`Limits` 默认允许 10,000 条路径、100,000 个原始顶点。负限制为 `InvalidInput`，零额度合法。集合先检查路径数，再按原始路径顺序检查总顶点额度，最后检查全部坐标；预检通过后才计算或分配输出。 - 空路径占一个路径额度；空集合占零条路径。 - 连续重复点、重复闭合点与共享数组的每次出现均消耗原始输入额度。 - 总量通过剩余额度的比较和减法核算，不用可能溢出的 Int 累加。 - 单路径函数占一个路径额度。三个点的谓词将三个实参视为一条逻辑路径，索引按实参顺序编号。 - `point_in_polygon` 的轮廓占一个路径额度，查询点额外消耗一个顶点额度。查询点不属于轮廓，其错误位置的路径和顶点索引为 None；即使轮廓为空也校验查询点。 - 资源错误报告第一条超出路径或第一个超出顶点的原始索引（从零开始），并附资源类别及限制值。所有错误附处理阶段。坐标错误附轴和未经修改的 Int64 原值。 - 整数几何入口的范围证明和精确面积回退不预期产生 `NumericFailure`；内部扫描投影的非有限值、越界转换和槽位代次耗尽使用此分类。内部节点与扫描工作量预算已接入，交点和圆弧预算随后续实现增加。 错误信息为英文；调用方可模式匹配结构化载荷。函数不退出进程、不以空数组隐藏错误，也不返回部分成功结果。一次调用没有留存预算或可变缓存。 ## 叉积安全推导 设 M = 10^9，三个点的每一坐标均在 [-M, M]。 1. 坐标差在 [-2M, 2M]，可安全使用 Int64 减法。 2. 每个差值乘积绝对值不超过 4M² = 4 × 10^18。 3. `(b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x)` 的保守绝对值界为 8 × 10^18，小于 Int64 最大值 9,223,372,036,854,775,807。 内部 `cross_validated` 只用于已经预检的坐标；后续扫描线可复用它，避免重复校验。扩大公开坐标上限必须重新审计算术和所有调用点。边界测试覆盖极端角点组合、4 × 10^18 的实际行列式，以及大乘积相消后精确等于 1 的近共线输入。 数学坐标系 x 向右、y 向上。正叉积表示 CounterClockwise，负值表示 Clockwise，零表示 Collinear；重复点也可产生合法的零结果。没有 epsilon 或浮点符号判断。屏幕显示的 y 轴翻转应由绘图层处理。 ## 精确面积 `area2` 返回标准库 `BigInt`，值为隐式闭合轮廓的两倍有向面积。单项鞋带公式 `x[i]*y[i+1]-y[i]*x[i+1]` 绝对值不超过 2 × 10^18，单项可用 Int64；总和不能假定如此。 内部累加器先使用 Int64：正项检查 `sum > MAX-term`，负项检查 `sum < MIN-term`。这些阈值运算安全，且在相加之前执行。一旦需要回退，先将仍未溢出的旧总和与当前项分别精确转成 BigInt 再相加，后续保持 BigInt，即使总和重新回到小范围。没有浮点累加或浮点返回值。 测试使用边长 2 × 10^9 的正方形三次绕行，独立整数预期为 `3 × 8 × 10^18`，并验证反向负值。三次正向加三次反向的案例中间超过 Int64，最终精确抵消为零。白盒测试验证回退分支、正负溢出阈值，以及 Int64 快路径和从头使用 BigInt 的一致性。 空路径、单点、两点面积为零；重复首点或连续重复点不改变面积。面积为零不能用于删除自交轮廓或判定没有填充区域。 ## 边界与 EvenOdd 包含 `bounds` 对空路径返回 `Ok(None)`，其他情况返回真实坐标范围，零宽或零高合法，不表示面域有效性。 `point_on_segment` 使用精确共线判断和两轴闭区间；零长度线段只包含其端点。 `point_in_polygon` 处理单条隐式闭合轮廓，返回 Outside / Inside / OnBoundary。每条边先检查边界，再以 `(a.y > q.y) != (b.y > q.y)` 选出跨越查询高度的边，形成一致的半开区间。叉积的符号结合边的上行或下行方向判断交点是否在查询点右侧，不作除法。水平边只参与边界判断，共享顶点不会重复计数。 它支持凹轮廓与按 EvenOdd 解释的自交轮廓。空路径为 Outside；单点和两点只可能产生 Outside 或 OnBoundary。重复绕行两次的区域按 EvenOdd 为 Outside。这里没有 NonZero、多轮廓布尔运算或孔洞树。 ## 无损重复点整理 `normalize_path` / `normalize_paths` 必须显式传 Open 或 Closed。先删除连续重复点；Closed 再删除末尾重复的首点，Open 保留返回首点的有意义端点。 保留非连续重复点、普通共线点、原始顺序、退化轮廓、空轮廓和零面积蝴蝶形。输出少于三个顶点时直接返回真实结果，后续算法再按自己的契约处理。整理不是简化、拓扑修复或面域有效性校验。 每次调用为每条路径创建独立数组；输入中的别名不会传播到输出。失败不会修改输入；成功后的源和结果也能独立修改。 ## 精确整数依赖 使用固定工具链自带的 `moonbitlang/core/bigint`，无新增 Mooncakes 或外部几何依赖。其源码来自官方 `core-0.10.13+cbb11c36f.tar.gz`，SHA256 为 `d36b64c42df3019d9da87291e40738e90623c0380d0e200a62156091fb00c176`，来源地址及构建步骤已固定在 CI。core 源码版权为 International Digital Economy Academy，Apache-2.0，未复制其代码到 MoonClip。 已核对该版本 core 的目标配置：native 使用 MoonBit 的宽整数 BigInt 实现，JS 使用标准库的精确 JS BigInt 后端；两者都没有将几何整数转成普通 JS Number 或 Double。JS 后端采用目标平台精确整数能力，并非将 native 的数据转成浮点模拟。回归测试在两目标使用相同输入、Int64/BigInt 字面量及独立精确预期。 ## Commit 4 内部扫描投影 扫描高度从较大 y 到较小 y，内部 bot.y >= top.y；这不改变公开数学坐标系及有向面积符号。活动边的转向、共线和方向比较仍使用统一的精确整数行列式。向量分量是已验证坐标之差，绝对值最多 2×10^9，仍满足乘积 4×10^18、差 8×10^18 的安全推导。 非水平投影对齐固定 C++ TopX / C# TopX： ```text 端点或垂直边：直接返回原始整数 x 其他非水平边： dx = Double(top.x - bot.x) / Double(top.y - bot.y) displacement = round_ties_to_even(dx * Double(y - bot.y)) x = bot.x + displacement ``` 这里的 Double 只用于上游约定的网格投影，不用于几何符号判断。水平边独立记录 ToLeft/ToRight，不除以零。y 必须在当前非水平边段的端点区间内。 舍入用 floor、半整数比较及下方整数奇偶明确实现，两目标不依赖各自默认 round。+0.5→0、+1.5→2、+2.5→2；-0.5→0、-1.5→-2、-2.5→-2。先舍入位移再相加：bot.x=1、位移=0.5 时结果为 1，而不是把最终 1.5 舍入为 2。测试预期直接写出，含半整数两侧、非零起点、正负斜率、垂直边、端点和坐标边界。 斜率及位移检查 NaN/Infinity。接受的位移在转换前被限制到安全的小整数范围，舍入后绝对值不得超过 2×10^9；此范围内的 floor 整数可被 Double 精确表示，随后才转换 Int64。加法执行 Int64 溢出阈值检查，最终 x 必须仍位于几何坐标范围。内部异常归类 NumericFailure，经过扫描入口转为 Result 并终止当前状态。 投影含有网格舍入，不能代替精确相交判定，也不构成未来全部交点计算的误差保证。带顶投影倒置或存在不能排除的并列时，当前组件保留 AwaitIntersections，不通过排序把问题隐藏。Commit 5 的交点与输出规则见下文；投影并列仍需显式接触决策。 ## Commit 5 固定参考交点路线 Commit 3 的 CMake 构建没有定义 `CLIPPER2_HI_PRECISION`；固定源码的 `#if CLIPPER2_HI_PRECISION` 因而选择普通分支。已核对实际 Ninja 命令原为 `-O3 -DNDEBUG -std=c++17`，没有高精度定义。Commit 5 将 `CLIPPER2_HI_PRECISION=0` 显式加入 reference 库的 PUBLIC 编译定义，并写入 environment.json 的 compile_definitions，适配器继承同一定义。该变更固定已有分支，不修改预期数据；仍须实际重建、运行 10 项适配器测试和 136 例重建比较。 普通 `GetLineIntersectPt` 按固定 C++ 顺序计算： ```text dx1 = Double(b.x-a.x); dy1 = Double(b.y-a.y) dx2 = Double(d.x-c.x); dy2 = Double(d.y-c.y) det = dy1*dx2 - dy2*dx1 若 det == 0：无普通交点（平行/共线或该浮点公式退化） t = (Double(a.x-c.x)*dy2 - Double(a.y-c.y)*dx2) / det 若 t <= 0：返回 a；若 t >= 1：返回 b 否则：分别向零截断 Double(a.x)+t*dx1、Double(a.y)+t*dy1 ``` 几何关系使用精确整数，普通坐标公式仍保留固定参考的 Double 运算次序；不添加 epsilon，也不以 TopX 舍入替换截断。每个浮点参数检查有限性，最终坐标在转整数前检查 ±10^9 范围。平行分支的事件坐标采用 `(first.current_x, top_y)`，并不把平行返回转换成合法空输出。端点不会重新经过浮点构造。 `AddNewIntersectNode` 的带外修正按固定分支处理。若 raw.y 位于带底之下或带顶之上：两边 |dx| 均大于 100 时选择 |dx| 更大的边；仅一边大于 100 时选择该边。投影到被选线段的最近点，q 限制到 [0,1]，两个相对位移分别 ties-to-even，再加起点。最近点可能仍不在当前扫描带内，不能再次统一钳制。其余情况才把 y 限制到带顶/带底，并在 |dx| 较小的边上使用 TopX（相等时选择第二条边）。100 是固定源码的分支常量，不是新增容差。 水平端点的后续边段比较允许对另一条非水平边作 TopX 外推。只比较位置关系，不把可能很大的外推值转成坐标。位移绝对值大于 2×10^9+0.5 时，可直接确定相对合法坐标的左右关系；其余情况复用统一 ties-to-even 舍入。阈值来自两个合法坐标的最大差及偶数边界的半整数规则，不是接近零阈值。 ### 中间值审计 所有坐标先验证，Int64 差、和最多分别 2×10^9，新增叉积/点积的乘积最多 4×10^18，两个项的和/差最多 8×10^18。严格线段相交仅比较叉积符号，不把两个叉积相乘。普通交点的 Double 行列式、分子、最近点的点积/平方和绝对值最多约 8×10^18，远小于 Double 上限；仍显式检查参数与结果。外推位移最坏约 4×10^18，仅用于浮点位置比较，禁止直接转 Int64 坐标。 输出环面积使用 Commit 2 的检查累加及 BigInt 回退。局部修复设原环两倍有向面积 S、分离三角形叉积 T：固定源码 `Area` 是 S/2，`AreaTriangle` 返回 T。`abs(Area)<2` 写成 `abs(S)<4`；保留三角形条件写成 `abs(T)>=1 && (2*abs(T)>abs(S) || sign(T)==sign(S))`，乘 2 在 BigInt 中完成，避免 Int64 溢出。这里刻意使用精确阈值比较，区别于上游环面积的浮点累加；不因此承诺任意自交输入的布尔兼容性。微交叉沿用固定源码的第五坐标插点分支，不猜测一般修复规则。 native 和 JS 共用上述代码、正负小数/半整数、近水平修正、边界坐标、同点多事件以及环修复的固定预期；没有目标专用近似容差。 ## Commit 6 公开布尔入口 输入坐标、TopX、普通交点截断与带外修正规则保持不变；共享边连接只使用精确叉积、闭区间和方向点积。点积每项最多 4×10^18，两项之和最多 8×10^18，仍在 Int64 安全范围。仅正长度重叠连接，端点接触不触发拼接。所有查找与新增节点受同一调用预算约束。 ExecutionFailure 区分内部扫描/输出契约失败与 InvalidInput 参数错误；坐标、数值、资源错误保留各自分类。原生命令序列化坐标时先转成 Int（合法几何值均在 ±10^9，适合 Int），再输出 JSON 整数；这是避开标准库 Int64::to_json 的字符串编码，不改变运行库 Int64 算术。native/JS 的固定测试均直接使用 Int64 字面量与完整坐标预期。 ## Commit 9 闭合偏移数值路线 先以原始整数坐标执行共同 Union，确保外正孔负，再生成法线和偏移连接。固定 C++ `CrossProduct(vec1,vec2)` 为 `vec1.y*vec2.x-vec2.y*vec1.x`；OffsetPoint 使用当前法线、前一法线这一顺序。它与三点精确叉积的写法不同，不改变核心数学方向定义。 单位法线沿边差 `(dx,dy)` 计算 `inverse=1/sqrt(dx*dx+dy*dy)`，结果 `(dy*inverse,-dx*inverse)`。边差先用已验证 Int64 相减，再转 Double；重复点返回零法线。归一化后的填充轮廓不含零长度边。生成过程检查有限性。源码的 cosine > -0.999 凹角分类、cosine > 0.999 近直线分支和 Square 平分向量长度 0.001 阈值为固定算法分支，不是整数谓词 epsilon 或最终比较容差。 Miter 使用 `q=delta/(cosine+1)`，尖角为顶点加 `(previousNormal+currentNormal)*q`；当 `cosine > 2/(miter_limit*miter_limit)-1` 才使用 Miter，恰好相等也进入 Square。Square 沿法线平分方向推进 abs(delta)，构造横向截线，与前一偏移边求固定次序的浮点交点，再反射生成另一端；不以 Bevel 替代。近直线对两公开 Join 均使用 Miter；凹角保存前偏移点、原点、后偏移点供清理。负距离仍走相同分类及 Positive 清理。 偏移坐标转换独立实现 std::round：负值 ceil(value-0.5)，非负值 floor(value+0.5)，因此 ±0.5→±1，±1.5→±2。不调用 JS Math.round 或扫描 ties-to-even。先拒绝非有限值及不能安全转换的 Double（保守检查 ±9e18），转换后再检查 ±1e9 网格边界；不截断、不钳制。比如 9.5→10，故 [0,10] 收缩 -0.5 的网格范围 [1,10]，而 -0.500000001 得 [1,9]。原始坐标合法不保证生成点合法；所有中间生成点均先检查，不能等待 Union 删除越界点。巨大的有限参数导致非有限运算时返回 NumericFailure；Bevel 不计算无关的 Miter 平方。 CallBudget 持有跨 ScanState 共用的 ScanStats 与固定 ScanLimits。规范化、生成（外层/路径/法线/生成顶点）、清理、快照的节点和工作量累计递增，阶段清理只释放状态，不退款。清理预检从剩余工作量扣除。原始输入路径/顶点只预检一次；内部清理绕过原始输入数量限制，仍验证坐标、数组结构及累计工作量。规范化/生成不能唯一追溯原始输入，内部 SourceId 带来源标记，错误位置不伪造原始索引。公开 Limits 两字段未改变；公开布尔/树独立调用仍各自拥有预算。 abs(delta)<0.5 返回已经规范化且独立拥有数组的结果；参数、坐标、原始预算均不能绕过。35 项功能测试含精确累计额度/少一个单位、生成及清理分别耗尽、失败重试、四原始顶点生成八个 Bevel 顶点，以及 native/JS 同预期半整数和边界拒绝。没有新增运行库依赖。 ## Commit 10 Square、Round 与 ArcTolerance 公开 Square 直接复用 offset_square；Miter 超限仍调用同一函数。凹角分类在样式分派之前，近共线 cosine>0.999 的 Miter 快速路径只供非 Round 样式，Round 不跳过圆弧。所有新点继续通过 offset_push / offset_coordinate，半整数远离零，生成坐标必须在清理前合法。 规范化非空且 abs(delta)>=0.5 后才计算 Round 参数。令 r=abs(delta)：容差大于 1e-12 时 effective=min(r,tolerance)，否则 effective=r*0.002；steps360=min(π/acos(1-effective/r),r*π)，step=2π/steps360，steps_per_rad=steps360/(2π)。当 1-effective/r 因 Double 舍入成为 1 时，显式采用 r*π，等价固定源码 min(+Infinity,cap)，不制造无检查的 Infinity 或转整数。其余中间值都检查有限性。r*π 是算法采样上限，不是节点预算或误差保证。 step_sin=sin(step)、step_cos=cos(step)，负 delta 将 step_sin 取反。每角 angle=atan2(sine,cosine)，steps=ceil(steps_per_rad*abs(angle))。先发出前法线偏移点，中间 i=1..steps-1 用旧向量同时旋转两个分量，最后直接发出当前法线偏移点。保持全局固定旋转步长，不将当前角平均分段；终点不依赖累计旋转。这也是整数网格上圆角样本不必对称的原因。 offset_arc_steps 在 Double→Int 之前检查有限性、非负性、剩余节点/工作量及 Int 范围。实际输出点数为 steps<=1 时 2，否则 steps+1。整个角的采样预检在任何点分配和循环之前完成，只检查而不扣费；offset_push 实际逐点扣费，包括舍入后相同的样本。每角、路径、清理均共享 Commit 9 CallBudget，失败无部分结果，下一次调用重新开始。 解析测试预先固定 r=100、tolerance=0.25、sagitta 绝对数值误差 1e-11、40 次旋转半径误差 1e-10；该例 steps360