如何测试二维坐标系中线段是否与轴对齐的矩形相交？该线段由其两个端点p1和p2定义。该矩形由左上角和右下角点定义。
12个回答
64
原帖想要检测线段和多边形之间的交点。如果存在交点，则无需定位交点，如果您是这个意思，您可以做比Liang-Barsky或Cohen-Sutherland更少的工作：
线段端点为p1 =（x1 y1）和p2 =（x2 y2）。让矩形的角落为（xBL yBL）和（xTR yTR）。
然后你只需要
A. 检查矩形的所有四个角是否在线的同一侧。
通过p1和p2定义的线的隐式方程是:
F（xy）=（y2-y1）* x +（x1-x2）* y +（x2 * y1-x1 * y2）
如果F（xy）= 0，则（xy）在直线上。
如果F（xy）> 0，则（xy）在“上面”线上。
如果F（xy）<0，则（xy）在“下面”线上。
将所有四个角代入F（xy）。 如果它们都为负或都为正，则没有交集。 如果有些是正的，有些是负的，请转到步骤B。
B. 投影端点到x轴上，并检查线段的投影是否与多边形的投影相交。 在y轴上重复：
如果（x1> xTR并且x2> xTR），则没有交集（线在矩形右侧）。
如果（x1 yTR并且y2> yTR），则没有交集（线在矩形上方）。
如果（y1
- user37968
8
1另一种快捷的方法是按照以下顺序通过矩形：F（左上角），F（右上角），F（右下角），F（左下角），然后检查任何这些方程式符号是否与前一个不同，这意味着一个点在线的“下方”，而下一个点在“上方”。 - noio
1讲解得非常清楚，并且似乎处理了部分完全被包围在盒子内的情况。 - Paul Chernoch
我在上面的那行有 F(x, y) < 0。虽然对算法来说并没有什么影响。 - Druckles
为什么步骤B是必要的？我想不出有哪种情况下，某些角落在线的两侧，而该线又不与矩形相交。 - jnovacho
1@jnovacho，我猜是因为它不是一条线，而是一个有端点的线段。即使线穿过线段，线段也可能没有交点。 - RubenLaguna
显示剩余3条评论
29
我写了一个相当简单且有效的解决方案:
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;
}
- metamal
7
4这非常简单且效果很好！我做了一个 JavaScript 测试：http://jsfiddle.net/77eej/2/ - urraka
顺便问一下，有人能指出为什么要用
abs（dx）> 0.0000001而不是零吗？ - urraka1由于浮点数运算不精确，两个在数学上应该相等的数字可能会有微小的差异，导致相等比较失败。 - Minthos
1在某些情况下无法正常工作，请在框[0,0 100,100]上尝试使用点[25,125]和[101,100]，并查看它是否返回true。但是该线段明显在外部。 - Palax
我知道这很老了，有人能解释一下为什么要使用斜率来查找minY maxY，然后再重新排序并稍后查找真正的minY、maxY吗？ - Vinh
显示剩余2条评论
9
如果您的矩形是对齐的，Liang-Barsky可能是一个不错的解决方案。如果速度很重要，它比Cohen-Sutherland更快。
- ryan_s
7
您可以将该线段创建成一个矩形，并测试另一个矩形是否与之相碰撞，因为这只是一系列的比较操作。从pygame源代码中可以看到：
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
- asolano
1
4这个方法过于简单且过于迫切。它会收集到错误的结果，即线的起点在 x 轴上有重叠但在 y 轴上没有重叠，而线的终点在 y 轴上有重叠但在 x 轴上没有重叠（或者反之亦然）。 - Synesso
5
使用Cohen-Sutherland算法。该算法用于剪辑，但可以稍微调整以适应此任务。它将2D空间分成井字棋板，以您的矩形作为“中心方块”。然后，它检查您线条的两个点位于哪九个区域之一。
- 如果两个点都在左侧、右侧、顶部或底部，则可以轻松地拒绝。
- 如果任一点在内部，则可以轻松接受。
- 在罕见的剩余情况下，您可以进行计算，与矩形可能相交的边相交，根据它们所处的区域确定。
- Kevin Conner
3
或者直接使用/复制Java方法中已有的代码。
java.awt.geom.Rectangle2D.intersectsLine(double x1, double y1, double x2, double y2)
为了方便，这里是被转换成静态方法后的方法：
/**
* 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;
}
}
- Craigo
1
这是@metamal答案的JavaScript版本。
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
}
- Breck
0
我做了一个简单的餐巾纸解决方案...
接下来找到m和c，从而得出方程y = mx + c
y = (Point2.Y - Point1.Y) / (Point2.X - Point1.X)
用P1坐标替换以找到c
对于矩形顶点，将X值放入直线方程中，得到Y值，并查看Y值是否位于下面所示的矩形边界内
(您可以找到矩形的常数值X1、X2、Y1、Y2)
X1 <= x <= X2 &
Y1 <= y <= Y2
如果Y值满足上述条件并且位于（Point1.Y，Point2.Y）之间，则存在交点。如果这个点无法通过测试，请尝试每个顶点。
- Gishu
0
我在研究一个类似的问题，这是我的解决方案。我首先比较了边缘并意识到了一些事情。如果一个边缘的中点落在第一个框的相反轴上，并且在同一轴上第一个框外部点的半长内，那么该侧的某个位置就会有交叉点。但这只是一维思考，并需要查看第二个框的每条边。
突然间我意识到，如果您找到第二个框的“中点”，并比较中点的坐标是否落在第一个框的外部尺寸的1/2长度之内，则肯定有交集出现在某处。
突然间我意识到，如果您找到第二个框的“中点”，并比较中点的坐标是否落在第一个框的外部尺寸的1/2长度之内，则肯定有交集出现在某处。
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的中点是否在box2的外部尺寸的1/2长度内）
甚至更简化-将中点移动半个长度，它就与该框的原点相同。这意味着您现在可以仅检查该点是否落在您的边界范围内，并通过将平面向上和向左移动，使下角现在成为第一个框的下角。计算量大大减少：
(x1 - w2) < a1 < x2
&&
(y1 - h2) < b1 < y2
[overlap exists]
或者不被替换的：
( (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]
- Scott
1
问题是关于线段和矩形的相交，而不是矩形和矩形的相交。 - NateS
0
PHP编程示例（我使用了一个对象模型，其中包含了getLeft()、getRight()、getTop()、getBottom()等方法来获取多边形的外部坐标，还有getWidth()和getHeight()方法——根据输入的参数，它会计算并缓存未知数，例如我可以用x1、y1和...w、h或者x2、y2创建一个多边形，然后它就可以计算出其他值）
我使用“n”来表示正在检查重叠的“新”项（$nItem是我的多边形对象的实例），要测试的项（这是一个bin/sort背包程序）在一个数组中，该数组由更多相同的多边形对象实例组成。
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;
}
- Scott
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接