快速几何接近谓词

Question

我有3个点(A,B和X)和距离(d).我需要创建一个函数来测试点X是否比距离d更接近线段AB上的任何点.

问题首先是,我的解决方案是正确的,然后提出更好(更快)的解决方案.

我的第一次通过如下

AX = X-A
BX = X-B
AB = A-B

    // closer than d to A (done squared to avoid needing to compute the sqrt in mag)
If d^2 > AX.mag^2  return true

    // closer than d to B
If d^2 > BX.mag^2 return true

    // "beyond"  B
If (dot(BX,AB) < 0) return false

    // "beyond"  A
If (dot(AX,AB) > 0) return false

    // find component of BX perpendicular to AB
Return (BX.mag)^2 - (dot(AB,BX)/AB.mag)^2 < d^2

这段代码最终将运行一大堆P和一大组A/B/d三元组,目的是找到所有通过至少一个A/B/d的P,所以我怀疑有一种方法在此基础上降低总体成本,但我还没有考虑过.

(顺便说一句:我知道一些重新排序,一些临时值和一些代数身份可能会降低上述成本.为了清楚起见,我只是省略了它们.)

---

编辑:这是一个2D问题(但推广到3D的解决方案很酷

编辑:进一步反思,我预计命中率约为50%.X点可以在嵌套层次结构中形成,因此我希望能够将大型子树修剪为全通和全失败.限制三胞胎的A/B/D将更加成功.

编辑:d与AB的数量级相同.

---

编辑:Artelius发布了一个很好的解决方案.在我完全理解它之前,我不确定我是否正确理解了他所得到的东西.无论如何,我想到了另一个想法:

• 首先是Artelius的位,预先确定一个矩阵,它将AB放置在原点的中心并与X轴对齐.(2加,4 muls和2加)
• 将它全部折叠到第一象限(2 abs)
• 在X和Y中缩放以使区域的中心部分成为单位正方形(2 mul)
• 测试点是否在那个方块(2测试)是如此退出
• 测试端盖(返回未缩放的值
  • 在x中翻译以将结尾放在原点(1添加)
  • 方和添加(2 mul,1 add)
  • 与d ^ 2(1 cmp)比较

我很确定这会打败我的解决方案.

(如果没有什么比这更好的了,Artelius获得了"奖品":)

Answer 1

如果你的(A,B,d)集合是固定的，你可以为每一个计算一对矩阵来平移坐标系，这样AB线就成为X轴，AB的中点就是原点。

我认为这是构造矩阵的简单方法：

trans = - ((A + B) / 2)        // translate midpoint of AB to origin

rot.col1 = AB / AB.mag         // unit vector in AB direction

                        0 -1    
rot.col2 = rot.col1 * (      ) // unit vector perp to AB
                        1  0 

rot = rot.inverse()            // but it needs to be done in reverse

然后你只需取出每个 X 并执行rot * (X + trans)。

现在，所讨论的区域实际上在 x 轴和 y 轴上都是对称的，因此您可以取 x 坐标和 y 坐标的绝对值。

然后你只需要检查：

y < d && x < AB.mag/2            //"along" the line segment
|| (x - AB.mag/2)^2 + y^2 < d^2  // the "end cap".

你还可以使用另一个技巧；矩阵可以按比例缩小AB.mag/2（请记住，每个（A，B）矩阵仅计算一次，这意味着最好找到它们比实际检查本身更慢）。这意味着您的支票将变为：

y < 2*d/AB.mag && x < 1
|| (x - 1)^2 + y^2 < (2*d/AB.mag)^2

将 AB.mag/2 的两个实例替换为常量 1 后，速度可能会快一些。当然你也可以2*d/AB.mag预先计算。(2*d/AB.mag)^2

这是否比其他方法更快取决于您提供的输入。但如果 AB 的长度比 d 长，我认为它会比您发布的方法快得多。