1

我们有一条从 point 开始A(X, Y)并一直持续到给定 point的射线B(X, Y) != A。我们有一个由点定义的矩形，K,L,M,N每个点都有它的(X, Y).

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

4

4 回答 4

3

让我说清楚。你有一个向量v指向方向(b_x - a_x, b_y - a_y)并从 开始(a_x, a_y)。

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

因此，使用矩形的所有 4 个角来取那个点积。如果任何一个给出 0 点积，它们就在向量上，如果符号发生变化，则存在交集，如果符号始终相同，则没有交集。

于 2012-06-05T23:41:17.333 回答
0

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

于 2012-06-06T19:20:04.710 回答
0

您可能想要计算与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

请注意，这是多余的，因为给定 any k > 0， [k*a, k*b, k*c] 表示同一条线（此属性使其成为齐次坐标系）。我们还可以通过用第三个坐标增加它们来表示具有齐次坐标的点：

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 上。

AB为了表示与矩形相交的线段，首先计算 vector V = B - A，如@btilly 的答案。对于齐次坐标，其工作原理如下：

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才会位于线的射线部分。（与 的通常表述相比，这种表示可能看起来晦涩难懂，但这样做可以避免不必要的被零除的情况......）uvC = 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 种情况决策对于每条边都应该保持不变。

于 2012-06-06T19:11:04.397 回答
0

您可以使用扫描线算法来执行此操作。

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

于 2012-06-06T08:02:15.783 回答