algorithm - 快速几何邻近谓词

Question

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

问题首先是，我的解决方案是否正确，然后想出更好(更快)的解决方案。

我的第一遍如下

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 个乘法和 2 个加法)
• 将其全部折叠到第一象限(2 abs)
• 在 X&Y 上缩放，使区域的中心部分成为一个单位正方形 (2 mul)
• 测试点是否在那个正方形中(2 次测试)所以退出
• 测试端盖(回到未缩放的值
  • 平移 x 以将末端置于原点(1 添加)
  • 平方加法(2 乘法，1 加法)
  • 与 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

用常量 1 替换了 AB.mag/2 的两个实例后，它可能会快一点。当然，您也可以预先计算 2*d/AB.mag 和 (2*d/AB.mag)^2。

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