关于图形：如何测试线段是否与2D中的轴对齐矩形相交？

How to test if a line segment intersects an axis-aligned rectange in 2D?

如何在2D中测试线段是否与轴对齐的矩形相交？段的两端定义为：p1，p2。矩形由左上角和右下角定义。

原始海报想要检测线段和多边形之间的交点。如果有交叉点，则无需定位。如果这就是您的意思，那么您可以做的工作比Liang-Barsky或Cohen-Sutherland少：

令段端点为p1 =(x1 y1)和p2 =(x2 y2)。

令矩形的角为(xBL yBL)和(xTR yTR)。

那你要做的就是

A.检查矩形的所有四个角是否在直线的同一侧。
通过p1和p2的直线的隐式方程为：

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

如果F(x y)= 0，则(x y)为ON。

如果F(x y)> 0，则(x y)在该行"上方"。

如果F(x y)<0，则(x y)在该行"下方"。

将所有四个角代入F(x y)。如果它们全部为负或全部为正，则没有交集。如果有些是肯定的而有些是消极的，请转到步骤B。

B.将端点投影到x轴上，并检查线段的阴影是否与多边形的阴影相交。在y轴上重复：

如果(x1> xTR和x2> xTR)，则无交集(直线在矩形的右边)。

如果(x1 yTR且y2> yTR)，则无交集(直线在矩形上方)。

