直线和正方形之间的交点 [英] intersection between a line and square

问题描述

我在2d空间中有一个正方形(宽度=高度).正方形当前由两个点定义:BottomLeft(X1，Y1)和TopRight(X2，Y2).

I have a square in 2d space (width = height). The square is currently defined by two points: BottomLeft(X1,Y1) and TopRight(X2,Y2).

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

The square is axis-aligned, so finding the other two corners is as easy as (X1, Y2) and (X2, Y1).

我也有两个要点-一个总是在正方形内，另一个肯定在外面.它们不一定位于正方形的中心-可以位于任何地方.我也知道他们的坐标.

I also have two points - one is always inside the square, and the other is definitely outside. They aren't necessarily at the centre of the square - they can be wherever. I know their coordinates too.

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

What I need is to find the intersection point between the line segment defined by these two points, and the side of the square. I also want to know which side of the square I intersected. What gives me trouble are cases where the line goes diagonally, and close to the corner of the square - so for example it can either intersect top or the side line.

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

The brute-force method is to try and calculate the intersections for each side of the square and check if it exists. It can be optimized by calculating where in relation to the square the second point lies, and discarding two lines (for example if both X and Y coordinates increase, there's no need to check bottom and left sides of the square).

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

I'm wondering if there's a better/faster solution to my problem? I'll be writing in Java

推荐答案

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

以参数形式表示行

vx = ox - x0
vy = oy - y0

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

现在根据方向找到潜在的边界位置:

Now find potential border positions depending on direction:

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

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

检查水平/垂直线方向的其他情况:

Check extra cases of horizontal/vertical line direction:

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

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

通常情况下，找到水平和垂直边缘线相交的参数

In general case find parameters of intersections with horizontal and vertical edge lines

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

获得较小的参数值的交集

And get intersection for smaller parameter value

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

这篇关于直线和正方形之间的交点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！