java - 直线与正方形的交点

Question

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

正方形是轴对齐的，因此找到其他两个角就像 (X1, Y2) 和 (X2, Y1) 一样简单。

我也有两点——一个总是在广场里面，另一个肯定在外面。它们不一定在广场的中心——它们可以在任何地方。我也知道他们的坐标。

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

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

我想知道是否有更好/更快的解决方案来解决我的问题？我将用 Java 编写

score 1 · Accepted Answer

设内点为(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

检查水平/垂直线方向的额外情况：

 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

score 0 · Accepted Answer

有效的解决方案：

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

从所有其他点（第二个端点和四个角）中减去该点的坐标。考虑将平面细分为九个区域，这些区域是通过扩展正方形的边而形成的。要知道另一点位于八个外部区域中的哪个区域，需要进行四次符号测试。

然后，如果该点位于“侧面”区域，则您隐含地知道穿过了哪一侧。如果该点位于“拐角”区域，则必须在两侧之间做出决定，这是通过检查拐角位于线段的哪一侧来完成的。这需要计算三角形的有符号面积（两个乘法和一个减法）。

当你知道哪边是交叉的时候，通过使用比例找到交叉点是一件容易的事。这需要一个部门。

最后，您转换回内部点的原始位置。总成本为

加上一点胶合逻辑。

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

2 回答 2