如何测试一个线段相交的2D轴对准rectange？段的定义与它的两个端部：P1，P2。该矩形定义左上角和右下角点。

How to test if a line segment intersects an axis-aligned rectange in 2D? The segment is defined with its two ends: p1, p2. The rectangle is defined with top-left and bottom-right points.

推荐答案

楼主想DETECT线段和多边形之间的交点。没有必要对LOCATE交集，如果有一个。如果这就是你的意思，你可以做的比良巴斯基或科恩 - 萨瑟兰工作量少：

The original poster wanted to DETECT an intersection between a line segment and a polygon. There was no need to LOCATE the intersection, if there is one. If that's how you meant it, you can do less work than Liang-Barsky or Cohen-Sutherland:

让段终点为P1 =（X1 Y1）和p2 =（X2 Y2）。 让矩形的角是（XBL YBL）和（XTR YTR）。

Let the segment endpoints be p1=(x1 y1) and p2=(x2 y2). Let the rectangle's corners be (xBL yBL) and (xTR yTR).

然后，所有你需要做的就是

Then all you have to do is

一个。检查，如果是在该行的同一侧的所有四个角的矩形。 隐方程用于通过p1和p2的直线是：

A. Check if all four corners of the rectangle are on the same side of the line. The implicit equation for a line through p1 and p2 is:

F（XY）=（Y2-Y1）的 X +（X1-X2）的Y +（X 2 * Y1-X1 * Y2）

F(x y) = (y2-y1)x + (x1-x2)y + (x2*y1-x1*y2)

如果F（x和y）= 0，（x和y）就行了。 若F（x和y）> 0，（x和y）是上面的行。 如果F（x和y）＆LT; 0，（x和y）为低于行了。

If F(x y) = 0, (x y) is ON the line. If F(x y) > 0, (x y) is "above" the line. If F(x y) < 0, (x y) is "below" the line.

替换四角为F（x和y）。如果他们都是阴性或阳性全部，没有交集。如果有些是积极的，一些负面的，执行步骤b。

Substitute all four corners into F(x y). If they're all negative or all positive, there is no intersection. If some are positive and some negative, go to step B.

乙。项目中的端点到X轴，并检查段的影子相交多边形的影子。重复在y轴：

B. Project the endpoint onto the x axis, and check if the segment's shadow intersects the polygon's shadow. Repeat on the y axis:

如果（X1> XTR和x2> XTR），没有交点（线是矩形的右边）。 如果（X1＆LT; XBL和X2＆LT; XBL），无交集（线到左矩形）。 如果（Y1> YTR和Y2> YTR），没有交点（线以上的矩形）。 如果（Y1＆LT; YBL和Y2＆LT; YBL），没有交点（线低于矩形）。 否则，有一个交叉点。不要科恩 - 萨瑟兰或任何code中提到的其他答案你的问题。

If (x1 > xTR and x2 > xTR), no intersection (line is to right of rectangle). If (x1 < xBL and x2 < xBL), no intersection (line is to left of rectangle). If (y1 > yTR and y2 > yTR), no intersection (line is above rectangle). If (y1 < yBL and y2 < yBL), no intersection (line is below rectangle). else, there is an intersection. Do Cohen-Sutherland or whatever code was mentioned in the other answers to your question.

您可以，当然，首先做B，则A

You can, of course, do B first, then A.

阿莱霍