2

如何在 2D 中找到射线之间最近的交点：

x = x0 + t*cos(a), y = y0 + t*sin(a)

和 m 多段线：

{(x1,y1), (x2,y2), ..., (xn,yn)}

迅速地？

我开始循环遍历所有线段和每个线段； {(x1,y1),(x2,y2)}解决：

x1 + u*(x2-x1) = x0 + t*cos(a)

y1 + u*(y2-y1) = y0 + t*sin(a)

根据克莱默的规则，然后按距离对交叉点进行排序，但这很慢:-(

顺便说一句：折线恰好在 中单调递增x。

4

2 回答 2

2

坐标系变换

我建议您首先将您的设置转换为更简单的坐标：

  1. Take your point p = (x, y).
  2. Move it by (-x0, -y0) so that the ray now starts at the center.
  3. Rotate it by -a so that the ray now lies on the x axis.

So far the above operations have cost you four additions and four multiplications per point:

ca = cos(a) # computed only once
sa = sin(a) # likewise

x' = x - x0
y' = y - y0
x'' = x'*ca + y'*sa 
y'' = y'*ca - x'*sa

Checking for intersections

Now you know that a segment of the polyline will only intersect the ray if the sign of its y'' value changes, i.e. y1'' * y2'' < 0. You could even postpone the computation of the x'' values until after this check. Furthermore, the segment will only intersect the ray if the intersection of the segment with the x axis occurs for x > 0, which can only happen if either value is greater than zero, i.e. x1'' > 0 or x2'' > 0. If both x'' are greater than zero, then you know there is an intersection.

The following paragraph is kind of optional, don't worry if you don't understand it, there is an alternative noted later on.
If one x'' is positive but the other is negative, then you have to check further. Suppose that the sign of y'' changed from negative to positive, i.e. y1'' < 0 < y2''. The line from p1'' to p2'' will intersect the x axis at x > 0 if and only if the triangle formed by p1'', p2'' and the origin is oriented counter-clockwise. You can determine the orientation of that triangle by examining the sign of the determinant x1''*y2'' - x2''*y1'', it will be positive for a counter-clockwise triangle. If the direction of the sign change is different, the orientation has to be different as well. So to take this together, you can check whether 

(x1'' * y2'' - x2'' * y1'') * y2'' > 0

If that is the case, then you have an intersection. Notice that there were no costly divisions involved so far.

Computing intersections

As you want to not only decide whether an intersection exists, but actually find a specific one, you now have to compute that intersection. Let's call it p3. It must satisfy the equations

(x2'' - x3'')/(y2'' - y3'') = (x1'' - x3'')/(y1'' - y3'') and 
                       y3'' = 0

which results in

x3'' = (x1'' * y1'' - x2'' * y2'')/(y1'' - y2'')

Instead of the triangle orientation check from the previous paragraph, you could always compute this x3'' value and discard any results where it turns out to be negative. Less code, but more divisions. Benchmark if in doubt about performance.

To find the point closest to the origin of the ray, you take the result with minimal x3'' value, which you can then transform back into its original position:

x3 = x3''*ca + x0
y3 = x3''*sa + y0

There you are.

Note that all of the above assumed that all numbers were either positive or negative. If you have zeros, it depends on the exact interpretation of what you actually want to compute, how you want to handle these border cases.

于 2012-10-05T15:57:58.537 回答
1

为了避免检查与所有段的交集，需要一些空间分区，例如Quadtree，BSP tree。对于空间分区，需要检查与空间分区的光线相交。

在这种情况下，由于点是按 x 坐标排序的，因此可以用框(min x, min y)-(max x, max y)对折线的一部分进行空间划分。根框是所有点的最小值-最大值，它被分成 2 个框，用于折线的第一部分和第二部分。零件中的段数相同或一个盒子多一个段。这种盒子分割是递归完成的，直到只有一个段在一个盒子里。

要检查射线相交从根框开始，检查它是否与射线相交，如果是，则检查 2 个子框是否相交，首先测试更近的子框，然后测试更远的子框。

检查光线盒相交是检查光线是否穿过两个位置之间的轴对齐线。这是针对 4 个框边界完成的。

于 2012-10-05T15:26:28.937 回答