2d段的最近点,通过第3个2d段
Sne*_*tel 9 math geometry intersection mathematical-optimization computational-geometry
使用图表可以更轻松.CaRMetal,攻击!
我有两个2D线段,P和Q.我想找到点Px上P,和Qx上Q,以便dist(Px,Qx)最小化.到现在为止还挺好; 这是一项非常简单的任务.
皱纹现在来了.我想约束Px并且包含它们Qx的行PxQx必须与第三个线段相交C.(可以自由地假设没有原始线段相交,BTW.)
- 显然有一种情况是无约束
Px且Qx已经恰好满足C交叉条件. - 还有一个不可行的情况下,如果
C不甚至含有的凸包P和Q.这些是需要检查的微不足道的案例. - 在其他情况下,该行
PxQx必须包含Ca或Cb.这似乎没有干净地减少到线性方程组. - 在最后一组案例中,
PxQx不仅包含端点C,还包含端点P或者Q也包含端点.这些看起来很简单.
我担心的是(3)中的情况,因为我没有看到如何在不调用令人不快的高次多项式的情况下获得一个好的封闭形式.当然,我可以在整个过程中投入一个迭代约束优化器,但我希望最大限度地提高性能,并且在近简并情况下的高精度可能很重要.
我想在这里写下一个简短的小公式并说'瞧',但这不会发生,这就是原因.这个问题是找到两个线段之间最短距离的延伸,这是Dan Sunday在段和光线之间的距离中很好地描述的.使用此图中的标签和符号
我们可以参数化P,并Q通过P(t) = P_0 + t(P_1 - P_0)与Q(s) = Q_0 + s(Q_1 - Q_0)地方分减法做协调明智的,即Q_1 - Q_0 = (m1-m0,n1-n0).与此参数化找到线段之间的最短距离的问题P和Q简单地最小化的距离^ 2,
f(s,t) = (a0 + (a1 - a0)*t - m0 - (m1 - m0)*s)^2 + (b0 + (b1-b0)*t - n0 - (n1-n0)*s)^2
在s,t太空的区域0<=s<=1和0<=t<=1.(此变换避免处理平方根同时保留最小值的位置)请注意,除非段相交,否则边界上会出现最小值.
然而,我们还有一个约束 - 我们只考虑(s,t)连接P(t)和Q(s)通过的线对C.修正了一个点Cp = (c,d)上C.然后,如果相关联的一对线(s,t)穿过Cp,该矢量P(t)->Cp和Q(S)->Cp
必须是平行的.由于这是一个2D问题,我们设置z方向0并使用交叉积(对于平行向量必须为零)才能得到任何这样的(s,t)必须满足关系
g(s,t) = (a0 + (a1 - a0)*t - c)*(n0 + (n1 - n0)*s -d) - (b0 +(b1 - b0)*t - d)*(m0 + (m1 - m0)*s -d) = 0
所以解决方案g(s,t) = 0都是(s,t)连接其相关点的线路所在的所有线对Cp.如果我们参数化C的C(r) = C_0 + r(C_1 - C_0),那么我们可以认为与每个r是一套解决方案,g(s,t) = 0我们让地方Cp = C(r).绘制g(s,t)上[0,1]X[0,1],我们可以看到这些曲线的样子.
![距离^ 2的色图,其中<code>r</code>的轮廓<code>C(0)</code>和<code>C(1)</code>形成边界的增加而增加.图中的底层颜色是值<code>f(s,t)</code>.更一般地,可行区域(即这些值<code>(s,t)</code>是该问题可能的解决方案),我们额外的约束是在框中点<code>[0,1]X[0,1]</code>,同时也是轮廓的之间<code>C(0)</code>和<code>C(1)</code>.当然,两个轮廓都不可能与盒子相交,<code>[0,1]X[0,1]</code>此时整个盒子是可行的,或者没有解决方案.和以前一样,除非<code>P</code>并且<code>Q</code>在可行区域相交,会发生的边界上的最小值. </noimg></p>
<p>因此,这是受约束的优化问题.可行区域的边界分为三种类型之一:</p>
<ol>
<li>交点</li>
<li>盒子的边缘 <code>[0,1]X[0,1]</code></li>
<li><code>g(s,t) = 0</code>任何一个<code>C(0)</code>或两个的轮廓<code>C(1)</code></li>
</ol>
<p>前两个很容易检查.然而第三个是有趣的地方.好消息是我们试图最小化二次约束条件下的二次函数.坏消息是,这意味着我们需要解决一个立方体才能这样做.为最小化的最小值的闭合形式<code>f(s,t)</code>经受<code>g(s,t) = 0</code>是解决方程系统(参考任何演算教科书或<a rel=](https://i.stack.imgur.com/xMn3v.png)
维基百科,拉格朗日乘子)
(partial g)/(partial s) (partial f)/partial t) = (partial g)/(partial t) (partial f)/partial s)g(s,t) = 0
也被称为
-2*((b0 - b1)*((n0 - n1)*s - (b0 - b1)*t + b0 - n0) + (a0 - a1)*((m0 - m1)*s - (a0 - a1)*t + a0 - m0))*((n0 - n1)*((a0 - a1)*t - a0 + c) - (m0 - m1)*((b0 - b1)*t - b0 + d)) + 2*((b0 - b1)*((m0 - m1)*s + d - m0) - (a0 - a1)*((n0 - n1)*s + d - n0))*((n0 - n1)*((n0 - n1)*s - (b0 - b1)*t + b0 - n0) + (m0 - m1)*((m0 - m1)*s - (a0 - a1)*t + a0 - m0)) = 0(a0 + (a1 - a0)*t - c)*(n0 + (n1 - n0)*s -d) - (b0 +(b1 - b0)*t - d)*(m0 + (m1 - m0)*s -d) = 0
对于三次方程有一个闭合形式,因此存在一个解决方案,取决于适当的边界假设.(特别是你需要系数of s和tin g非零.)结果很长.
或者,我们正在最小化一个抛物面,因此它在正常的二次曲线上是二次的g(s,t) = 0.这非常适合二元搜索,它具有快速收敛并且不需要任何平方根的附加奖励.
\n\n\nPx = P ( t1 ) = Pa · (1 - t1 ) + Pb · t1
\n\n
\n Qx = Q ( t2 ) = Qa · (1 - t2 ) + Qb · t2最小化f ( t1 , t2 ) = | PX - Qx | 2
\n
使用“如何检测两条线段相交的位置？”中的方程 ， 我们有：
\n\n\n\n\nt ( t1 , t2 ) = ( Ca - Px ) \xe2\xa8\xaf ( Cb - Ca ) / ( Qx - Px ) \xe2\xa8\xaf ( Cb - Ca )
\n
\n u ( t1 , t2 ) = ( Ca - Px ) \xe2\xa8\xaf ( Qx - Px ) / ( Qx - Px ) \xe2\xa8\xaf ( Cb - Ca )
（\xe2\xa8\xaf = 叉积）
\n\n这两个值必须介于 0 和 1 之间才能使线段相交。t是沿着Px Qx线的位置，u是沿着C线的位置。如果展开公式，它们将是两个线性或二次函数的商。
\n\n由于您只需将t和u 与零和一进行比较，因此可以稍微简化它们：
\n\n\n\n\nt ( t1 , t2 ) = 0
\n
\n ( Ca - Px ) \xe2\xa8\xaf ( Cb - Ca ) / ( Qx - Px ) \xe2\xa8\xaf ( Cb - Ca ) = 0
\n ( Ca - Px ) \xe2\xa8\xaf ( Cb - Ca ) = 0, Qx ≠ Px
和
\n\n\n\n\nt ( t1 , t2 ) = 1
\n
\n ( Ca - Px ) \xe2\xa8\xaf ( Cb - Ca ) / ( Qx - Px ) \xe2\xa8\xaf ( Cb - Ca ) = 1
\n ( Ca - Px ) \xe2\xa8\xaf ( Cb - Ca ) - ( Qx - Px ) \xe2\xa8\xaf ( Cb - Ca ) = 0
\n ( Ca - Qx ) \xe2\xa8\xaf ( Cb - Ca ) = 0，Qx ≠ Px
和
\n\n\n\n\nu ( t1 , t2 ) = 0
\n
\n ( Ca - Px ) \xe2\xa8\xaf ( Qx - Px ) / ( Qx - Px ) \xe2\xa8\xaf ( Cb - Ca ) = 0
\n ( Ca - Px ) \xe2\xa8\xaf ( Qx - Px ) = 0, Qx ≠ Px
和
\n\n\n\n\nu ( t1 , t2 ) = 1
\n
\n ( Ca - Px ) \xe2\xa8\xaf ( Qx - Px ) / ( Qx - Px ) \xe2\xa8\xaf ( Cb - Ca ) = 1
\n ( Ca - Px ) \xe2\xa8\xaf ( Qx - Px ) - ( Qx - Px ) \xe2\xa8\xaf ( Cb - Ca ) = 0
\n ( Ca - Px ) \xe2\xa8\xaf ( Qx - Px ) + ( Cb - Ca ) \xe2\xa8\xaf ( Qx - Px ) = 0
\n ( Cb - Px ) \xe2\xa8\xaf ( Qx - Px ) = 0，Qx ≠ Px
我们有四个限制（或八个，具体取决于您的计数方式）：
\n\n- \n
- 0≤t1≤1 \n
- 0≤t2≤1 \n
- 0≤t ( t1 , t2 ) ≤1 \n
- 0≤u ( t1 , t2 ) ≤1 \n
您有四个约束变量，每个变量有两个边界。这使得您必须考虑总共八种情况，每种情况在 ( t1 , t2 ) 空间中形成一条曲线或线段。
\n\n约束在允许值的 ( t1 , t2 ) 空间中形成一个区域。您必须沿着该区域的外边缘追踪并找到使Px和Qx之间的距离最小的点。只要线段P和Q不相交，最小值将始终位于外边界上。尽管在某些情况下，不会有任何有效的解决方案。
\n\n\n\n
要找到最小值（t1，t2），您需要评估所有候选点：
\n\n- \n
- 内部最小；线P和Q相交的点。（1分） \n
- 最小边界；沿任意边界曲线的最小值。（8分） \n
- 最小交叉点；任意两条边界曲线相交的点。（24分） \n
对于每个点，您需要检查它是否符合所有其他约束，并选择在Px和Qx之间生成最小距离的点。
\n\n要找到内部最小点，请求解t1、t2的Px = Py。如果该点落在其他边界内，则两条线交叉并穿过C线。（极不可能）
\n\n要找到边界最小点，您需要查看沿曲线的斜率。这可以通过求解找到
\n\n\n\n\n{\n ∇ f ( t1 , t2 ) \xe2\xa8\xaf ∇ G ( t1 , t2 ) = 0,\n G ( t1 , t2 ) = k \n }
\n
对于t1 , t2，其中 ∇ 是Nabla 算子（函数一阶导数的向量），G ( t1 , t2 ) = k是边界条件，例如t ( t1 , t2 ) = 1。
\n\n要找到交点最小点，您需要使两条曲线相等，并求解t1、t2。
\n\n组织此操作的一种方法是计算每条约束曲线的多项式系数，并编写一个函数来检查交点。
\n\n\n\n(A 1 + A 2 · t1 + A 3 · t1 2 + A 4 · t2 + A 5 · t1 · t2 + A 6 · t2 2 ) / (A 7 + A 8 · t1 + A 9 · t2 )
\n