javascript - 如何检查线段是否与正方形相交

Question

我有一条由两点 a 和 b 确定的线段。我还有一个由 x0 < x < x1 和 y0 < y < y1 确定的正方形，其中 x1-x0 = y1-y0。我正在尝试检查线段的任何部分是否与正方形内的区域相交。 (如果线段刚好接触到不算交叉点的边)。

我的想法是使用这张图片

function(a, b, x0, x1, y0, y1) {
  if (a or b is inside square)
    return true;
  else {
    switch (which quadrant is a in) {
      case 1: return (ab intersects top of square);
      case 2: return (ab intersects left of square);
      case 3: return (ab intersects bottom of square);
      case 4: return (ab intersects right of square);
    }
  }
}

我想知道是否有更好的方法来解决这个问题。

Answer 1

我想到的一个简短答案就是测试线段与您的线和正方形的 4 条线的交点使用标准计算几何叉积。

这是一个快速教程 http://web.stanford.edu/class/cs97si/09-computational-geometry.pdf

Define ccw(A,B,C) = (B-A) X (C-A) where A,B,C is some point
ccw(A,B,C) < 0 means C lies on the left side of line AB
ccw(A,B,C) > 0 means C lies on the right side of line AB

所以测试线段相交就像给出两条线 AB(您的线段)和 CD(正方形的任意一侧)

它们正确相交(即不包括触摸情况)当且仅当

ccw(A,B,C) * ccw(A,B,D) < 0 AND ccw(C,D,A) * ccw(C,D,B) < 0

简单的意思是“C 和 D 位于 AB 线的不同侧，而 A 和 B 位于线 CD 的不同侧”--> 交点