java - 直线和正方形之间的交点

Question

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

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

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

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

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

我想知道是否有更好/更快的解决方案来解决我的问题？我将用 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

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

 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