数学/算法/JS: 如何确定两个矩形是否相交，给定每个矩形的左上角(x0, y0)和右下角(x1, y1)
数学/算法/JS: 如何确定两个矩形是否相交，给定每个矩形的左上角(x0, y0)和右下角(x1, y1)
我遇到了一个需要完成我的申请的数学问题，所以我在这里寻求帮助。
给定2个（或更多，但基本上是2个）矩形，每个矩形都有2个已知的点：左上角（x1，y1）和右下角（x2，y2）（如果需要解决问题，我可以用这些信息找到长度）。
左上角（x1，y1）
+-----------------+
| |
| | 左上角（x3，y3）
| | +---------------------------+
+-----------------+ | |
右下角（x2，y2） +---------------------------+
右下角（x4，y4）
有没有办法确定它们是否有交集，即是否有任何一个矩形的一部分位于另一个矩形的一部分上？
我搜索了一下，找到了一点帮助，但它没有解决问题：
有四个条件下两个矩形不会相交：
- 一个矩形的左边缘位于另一个矩形的右边缘的右侧，这意味着第一个矩形完全位于第二个矩形的右侧，没有交集。
- 一个矩形的右边缘位于另一个矩形的左边缘的左侧，这意味着第一个矩形完全位于第二个矩形的左侧，没有交集。
- 一个矩形的上边缘位于另一个矩形的下边缘的下方，这意味着第一个矩形完全位于第二个矩形的下方，没有交集。
- 一个矩形的下边缘位于另一个矩形的上边缘的上方，这意味着第一个矩形完全位于第二个矩形的上方，没有交集。
所以我尝试反转这些条件，即如果上述4个条件都不满足，则矩形可能相交。但我仍然找不到满足任何条件但不相交的条件（如上面的图片）。
非常感谢任何帮助，请告诉我如何做或算法或代码（仅限JS和PHP）。
非常感谢！
[x]
这是我关于这个问题的一点建议。如果有改进的地方，请告诉我。我自己做的例子似乎与这段代码一致，但如果你能给我一个使它失效的坐标示例，我仍然希望解决这个问题 🙂
array("x" => 10, "y" => 20), "LR" => array("x" => 22, "y" => 5)),
$R2 = array("UL" => array("x" => 32, "y" => 44), "LR" => array("x" => 65, "y" => 20)),
$R3 = array("UL" => array("x" => 20, "y" => 16), "LR" => array("x" => 25, "y" => 10))
);
if (rectIntersect($rectangle_array)) {
echo "THEY INTERSECT";
} else {
echo "NO INTERSECTION";
}
function rectIntersect($rectangles) {
$num_rectangles = count($rectangles);
for ($i = 0; $i < $num_rectangles; $i++) {
//对于每个矩形，将其顶点与后面的每个矩形进行比较
$R1 = $rectangles[$i];
for ($k = $i; $k < ($num_rectangles - $i); $k++) {
$R2 = $rectangles[$k + 1];
if ($R1['LR']['x'] > $R2['UL']['x'] && $R1['UL']['x'] < $R2['LR']['x']) {
//矩形在x轴上交叉
if (($R1['LR']['y'] < $R2['UL']['y'] && $R1['UR']['y'] < $R2['LR']['y']) ||
($R1['UL']['y'] > $R2['LR']['y'] && $R1['LR']['y'] < $R2['UL']['y'])) {
//矩形相交
return true;
}
}
}
}
return false;
}
?>
我建议将变量重新命名，以更好地指示哪个点属于哪个矩形的哪个角落。例如，$r1TL（矩形1的左上角），$r1BR，$r2TL，$r2BR。我知道问题中使用了$x1等变量，但那样很令人困惑。
给定每个矩形的左上角（x0，y0）和右下角（x1，y1），如何确定2个或更多矩形是否相交？
这个问题的出现是因为我们需要判断给定的多个矩形是否存在相交的情况。为了解决这个问题，可以使用以下算法：
1. 创建两个数据结构：排序列表S，用于存储矩形的左右边缘的x坐标；区间树T，用于存储矩形的底部和顶部的y坐标。
2. 算法对排序列表S中的x坐标进行扫描：
a. 如果当前x坐标是矩形R的左边缘，则将矩形R的y坐标[y1，y2]与区间树T进行比较。如果存在重叠，则算法停止并报告“重叠”。如果树T中不存在重叠，则将区间[y1，y2]插入到树中。
b. 如果当前x坐标是矩形R的右边缘，则从区间树T中删除其y区间[y1，y2]。
c. 如果排序列表S被完全处理，则表示没有重叠。算法停止并报告“无重叠”。
该算法的时间复杂度为O(N*log(N))，其中N表示矩形的数量，因为对于每个2*N个x坐标，需要在区间树中搜索N个区间。辅助数据结构S和T的空间复杂度为O(N)。