如何测试线段是否与二维中的轴对齐矩形相交？该段由其两端定义：p1，p2。矩形由左上角和右下角点定义。
metamal
问问题
39678 次
12 回答
61
最初的海报想要检测线段和多边形之间的交点。没有必要找到交叉口，如果有的话。如果这就是你的意思，你可以做的工作比 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 < xBL 和 x2 < xBL)，则没有交点（直线在矩形的左侧）。
如果（y1 > yTR 和 y2 > yTR），则没有交点（直线在矩形上方）。
如果（y1 < yBL 和 y2 < yBL），则没有交点（直线在矩形下方）。
否则，有一个交叉点。做 Cohen-Sutherland 或您问题的其他答案中提到的任何代码。
当然，你可以先做 B，然后做 A。
阿莱霍
于 2008-11-15T21:07:35.647 回答
27
写了非常简单且有效的解决方案：
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;
}
于 2008-09-19T07:07:52.417 回答
9
由于您的矩形是对齐的，Liang-Barsky 可能是一个很好的解决方案。如果这里的速度很重要，它比 Cohen-Sutherland 快。
于 2008-09-19T03:51:35.290 回答
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
于 2012-12-12T16:57:45.013 回答
5
它用于剪辑，但可以针对此任务进行微调。它将 2D 空间划分为一个井字棋盘，以您的矩形为“中心正方形”。
然后它会检查您的线的两个点中的每一个都在九个区域中的哪个区域。
- 如果两个点都是左、右、上或下，你会轻易拒绝。
- 如果任何一点在里面，你都会接受。
- 在极少数情况下，您可以根据矩形所在的区域进行数学运算，以与矩形的任何可能相交的边相交。
于 2008-09-19T03:42:10.523 回答
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;
}
}
于 2011-03-22T04:50:23.920 回答
1
于 2008-09-19T03:45:09.410 回答
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
}
于 2013-08-04T19:20:16.663 回答
0
PHP中的编码示例（我正在使用一个对象模型，该模型具有诸如getLeft（），getRight（），getTop（），getBottom（）之类的方法来获取多边形的外部坐标，并且还具有getWidth（）和getHeight () - 根据输入的参数，它会计算并缓存未知数 - 即我可以用 x1,y1 和 ... w,h 或 x2,y2 创建一个多边形，它可以计算其他的）
我使用“n”来指定正在检查重叠的“新”项目（$nItem 是我的多边形对象的一个实例）-要再次测试的项目 [这是一个 bin/sort knapsack 程序] 在一个由以下组成的数组中（相同）多边形对象的更多实例。
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;
}
于 2012-07-26T19:12:33.790 回答
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) 之间 - 我们有一个交集。如果这一个未能进行切割，请尝试每个顶点。
于 2008-09-19T04:11:53.213 回答
0
我的解决方案的一些示例代码（在 php 中）：
// 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;
}
于 2012-07-27T15:49:59.190 回答
0
我正在研究一个类似的问题，这就是我想出的。我首先比较了边缘并意识到了一些事情。如果落在第一个框的相对轴内的边的中点在同一轴上第一个框的外部点的该边长度的一半之内，则该边在某处存在交点。但这是一维思考，需要查看第二个盒子的每一侧才能弄清楚。
我突然想到，如果你找到第二个盒子的“中点”并比较中点的坐标，看看它们是否落在第一个盒子外部尺寸的边（第二个盒子）的 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 <=
当然，您也可以轻松地进行比较（检查框 1 的中点是否在框 2 外部尺寸的 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]
于 2012-07-26T18:10:40.550 回答