圆和矩形是否有重叠

标签: 几何 数学

难度: Medium

给你一个以 (radius, xCenter, yCenter) 表示的圆和一个与坐标轴平行的矩形 (x1, y1, x2, y2) ，其中 (x1, y1) 是矩形左下角的坐标，而 (x2, y2) 是右上角的坐标。

如果圆和矩形有重叠的部分，请你返回 true ，否则返回 false 。

换句话说，请你检测是否 存在 点 (xi, yi) ，它既在圆上也在矩形上（两者都包括点落在边界上的情况）。

示例 1 ：

输入：radius = 1, xCenter = 0, yCenter = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
输出：true
解释：圆和矩形存在公共点 (1,0) 。

示例 2 ：

输入：radius = 1, xCenter = 1, yCenter = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1
输出：false

示例 3 ：

输入：radius = 1, xCenter = 0, yCenter = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1
输出：true

提示：

  • 1 <= radius <= 2000
  • -104 <= xCenter, yCenter <= 104
  • -104 <= x1 < x2 <= 104
  • -104 <= y1 < y2 <= 104

Submission

运行时间: 25 ms

内存: 16.0 MB

class Solution:
    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:
        if xCenter < x1 and x1 - xCenter > radius:
            return False
        if xCenter > x2 and xCenter - x2 > radius:
            return False
        if yCenter < y1 and y1 - yCenter > radius:
            return False
        if yCenter > y2 and yCenter - y2 > radius:
            return False
        if xCenter < x1 and yCenter < y1:
            return (x1 - xCenter) ** 2 + (y1 - yCenter) ** 2 <= radius ** 2
        if xCenter < x1 and yCenter > y2:
            return (x1 - xCenter) ** 2 + (y2 - yCenter) ** 2 <= radius ** 2
        if xCenter > x2 and yCenter < y1:
            return (x2 - xCenter) ** 2 + (y1 - yCenter) ** 2 <= radius ** 2
        if xCenter > x2 and yCenter > y2:
            return (x2 - xCenter) ** 2 + (y2 - yCenter) ** 2 <= radius ** 2
        return True

Explain

此题解首先检查圆心是否在矩形外部的某个方向上距离过远，足以使圆完全不与矩形重叠。若圆心在矩形的左侧、右侧、下侧或上侧，且与矩形的距离超过半径，则直接返回False。如果圆心与矩形的某个角的距离在x或y方向超过半径，也会返回False。接着，代码检查圆心是否在矩形的四个角的外侧，如果是，则需要计算圆心到最近角的距离，看其是否小于等于半径的平方，若是，则圆至少与矩形的角接触。如果以上情况都不满足，即圆心在矩形内部或边界上，则返回True，表示圆和矩形重叠。

时间复杂度: O(1)

空间复杂度: O(1)

class Solution:
    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:
        # 检查圆心是否在矩形左侧且距离矩形左边界超过半径
        if xCenter < x1 and x1 - xCenter > radius:
            return False
        # 检查圆心是否在矩形右侧且距离矩形右边界超过半径
        if xCenter > x2 and xCenter - x2 > radius:
            return False
        # 检查圆心是否在矩形下侧且距离矩形下边界超过半径
        if yCenter < y1 and y1 - yCenter > radius:
            return False
        # 检查圆心是否在矩形上侧且距离矩形上边界超过半径
        if yCenter > y2 and yCenter - y2 > radius:
            return False
        # 圆心在矩形左下角外侧
        if xCenter < x1 and yCenter < y1:
            return (x1 - xCenter) ** 2 + (y1 - yCenter) ** 2 <= radius ** 2
        # 圆心在矩形左上角外侧
        if xCenter < x1 and yCenter > y2:
            return (x1 - xCenter) ** 2 + (y2 - yCenter) ** 2 <= radius ** 2
        # 圆心在矩形右下角外侧
        if xCenter > x2 and yCenter < y1:
            return (x2 - xCenter) ** 2 + (y1 - yCenter) ** 2 <= radius ** 2
        # 圆心在矩形右上角外侧
        if xCenter > x2 and yCenter > y2:
            return (x2 - xCenter) ** 2 + (y2 - yCenter) ** 2 <= radius ** 2
        # 其他情况，圆心在矩形内
        return True

Explore

在计算机科学中，计算平方距离比计算欧几里得距离（即包含平方根操作）更为高效，因为平方根计算通常是一个计算密集型的操作。由于比较平方值和直接比较距离在数学上是等效的，只要保证比较双方都是平方值，使用平方距离可以避免不必要的计算，同时保持正确性和精确性。

当`(x1 - xCenter) > radius`时，表示圆心到矩形边界的距离大于圆的半径，因此圆与矩形不重叠。如果使用`(x1 - xCenter) >= radius`，那么当圆心到矩形边界的距离正好等于半径时，圆仍然会与矩形的边界接触，此时应该认为圆与矩形有重叠。因此，使用`>`可以更准确地判断圆与矩形的非重叠情况。

如果圆心正好在矩形的边上，根据上述算法，这将被视为圆与矩形重叠的一种情况。算法最后检查是否有其他情况导致圆心与矩形的关系被认为是重叠。只要圆心与矩形边界的距离不超过圆的半径，圆就至少与矩形的边缘接触，从而产生重叠。

是的，算法考虑了圆完全在矩形内部但不接触边界的情况，并会返回正确的结果。如果圆的所有检查都未能证明圆与矩形不重叠（即圆心不在矩形的外部、圆心到矩形角的距离不超过半径以及其他边界情况），最后的返回值是True。这意味着无论圆是否接触边界，只要它在矩形内部，就认为它们重叠。