如果(y1

您当然可以先做B，然后再做A。

阿列霍

编写了非常简单有效的解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

bool SegmentIntersectRectangle(double a_rectangleMinX,
double a_rectangleMinY,
double a_rectangleMaxX,
double a_rectangleMaxY,
double a_p1x,
double a_p1y,
double a_p2x,
double a_p2y)
{
// Find min and max X for the segment

double minX = a_p1x;
double maxX = a_p2x;

if(a_p1x > a_p2x)
{
minX = a_p2x;
maxX = a_p1x;
}

// Find the intersection of the segment's and rectangle's x-projections

if(maxX > a_rectangleMaxX)
{
maxX = a_rectangleMaxX;
}

if(minX < a_rectangleMinX)
{
minX = a_rectangleMinX;
}

if(minX > maxX) // If their projections do not intersect return false
{
return false;
}

// Find corresponding min and max Y for min and max X we found before

double minY = a_p1y;
double maxY = a_p2y;

double dx = a_p2x - a_p1x;

if(Math::Abs(dx) > 0.0000001)
{
double a = (a_p2y - a_p1y) / dx;
double b = a_p1y - a * a_p1x;
minY = a * minX + b;
maxY = a * maxX + b;
}

if(minY > maxY)
{
double tmp = maxY;
maxY = minY;
minY = tmp;
}

// Find the intersection of the segment's and rectangle's y-projections

if(maxY > a_rectangleMaxY)
{
maxY = a_rectangleMaxY;
}

if(minY < a_rectangleMinY)
{
minY = a_rectangleMinY;
}

if(minY > maxY) // If Y-projections do not intersect return false
{
return false;
}

return true;
}

由于矩形是对齐的，因此Liang-Barsky可能是一个很好的解决方案。如果此处的速度显着，则它比Cohen-Sutherland快。

信号图说明
另一个很好的描述
当然，维基百科

您也可以在线段之外创建一个矩形，并测试其他矩形是否与之碰撞，因为这只是一系列比较。从pygame来源：

1
2
3

def _rect_collide(a, b):
return a.x + a.w > b.x and b.x + b.w > a.x and \\
a.y + a.h > b.y and b.y + b.h > a.y

使用Cohen-Sutherland算法。

它用于剪辑，但可以略微调整此任务。它将2D空间划分为一个井字形棋盘，以您的矩形作为"中心正方形"。
然后检查线的两个点分别在九个区域中的哪个区域。

如果两个点都在左，右，上或下，您将微不足道。
如果其中任一点在里面，您都会微不足道地接受。
在极少数情况下，您可以根据矩形所在的区域进行数学运算，以使其与矩形的任意可能相交。

或者只是使用/复制Java方法中已经存在的代码

1	java.awt.geom.Rectangle2D.intersectsLine(double x1, double y1, double x2, double y2)

为方便起见，这是转换为静态后的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

/**
* Code copied from {@link java.awt.geom.Rectangle2D#intersectsLine(double, double, double, double)}
*/
public class RectangleLineIntersectTest {
private static final int OUT_LEFT = 1;
private static final int OUT_TOP = 2;
private static final int OUT_RIGHT = 4;
private static final int OUT_BOTTOM = 8;

private static int outcode(double pX, double pY, double rectX, double rectY, double rectWidth, double rectHeight) {
int out = 0;
if (rectWidth <= 0) {
out |= OUT_LEFT | OUT_RIGHT;
} else if (pX < rectX) {
out |= OUT_LEFT;
} else if (pX > rectX + rectWidth) {
out |= OUT_RIGHT;
}
if (rectHeight <= 0) {
out |= OUT_TOP | OUT_BOTTOM;
} else if (pY < rectY) {
out |= OUT_TOP;
} else if (pY > rectY + rectHeight) {
out |= OUT_BOTTOM;
}
return out;
}

public static boolean intersectsLine(double lineX1, double lineY1, double lineX2, double lineY2, double rectX, double rectY, double rectWidth, double rectHeight) {
int out1, out2;
if ((out2 = outcode(lineX2, lineY2, rectX, rectY, rectWidth, rectHeight)) == 0) {
return true;
}
while ((out1 = outcode(lineX1, lineY1, rectX, rectY, rectWidth, rectHeight)) != 0) {
if ((out1 & out2) != 0) {
return false;
}
if ((out1 & (OUT_LEFT | OUT_RIGHT)) != 0) {
double x = rectX;
if ((out1 & OUT_RIGHT) != 0) {
x += rectWidth;
}
lineY1 = lineY1 + (x - lineX1) * (lineY2 - lineY1) / (lineX2 - lineX1);
lineX1 = x;
} else {
double y = rectY;
if ((out1 & OUT_BOTTOM) != 0) {
y += rectHeight;
}
lineX1 = lineX1 + (y - lineY1) * (lineX2 - lineX1) / (lineY2 - lineY1);
lineY1 = y;
}
}
return true;
}
}

快速的Google搜索弹出带有C ++代码的页面，用于测试路口。

基本上，它测试线与每个边框或矩形之间的交点。

矩形和直线相交代码

这是@metamal答案的javascript版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

var isRectangleIntersectedByLine = function (
a_rectangleMinX,
a_rectangleMinY,
a_rectangleMaxX,
a_rectangleMaxY,
a_p1x,
a_p1y,
a_p2x,
a_p2y) {

// Find min and max X for the segment
var minX = a_p1x
var maxX = a_p2x

if (a_p1x > a_p2x) {
minX = a_p2x
maxX = a_p1x
}

// Find the intersection of the segment's and rectangle's x-projections
if (maxX > a_rectangleMaxX)
maxX = a_rectangleMaxX

if (minX < a_rectangleMinX)
minX = a_rectangleMinX

// If their projections do not intersect return false
if (minX > maxX)
return false

// Find corresponding min and max Y for min and max X we found before
var minY = a_p1y
var maxY = a_p2y

var dx = a_p2x - a_p1x

if (Math.abs(dx) > 0.0000001) {
var a = (a_p2y - a_p1y) / dx
var b = a_p1y - a * a_p1x
minY = a * minX + b
maxY = a * maxX + b
}

if (minY > maxY) {
var tmp = maxY
maxY = minY
minY = tmp
}

// Find the intersection of the segment's and rectangle's y-projections
if(maxY > a_rectangleMaxY)
maxY = a_rectangleMaxY

if (minY < a_rectangleMinY)
minY = a_rectangleMinY

// If Y-projections do not intersect return false
if(minY > maxY)
return false

return true
}

我的解决方案的一些示例代码(在php中)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// returns 'true' on overlap checking against an array of similar objects in $this->packed
public function checkForOverlaps(BinPack_Polygon $nItem) {
$nX = $nItem->getLeft();
$nY = $nItem->getTop();
$nW = $nItem->getWidth();
$nH = $nItem->getHeight();
// loop through the stored polygons checking for overlaps
foreach($this->packed as $_i => $pI) {
if(((($pI->getLeft() - $nW) < $nX) && ($nX < $pI->getRight())) && ((($pI->getTop() - $nH) < $nY) && ($nY < $pI->getBottom()))) {
return true;
}
}
return false;
}

PHP中的编码示例(我正在使用一个对象模型，该对象模型具有诸如getLeft()，getRight()，getTop()，getBottom()之类的方法，以获取多边形的外部坐标，并且还具有getWidth()和getHeight ()-根据输入的参数，它将计算并缓存未知数-即我可以使用x1，y1和... w，h或x2，y2创建多边形，并且可以计算其他多边形)

我使用'n'来指定要检查的'new'项是否重叠($ nItem是我的多边形对象的一个??实例)-要再次测试的项[这是bin / sort背包程序]位于由以下项组成的数组中(相同)多边形对象的更多实例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public function checkForOverlaps(BinPack_Polygon $nItem) {
// grab some local variables for the stuff re-used over and over in loop
$nX = $nItem->getLeft();
$nY = $nItem->getTop();
$nW = $nItem->getWidth();
$nH = $nItem->getHeight();
// loop through the stored polygons checking for overlaps
foreach($this->packed as $_i => $pI) {
if(((($pI->getLeft() - $nW) < $nX) && ($nX < $pI->getRight())) &&
((($pI->getTop() - $nH) < $nY) && ($nY < $pI->getBottom()))) {
return false;
}
}
return true;
}

我正在寻找一个类似的问题，这就是我的想法。我首先比较边缘并意识到一些东西。如果落在第一个框的相对轴之内的边的中点在同一轴上第一个框的外点的边的长度的一半以内，则该边在某处存在相交。
但这就是从尺寸上考虑1的问题，需要查看第二个盒子的每一侧才能弄清楚。

我突然想到，如果找到第二个框的"中点"并比较中点的坐标，看它们是否落在第一个框的外部尺寸(第二个框的边)的1/2长度之内，那么某处有一个交叉点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

i.e. box 1 is bounded by x1,y1 to x2,y2
box 2 is bounded by a1,b1 to a2,b2

the width and height of box 2 is:
w2 = a2 - a1 (half of that is w2/2)
h2 = b2 - b1 (half of that is h2/2)
the midpoints of box 2 are:
am = a1 + w2/2
bm = b1 + h2/2

So now you just check if
(x1 - w2/2) < am < (x2 + w2/2) and (y1 - h2/2) < bm < (y2 + h2/2)
then the two overlap somewhere.
If you want to check also for edges intersecting to count as 'overlap' then
change the < to <=

当然，您也可以轻松地进行另一种比较(将box1的中点检查为box 2的外部尺寸的1/2以内)

甚至更加简化-将中点偏移一半的长度，并且该中点与该盒子的原点相同。这意味着您现在可以只检查该点是否在边界范围内，并且通过将平原向左移动，则下角现在是第一个框的下角。数学要少得多：

1
2
3
4

(x1 - w2) < a1 < x2
&&
(y1 - h2) < b1 < y2
[overlap exists]

或未取代的：

1 2	( (x1-(a2-a1)) < a1 < x2 ) && ( (y1-(b2-b1)) < b1 < y2 ) [overlap exists] ( (x1-(a2-a1)) <= a1 <= x2 ) && ( (y1-(b2-b1)) <= b1 <= y2 ) [overlap or intersect exists]

我做了一点餐巾纸溶液。

接下来找到m和c，因此等式y = mx + c