5

我有 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个腹肌）
  • 在 X&Y 中缩放以使区域的中心部分成为一个单位正方形 (2 mul)
  • test if the point is in that square (2 test) is so quit
  • test the end cap (go back to the unscaled values
    • translate in x to place the end at the origin (1 add)
    • square and add (2 mul, 1 add)
    • compare to d^2 (1 cmp)

I'm fairly sure this beats my solution.

(if nothing better comes along sone Artelius gets the "prize" :)

4

5 回答 5

2

Hmmmmmmm.... What's the hit-rate? How often does point "X" meet the proximity requirements?

I think your existing algorithm is good, and any additional optimizations will come from tuning to the real data. For example, if the "X" point meets the proximity test 99% of the time, then I think your optimization strategy should be considerably different than if it only passes the test 1% of the time.

Incidentally, when you get to the point where you're running this algorithm with thousands of points, you should organize all the points into a K-Dimensional Tree (or KDTree). It makes the calculation of "nearest-neighbor" much simpler.

Your problem is a little more complex than a basic nearest-neighbor (because you're checking proximity-to-a-line-segment rather than just proximity-to-a-point) but I still think the KDTree will be handy.

于 2008-10-31T21:33:38.617 回答
2

If I read this correctly, then this is almost the same as the classic ray/sphere intersection test as used in 3D ray-tracing.

In this case you have a sphere at location X of radius d, and you're trying to find out whether the line AB intersects the sphere. The one difference with ray-tracing is that in this case you've got a specific line AB, whereas in ray-tracing the ray is normally generalised as as origin + distance * direction, and you don't care how far along the infinite line AB+ it is.

In pseudo-code from my own ray-tracer (based on the algorithm given in "An Introduction to Ray-tracing" (ed. Glassner):

Vector v = X - A
Vector d = normalise(B - A)  // unit direction vector of AB
double b = dot(v, B - A)
double discrim = b^2 - dot(v, v) + d^2
if (discrim < 0)
     return false            // definitely no intersection

If you've got this far, then there's some chance that your condition is met. You just have to figure out whether the intersection(s) is on the line AB:

discrim = sqrt(discrim)
double t2 = b + discrim
if (t2 <= 0)
    return false             // intersection is before A

double t1 = b  - discrim

result = (t1 < length(AB) || (t2 < length(AB))
于 2008-10-31T23:05:04.877 回答
2

If your set of (A,B,d) in fixed, you can calculate a pair of matrices for each to translate the co-ordinate system, so that the line AB becomes the X axis, and the midpoint of AB is the origin.

I think this is a simple way to construct the matrices:

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

Then you just take each X and do rot * (X + trans).

The region in question is actually symmetric in both the x and y axes now, so you can take the absolute value of the x co-ordinate, and of the y co-ordinate.

Then you just need to check:

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

You can do another trick; the matrix can scale down by a factor of AB.mag/2 (remember the matrices are only calculated once per (A,B) meaning that it's better that finding them is slower, than the actual check itself). This means your check becomes:

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

Having replaced two instances of AB.mag/2 with the constant 1, it might be a touch faster. And of course you can precalculate 2*d/AB.mag and (2*d/AB.mag)^2 as well.

Whether this will work out faster than other methods depends on the inputs you give it. But if the length of AB is long compared to d, I think it will turn out considerably faster than the method you posted.

于 2008-10-31T23:17:23.370 回答
1

This code will end up being run for a large set of P's and a large set of A/B/d triplets with the intent of finding all P's that pass for at least one A/B/d so I suspect that there is a way to reduce overall the cost based on that but I haven't looked into that yet.

In the case when d ~ AB, for a given point X, you can first test whether X belongs to one of the many spheres of radius d and center Ai or Bi. Look at the picture:

     ......        .....
  ...........   ...........
 ...........................
.......A-------------B.......
 ...........................
  ...........   ...........
     .....         .....

The first two tests

If d^2 > AX.mag^2 return true
If d^2 > BX.mag^2 return true

are the fastest ones, and if d ~ AB they are also the ones with highest probability to succeed (given that the test succeeds at all). Given X, you can do all the "sphere tests" first, and then all the final ones:

Return (BX.mag)^2 - (dot(AB,BX)/AB.mag)^2
于 2008-10-31T22:18:54.063 回答
1

If the # of sets of A/B/d are large, and you're definitely in 2D, consider using R-trees (or their octagonal equivalents) where each entry in the R-tree is the minimum bounding box of the A/B/d triple. This would let you eliminate having to test a lot of the A/B/d triples & focus your CPU power only on the few ones where each point X is within the bounding boxes of the A/B/d triple. Then do a more detailed test like the one you mention.

于 2008-12-10T15:14:39.793 回答