直线与正方形的交点

Question

我有一个二维正方形 space（宽度 = 高度）。该正方形当前由两个点定义：BottomLeft(X1,Y1) 和 TopRight(X2,Y2)。

正方形是轴对齐的，所以找到其他两个角就像 (X1, Y2) 和 (X2, Y1) 一样容易。

我还有两点，一是永远在广场内，二是肯定在广场外。它们不一定在广场的中心——它们可以在任何地方。我也知道他们的坐标。

我需要的是找到这两点定义的线段与正方形边的交点。我还想知道我与广场的哪一侧相交。给我带来麻烦的是线沿对角线延伸并靠近正方形角的情况 - 例如它可以与顶部或侧线相交。

蛮力法是尝试计算正方形每一边的交点并检查它是否存在。它可以通过计算第二个点相对于正方形的位置并丢弃两条线来优化（例如，如果 X 和 Y 坐标都增加，则无需检查正方形的底部和左侧）。

我想知道是否有 better/faster 解决我的问题的方法？我会写在 Java

Answer 1

设内点为(x0, y0)，外点为(ox, oy)

以参数形式表示线

vx = ox - x0
vy = oy - y0

//equations:
x = x0 + vx * t
y = y0 + vy * t

现在根据方向查找潜在的边界位置：

if vx > 0 then
   ex = x2
else
   ex = x1

if vy > 0 then
    ey = y2
else
   ey = y1

检查horizontal/vertical行方向的额外情况：

 if vx = 0 then
      return cx = x0,  cy = ey

 if vy = 0 then
      return cx = ex, cy = y0

一般情况下求水平和垂直边线交点的参数

 tx = (ex - x0) / vx
 ty = (ey - y0) / vy

并获取较小参数值的交集

 if tx <= ty then //meet vertical edge first
     return cx = ex, cy = y0 + tx * vy
 else
    return  cx = x0 + ty * vx,  cy = ey

Answer 2

高效解法：

我假设你知道哪个点在正方形（也可以是矩形）内。

从所有其他点（第二个端点和四个角）中减去此点的坐标。考虑通过延长正方形的边形成九个区域的平面细分。需要四次符号测试才能知道另一点位于八个外部区域中的哪一个。

然后，如果该点位于 "side" 区域内，则您隐式知道哪一侧被越过。如果该点位于 "corner" 区域内，则必须在两侧之间做出决定，这是通过检查拐角位于线段的哪一侧来完成的。这需要计算三角形的符号面积（两次乘法和一次减法）。

当你知道哪边被交叉时，通过比例找到交点就很容易了。这需要一个除法。

最后，你平移回内点原来的位置。总费用为

加上一点粘合逻辑。

这不能保证是绝对最小值，但必须接近。

intersection between a line and square