如何找出射线是否与矩形相交？

Question

我们有一条射线，从A(X, Y)开始，并在给定点B(X, Y) != A上永远持续下去。我们有一个由点K,L,M,N定义的矩形，每个点的(X, Y)。

我不知道如何检测我们的射线是否与我们的矩形的任何点相交（获得bool，不是精确坐标）？什么是计算这种值的算法？

Answer 1

让我直说吧。您有一个载体v，方向(b_x - a_x, b_y - a_y)，从(a_x, a_y)开始。

考虑向量w = (b_y - a_y, a_x - b_x)。它与第一个成直角。 （使用点积进行验证。）因此，对于任何点(p_x, p_y)，都可以通过使用(p_x - a_x, p_y - a_y)的点积与w并查看符号来轻松地确定其所在向量的哪一侧。

所以把你的矩形的所有4个角的点产品。如果有任何零点产品，则它们在矢量上，如果符号变化，则表示有交点，如果符号始终相同，则表示没有交点。

Answer 2

您可以使用扫描线算法来这样做。

http://en.wikipedia.org/wiki/Sweep_line_algorithm

Answer 3

你可能想计算相交的矩形光线AB的部分（如果有的话）。如果你的矩形是轴对齐的，从数字的角度来看，这将更容易计算，但逻辑应该是相似的。

---

可以表示向线L为[a, b, c]，使得如果点P是(X, Y)：

let L(P) = a*X + b*Y + c 

then, if L(P) == 0, point P is on L 
     if L(P) > 0, point P is to the left of L 
     if L(P) < 0, point P is to the right of L 

注意，这是在这个意义上的冗余，给定任何k > 0，[K *一，k * b，k * c]表示同一行（该属性使其成为homogeneous coordinate system）。我们还可以通过与第三对它们进行协调代表与齐次坐标点：

2D point P = (X, Y) 
-> homogeneous coordinates [x, y, w] for P are [X, Y, 1] 
    L(P) = L.a*P.x + L.b*P.y + L.c*P.w == a*X + b*Y + c*1 

在任何情况下，你的矩形给出两个角（比如，P和Q），就可以计算该行的齐次坐标通过P和Q使用他们的齐次坐标的3-d跨产品：

homogeneous coordinates for line PQ are: [P.X, P.Y, 1] cross [Q.X, Q.Y, 1] 
    -> PQ.a = P.Y - Q.Y 
    PQ.b = Q.X - P.X 
    PQ.c = P.X*Q.Y - Q.X*P.Y 

可以数学验证点P和Q都位于上述线PQ。

---

来表示相交的矩形，第一计算矢量V = B - A，如在@ btilly的回答线AB的段。对于齐次坐标，这种工作方式如下：

A = [A.X, A.Y, 1] 
B = [B.X, B.Y, 1] 
-> V = B - A = [B.X-A.X, B.Y-A.Y, 0] 

for any point C on AB: homogeneous coordinates for C = u*A + v*V 
    (where u and v are not both zero) 

点C将上线只有u和v都是非负的射线部分。 （此表示可能看起来模糊不清，相比C = A + lambda * V通常的制剂，但做这种方式避免了不必要的除以零的情况下...）现在

---

，我们可以计算出射线相交：我们所代表线段AB由各个端点的参数[u,v]坐标：{ start = [start.u, start.v]; end = [end.u, end.v] }。

我们以逆时针方向计算矩形的边缘，使得矩形内的点位于每条边的左侧/正侧（L(P)>0）。

Starting segment is entire ray: 
    start.u = 1; start.v = 0 
    end.u = 0; end.v = 1 

for each counterclockwise-directed edge L of the rectangle: 
    compute: 
    L(A) = L.a*A.X + L.b*A.Y + L.c 
    L(V) = L.a*V.X + L.b*V.Y 
    L(start) = start.u * L(A) + start.v * L(V) 
    L(end) = end.u * L(A) + end.v * L(V) 
    if L(start) and L(end) are both less than zero: 
    exit early: return "no intersection found" 
    if L(start) and L(end) are both greater or equal to zero: 
    do not update the segment; continue with the next line 
    else, if L(start) < 0: 
    update start coordinates: 
     start.u := L(V) 
     start.v := -L(A) 
    else, if L(end) < 0: 
    update end coordinates: 
     end.u := -L(V) 
     end.v := L(A) 

on normal loop exit, the ray does intersect the rectangle; 
the part of the ray inside the rectangle is the segment between points: 
    homog_start = start.u * A + start.v * V 
    homog_end = end.u * A + end.v * V 
return "intersection found": 
    intersection_start.X = homog_start.x/homog_start.w 
    intersection_start.Y = homog_start.y/homog_start.w 
    intersection_end.X = homog_end.x/homog_end.w 
    intersection_end.Y = homog_end.y/homog_end.w 

请注意，这将适用于任意凸多边形，而不仅仅是矩形;上面实际上是一个普通的射线/凸多边形相交算法。对于矩形，您可以展开for循环;如果矩形是轴对齐的，则可以大大简化算法。然而，内部循环中的4个案例决定应该对每个边缘保持相同。

Answer 4

一个不太聪明，但概念上更简单的方法：射线与矩形相交，当且仅当它与至少一个边相交时。因此，对于矩形的每一侧，找到穿过端点的线与光线AB的交点（如果有的话）;那么它只是一个范围检查，以确定该交点是否位于矩形边界上的线段的一部分，或者是否在外部。