快速几何接近谓词

我有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获得了"奖品":)