如何测试线段是否与2D中轴对齐的矩形相交？
如何测试线段是否与2D中轴对齐的矩形相交？线段使用其两端进行定义: p1和p2。矩形是用左上点和右下点定义的。
回答 12
Stack Overflow用户
发布于 2008-11-15 21:07:36
最初的发帖者希望检测线段和多边形之间的交点。没有必要定位交叉口，如果有的话。如果这是你的意思，你可以做比梁-巴斯基或科恩-萨瑟兰更少的工作：
假设线束段端点为p1=(x1 y1)和p2=(x2 y2)。
将矩形的角点设置为(xBL yBL)和(xTR yTR)。
那么你所要做的就是
检查矩形的所有四个角是否都在直线的同一侧。通过p1和p2的直线的隐式方程为：
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) < 0，则(x，y)“低于”线。
将所有四个角替换为F(x，y)。如果它们都是负的或都是正的，那么就没有交集。如果有些是正的，有些是负的，则转到步骤B。
B.将端点投影到x轴上，并检查线段的阴影是否与多边形的阴影相交。在y轴上重复：
如果(x1 > xTR和x2 > xTR)，则没有交集(直线位于矩形的右侧)。
如果(x1 < xBL和x2 < xBL)，则没有交集(直线在矩形的左侧)。
如果(y1 > yTR和y2 > yTR)，则没有交集(直线位于矩形之上)。
如果(y1 < yBL和y2 < yBL)，则没有交集(直线在矩形下)。
否则，会有一个交叉口。做Cohen-Sutherland或其他问题答案中提到的任何代码。
当然，您可以先做B，然后做A。
Alejo
Stack Overflow用户
发布于 2008-09-19 07:07:52
写了一个非常简单有效的解决方案：
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;
}Stack Overflow用户
发布于 2008-09-19 03:51:35
由于您的矩形是对齐的，因此梁-Barsky可能是一个很好的解决方案。如果速度在这里很重要，它比Cohen-Sutherland更快。
Siggraph explanation
Another good description
And of course, Wikipedia
https://stackoverflow.com/questions/99353
复制相似问题
腾讯云开发者
