数学/算法/JS：如何确定两个矩形是否相交，给定每个矩形的左上角(x0, y0)和右下角(x1, y1)。

Question

我碰到了一个需要解决的数学问题，它是我完成应用程序所需的，所以我寻求帮助。

假设有2个（或更多，但基本上为2个）矩形，每个矩形有2个已知的点：左上角(x1, y1)和右下角(x2, y2) （如果需要解决问题，我可以用这些信息找出长度）。

TL(x1, y1)
   +-----------------+
   |                 |
   |                 |       TL(x3, y3)
   |                 |            +---------------------------+
   +-----------------+            |                           |
               BR(x2, y2)         +---------------------------+
                                                         BR(x4, y4)

有没有一种方法可以确定它们是否有交集，在区域中，我的意思是，如果任何一个矩形的任何部分位于另一个矩形的任何部分上？

我已经搜索并找到了一点帮助，但它并没有解决问题：

这两个矩形不相交的条件有4个：

1. 一个矩形的左边缘在另一个矩形的右边缘的右侧，意味着第一个矩形完全位于第二个矩形的右侧，没有交集。 2. 一个矩形的右边缘在另一个矩形的左边缘的左侧，意味着第一个矩形完全位于第二个矩形的左侧，没有交集。 3. 一个矩形的顶部边缘在另一个矩形的底部边缘下面，意味着第一个矩形完全位于第二个矩形的下方，没有交集。 4. 一个矩形的底部边缘在另一个矩形的顶部边缘之上，意味着第一个矩形完全位于第二个矩形的上方，没有交集。

所以我尝试反转条件，即如果上述四个条件中的4个不发生，矩形可能相交。但是我仍然可以找到两个矩形不满足任何条件的情况（如上图），并且仍然不相交。

非常感谢任何帮助，请向我展示它的方式或算法或代码（仅限JS和PHP）。

非常感谢！ [x]

- xx3004

---

该图表满足条件2。 - Ignacio Vazquez-Abrams

这看起来正是你需要的：https://dev59.com/kXVD5IYBdhLWcg3wBWzd - nickb

@IgnacioVazquez-Abrams：谢谢，现在我注意到了。 - xx3004

@nickb：我读了那篇文章，但真的不知道它在讲什么 >.<! - xx3004

@nnnnnn：我的错，非常感谢你，现在我知道我可以将那个理论应用到我的代码中。再次感谢你。[x] - xx3004

不是“可能”相交，而是“必须”相交。假设你将一个矩形完全包含在另一个矩形内也算作相交，如果这些条件都没有被满足，那么这些矩形必须相交。（编辑：抱歉，我删除了我的原始评论以便更改它，没有意识到在我的评论之后还有更多的评论留下来了。） - nnnnnn

Answer 1

检测任意数量矩形的相交("重叠")算法可以按以下方式工作。使用两个数据结构。

• 一个排序列表S，其中包含矩形左右边缘的x坐标。
• interval tree T，其中包含矩形底部/顶部的y坐标组成的区间。

算法在排序列表S的x坐标上扫描：

1. 如果当前x坐标是矩形R的左边缘，则将其y坐标[y1，y2]与区间树T进行比较。如果找到重叠，则算法停止并报告OVERLAP。如果在树T中没有重叠，则将区间[y1，y2]插入树中。

2. 如果当前x坐标是矩形R的右边缘，则从区间树T中删除其y区间[y1，y2]。

3. 如果完全处理了排序列表S，则没有重叠。算法停止并报告NO-OVERLAP。

对于N个矩形，时间复杂度为O(N*log(N))， 因为对于每个2*N的x坐标，都要在区间树中搜索N个区间。 辅助数据结构S和T的空间复杂度为O(N)。

- Jiri Kriz

Answer 2

这是我对这个问题的看法。如果有改进的地方，请告诉我。我自己做的例子似乎与这段代码相符，但是如果你能给我一些使其失败的坐标示例，我仍然想解决这个问题 :)

 <?php

//declare the points for your rectangles
//'UL' means upper left points, and 'LR' means the lower right points
$rectangle_array = array(
    $R1 = array("UL" => 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++) {
        //for each rectangle, compare points to every following rectangle
        $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']) {
                //rectangles cross on x-axis
                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'])) {
                    //rectangles intersect
                    return true;
                }
            }
        }
    }
    return false;
}

?>

- donutdan4114

---

我可以建议您将变量重命名，以更好地指示哪个点属于哪个矩形的哪个角落？例如，$r1TL（矩形1左上角），$r1BR，$r2TL，$r2BR。我知道问题中使用了$x1等，但那很令人困惑。 - nnnnnn