performance - 具有从其中心点发出的线段的边界框的高性能相交算法

Question

对于 stackoverflow 上列出的类似问题，有许多接近且有用的答案，但是我还没有找到任何与我的特定情况相匹配的答案。

我需要一种性能高效的算法来计算边界框与从其中心点发出的线段的交点。每个边界框可能有多个线段放射。

根据我的问题的定义，每个线段将与边界框边缘段的一个（除了 4 个点之外只有一个）相交。

这是一个插图。

我想快速和计算“廉价”计算：

1. 线段与哪个边界框边缘相交？

2. 边和线段的交点是什么？

谢谢。

Answer 1

令 C 为边界框的中心，P 为线段的另一个端点。令 V = (Vx, Vy) = P - C 为从 C 指向 P 的向量。

让边界框的高度 = 2 * H 和宽度 = 2 * W。W 和 H 是正常高度和宽度的一半，这将使下面的计算更简单。

想法是这样的：考虑 V 位于第一象限的情况，因此 Vx > 0 且 Vy > 0。然后该段与顶部或右侧相交。我们可以通过比较 V 的斜率和从盒子中心到右上角的线段的斜率来判断是哪一个。如果斜率较大，则与顶部相交，否则与侧面相交。

因此，如果 V 在第一象限，并且如果 Vy / Vx > H / W，则该段与顶部相交。如果 Vy / Vx < H / W，它与边相交。如果它们相等，则与角相交。

一旦你知道它与哪一边相交，你就可以使用相似的三角形来找出相交点。如果它在点 I = (Ix, H) 处与顶部相交，则 Vx / Vy = Ix / H 或 Ix = H * Vx / Vy。如果它在 I = (W, Iy) 点与边相交，则 Vy / Vx = Iy / W 或 Iy = W * Vy / Vx。

同样的方法也适用于其他象限；您只需要跟踪 Vx 和 Vy 的迹象。您可以通过断言返回值满足 sign(Ix) == sign(Vx) 和 sign(Iy) == sign(Vy) 让您的生活更轻松一些。

还要注意，如果你对符号很小心，你可以避免除法：假设 Vx > 0，Vy / Vx > H / W 等价于 Vy * W > Vx * H。

Answer 2

假设您有一个以 (0,0) 为中心的方形盒子，边长为 2。假设您有一个从盒子中心向外辐射的向量 (dx,dy)。然后计算 (xp,yp) 射线与边缘相交的点。

它执行两个fabs、两个比较、一个除法和两个赋值。然后，您只需将其翻译并缩放到您的特定方块。

if (fabs(dx) > fabs(dy)){
  if (dx > 0){
    xp = 1;     // right side
    yp = dy/dx;
  } else {
    xp = -1;     // left side
    yp = -dy/dx
  }
} else {
  if (dy > 0){
    yp = 1;     // top side
    xp = dx/dy;
  } else {
    yp = -1;     // bottom side
    xp = -dx/dy
  }
}