曲线曲线2D解析求交方案

曲线曲线2D解析求交方案文章目录曲线曲线2D解析求交方案一. 2D 点到椭圆的最近点计算1. 推荐主方案λ 方程 Halley bracket 保护2. bracket 区间3. Halley bracket 保护4. Newton bracket 对比实现5. 轴线和中心特殊情况6. 椭圆弧最近点7. 方向角初值方案的定位二. 2D 圆与椭圆求交本文亮点/核心思想所在1. 距离极值点2. 交点数量判断2.1 圆心在椭圆内部的典型情况2.2 圆心在椭圆外部的简单情况3. 求交区间划分4. 推荐初值平方距离线性插值5. Halley bracket 保护求交6. Newton bracket 对比实现7. 椭圆弧与圆弧情况8. 结果去重与交点类型三. 实现要点本文档记录 2D 圆、椭圆相关解析求交中需要复用的两个核心算法点到椭圆最近点计算以及圆与椭圆求交。一. 2D 点到椭圆的最近点计算核心思想1.点到椭圆的距离是一个四次的函数表达式最多有四个解2.点到椭圆最多有四个极值距离点我如何将四个极值点稳定快速的计算出来3.我快速估计/获取到四个比较近的参数然后通过迭代割线法思想稳定高效地获取到全部极值点位置4.我拒绝了使用解一元四次方程的方法或者其他解析类似的方法避免由于条件数不好带来的失败问题必须保证稳定。适用对象LGKEllipse2d包括整椭圆和椭圆弧。椭圆参数表达为E(t) O a cos(t) U b sin(t) V其中O为椭圆局部坐标系原点。U为椭圆局部 x 轴方向。V为椭圆局部 y 轴方向。a为 x 方向半轴长度。b为 y 方向半轴长度。给定 2D 点P先将其转换到椭圆局部坐标系p (x, y)最近点问题等价于求距离函数的局部极小点F(t) |E(t) - P|^2一阶导为F(t) 2 (E(t) - P) · E(t)其中E(t) -a sin(t) U b cos(t) V1. 推荐主方案λ 方程 Halley bracket 保护整椭圆最近点推荐使用法线条件导出的 λ 方程而不是直接在周期参数t上做无保护 Newton。先利用椭圆关于局部坐标轴的对称性将点转到第一象限X abs(x) Y abs(y)求得第一象限最近点Q (qx, qy)后再按原始x/y符号恢复到对应象限。最近点满足qx a^2 X / (λ a^2) qy b^2 Y / (λ b^2)且Q位于椭圆上(qx / a)^2 (qy / b)^2 1代入得到一维方程G(λ) (a X / (λ a^2))^2 (b Y / (λ b^2))^2 - 1 0导数为G(λ) -2 a^2 X^2 / (λ a^2)^3 - 2 b^2 Y^2 / (λ b^2)^3二阶导为G(λ) 6 a^2 X^2 / (λ a^2)^4 6 b^2 Y^2 / (λ b^2)^4Halley 迭代步为λNew λ - 2 G G / (2 (G)^2 - G G)2. bracket 区间bracket是始终包含根的夹逼区间[low, high]。对于椭圆外点(X/a)^2 (Y/b)^2 1 λ ∈ [0, ∞) G(0) 0 G(∞) -1实现时从low 0开始逐步扩大high直到G(high) 0对于普通内点λ 通常为负根位于-b^2 λ 0可取low -b^2 eps high 0并保持G(low) 0 G(high) 0如果坐标轴或中心附近出现特殊情况应走专门分支避免分母接近零导致不稳定。3. Halley bracket 保护主迭代使用 Halley并用 bracket 保护for iteration: λHalley λ - 2 G G / (2 (G)^2 - G G) if λHalley 不在 [low, high] 内或分母过小: λHalley 0.5 * (low high) if G(λHalley) 0: low λHalley else: high λHalley λ λHalley这样通常 2 到 4 次可收敛极端情况下退化为二分但根不会丢失。4. Newton bracket 对比实现为了验证 Halley 的效果可以同时实现 Newton bracket 版本用于对比λNewton λ - G / G保护逻辑与 Halley 相同if λNewton 不在 [low, high] 内或 G 过小: λNewton 0.5 * (low high)推荐对比项迭代次数。最终距离误差。轴线附近点的稳定性。椭圆很扁时的稳定性。内点、外点、远点、中心附近点表现。预期结果Halley 迭代次数更少Newton bracket 实现更简单二者都应比纯参数 Newton 稳定。5. 轴线和中心特殊情况若点接近椭圆中心X ≈ 0 Y ≈ 0最近点位于短轴端点若a b候选为(0, b) (0, -b)若点在 x 轴上且位于椭圆内部Y ≈ 0 (X/a)^2 1可根据法线条件得到qx a^2 X / (a^2 - b^2)如果0 qx a则有两个对称最近点(qx, b * sqrt(1 - qx^2 / a^2)) (qx, -b * sqrt(1 - qx^2 / a^2))否则最近点退化为长轴端点(a, 0)6. 椭圆弧最近点椭圆弧最近点不应只依赖整椭圆最近点因为全局最近点可能被参数域截断。处理流程用 λ 方程求整椭圆最近点候选。将候选点转换为椭圆参数保留落在椭圆弧参数域内的候选。将椭圆弧起点、终点加入候选。如果存在轴线对称的多个最近点候选应分别检查参数域。比较候选点到P的距离取最小值。7. 方向角初值方案的定位方向角转参数仍可作为直观解释或备用初值t0 atan2(a * y, b * x)该初值适合参数 Newton 的初始估计但不推荐作为主方案。主方案应使用 λ 方程 Halley bracket 保护。二. 2D 圆与椭圆求交本文亮点/核心思想所在核心思想1.圆与椭圆求交方程是四次的最多有四个交点2.圆心到椭圆的四个极值点之间的距离和交点之间的关系我通过分析圆心到几个极值点的距离和圆的半径比较可以得知交点的情况距离和半径相等考虑容差相切都大于无交都小于无交大于小于之间必然夹着一个交点通过好的初值点估计迭代割线法思想稳定获取到交点。————2026.06.19 于上海3.交点个数判定相切判定都是基于距离的判断容差处理稳定*举个例子a. 我知道一个极值距离大于半径一个极值距离小于半径那么这两个极值之间必然存在一个交点;b. 我用二次估值法估计一个好的初值然后用迭代快速计算出精确的交点c. 如果迭代出了问题回归效率低但稳定的二分思想或者割线法: 两个中间必然有一个交点取中间点比较保证总有一个距离大于半径一个距离小于半径。这样不断逼近能稳定找到交点。*适用对象LGKCircle2d与LGKEllipse2d。圆与椭圆求交统一转化为椭圆参数上的标量方程f(t) |E(t) - C|^2 - R^2 0其中E(t)为椭圆参数点。C为圆心。R为圆半径。交点数量、求根区间和初值均由圆心到椭圆的平方距离函数决定q(t) |E(t) - C|^21. 距离极值点先计算圆心C到椭圆的距离极值点q(t) 2 (E(t) - C) · E(t) 0对于整椭圆通常可得到四个极值点t0, t1, t2, t3这些极值点把整椭圆切成四个距离单调区间。圆与椭圆求交时不再全周期采样找根而是在这些单调区间上判断是否存在根。2. 交点数量判断圆椭交点是距离函数水平集q(t) R^2当半径R穿过一个局部最小距离时会产生一对交点当R穿过一个局部最大距离时会消失一对交点当R等于某个极值距离时对应位置为切点。2.1 圆心在椭圆内部的典型情况设两个局部最小距离为m1 m2两个局部最大距离为M1 M2典型情况下m1 m2 M1 M2则交点个数为半径范围交点个数说明R m10圆太小未碰到椭圆R m11第一个最近点切触m1 R m22一侧产生两个交点R m23两个普通交点加一个切点m2 R M14四个普通交点R M13两个普通交点加一个切点M1 R M22一对交点消失R M21最远侧切触R M20圆完全越过椭圆边界2.2 圆心在椭圆外部的简单情况如果距离函数只有一个局部最小点和一个局部最大点设m min d(t) M max d(t)则半径范围交点个数R m0R m1m R M2R M1R M0圆心在椭圆外部时也可能存在四个极值点因此仍然可能出现四个交点。实现上不应仅根据圆心内外写死交点数量而应根据距离极值点和半径所在区间统一判断。3. 求交区间划分将距离极值参数按周期排序t0 t1 t2 t3整椭圆被分为四个区间[t0, t1] [t1, t2] [t2, t3] [t3, t0 2π]在每个相邻极值点之间平方距离函数通常是单调的因此每个区间最多对应一个普通交点。对每个区间端点计算qa q(ta) qb q(tb) s R^2如果s位于[qa, qb]之间则该区间存在候选根。端点满足|qa - s| equationTol或|qb - s| equationTol时端点为切点或端点交点应直接加入候选结果并避免在相邻区间重复加入。4. 推荐初值平方距离线性插值对于存在根的区间[ta, tb]采用平方距离线性插值构造初始参数u (R^2 - qa) / (qb - qa) tInit ta u * (tb - ta)该初值与实际求解方程一致f(t) q(t) - R^2通常比参数中点或圆心方向角更稳定。当qa与qb在容差内相等时该区间不是有效单调跨越区间应优先按端点切点处理不能使用上述插值公式除以接近零的数。5. Halley bracket 保护求交从tInit开始迭代f(t) q(t) - R^2令D(t) E(t) - C则f(t) 2 D(t) · E(t) f(t) 2 E(t) · E(t) 2 D(t) · E(t)其中E(t) -a sin(t) U b cos(t) V E(t) -a cos(t) U - b sin(t) VHalley 步为tHalley t - 2 f f / (2 (f)^2 - f f)保护逻辑当前区间为[ta, tb]且端点函数值异号或端点为根。从平方距离插值初值tInit开始。优先计算 Halley 步。如果 Halley 分母过小、结果不是有限数或tHalley跑出[ta, tb]则使用区间中点。根据f(tNew)与端点符号更新 bracket。收敛后得到交点参数t*。切点附近f(t)会接近零因此切点应优先由端点极值检测加入普通区间内部根再使用 Halley bracket。6. Newton bracket 对比实现可实现一个同签名的 Newton bracket 求根函数用于对比tNewton t - f / f保护逻辑与 Halley 相同if tNewton 不在 [ta, tb] 内或 f 过小: tNewton 0.5 * (ta tb)建议在调试或测试中记录两者迭代次数。预期 Halley 在普通交点上更快收敛Newton 实现更简单且可作为回退对照。7. 椭圆弧与圆弧情况如果椭圆是参数区间[tStart, tEnd]上的一段弧则候选分割点为tStart tEnd 参数域内的所有距离极值点排序后对每个相邻区间执行同样的端点检查、平方距离插值和 Halley bracket 保护迭代。如果圆也是圆弧则圆椭求交得到候选点后还需要检查候选点是否落在圆弧参数域内。参数范围判断应使用曲线参数域与几何点一致性双重检查避免端点附近结果不一致。8. 结果去重与交点类型求交过程中端点切点和相邻区间迭代结果可能产生重复点需要按几何距离去重。交点类型可按切向关系判断若椭圆切向与圆切向平行则为Tangent。否则为Simple。圆切向为Tcircle perpendicular(P - C)椭圆切向为Tellipse E(t)当两者叉积长度在角度容差或等效切向容差内时判定为切交。三. 实现要点点到椭圆最近点和圆椭求交都应优先在椭圆局部坐标系中计算减少坐标变换误差。点到椭圆最近点主方案使用 λ 方程 Halley bracket 保护Newton bracket 作为对比实现。圆椭求交中交点数量、求根区间和初值都应基于圆心到椭圆的距离极值点。圆椭求交初值采用平方距离线性插值u (R^2 - qa) / (qb - qa)。圆椭求根主方案使用 Halley bracket 保护Newton bracket 用于对比验证。极值点半径相等、圆心位于椭圆中心、椭圆退化为圆等情况需要合并处理避免重复或漏交点。