看到LeetCode 1401这道题估计不少刷题的人第一反应和我一样圆和矩形重叠这不就是初中几何吗能算什么算法题但真上手之后才发现这题是典型的“看着简单做起来全是细节”的计算几何入门题考察的不只是你会不会用点到直线的距离公式而是你对空间关系、边界条件、坐标系统的理解够不够扎实。这道题的输入非常直白给你一个圆的圆心坐标和半径再给你一个轴对齐矩形Axis-Aligned Rectangle的左上角和右下角坐标判断两者是否有重叠。坐标范围给到了10^9量级这意味着任何想通过暴力枚举矩形边界上的点、逐点计算距离的思路在第一秒就该被否掉。真正核心的解法其实只有三行代码但为了这三行代码你需要把所有边界情况嚼碎吃透。这篇文章我会从题目拆解到数学原理再到代码实现和常见坑点完整还原我自己做这道题的全过程。无论你是准备面试、刷周赛还是打算把计算几何的知识点系统过一遍这篇都能给你一些参考。1. 题目理解与核心思路拆解1.1 面积重叠的判定本质是什么先明确一下“重叠”的定义。在LeetCode的语境里圆和矩形有重叠指的是两个图形存在至少一个公共点。这个定义包含了三种情况一是矩形完全在圆内圆心在矩形内部且矩形所有顶点都在圆内二是圆完全在矩形内部圆心在矩形内部且圆的边界没有超出矩形三是两者边界相交也就是圆和矩形的某条边有交点或者某个顶点刚好落在圆周上。值得注意的是相切也算重叠。因为相切意味着边界上存在一个公共点这个点在数学上同时属于两个图形。很多人在做这道题的时候把判断条件写成了严格小于半径的比较导致相切的测试用例直接挂掉。那为什么不用“圆心到矩形四边的距离小于半径”来判断这个思路乍一听很合理圆和矩形有重叠不就是圆碰到矩形四条边中的任何一条吗但问题在于圆心到边的距离只适用于圆心在矩形外侧、且垂足落在线段上的情况。当圆心在矩形的四个角附近时距离圆最近的点根本不是边上的垂足而是矩形的顶点。这恰恰是这道题最容易踩的坑。1.2 为什么不建议暴力扫描边界点坐标范围是10^9如果沿着矩形四条边每隔0.01个单位扫一个点一轮下来需要扫描4乘10^11个点这在任何语言里都是灾难级别的计算量。即使你把步长放宽到0.1个单位扫描量依然在10^10以上。更关键的是这个思路在数学上就是不成立的。扫描是离散的采样过程永远存在漏掉真实相交点的可能。哪怕你的采样精度足够高也会因为浮点误差产生误判。对于这种几何判定问题正确的姿势是找到精确的数学表达而不是用数值方法去逼近。1.3 核心思路找矩形上离圆心最近的那个点如果你在纸上画几个不同位置的圆和矩形多画几次就会发现一个朴素的事实圆和矩形是否重叠取决于矩形上距离圆心最近的那个点与圆心的距离。如果这个最近距离小于等于半径那就必然有重叠如果大于半径那整个矩形都在圆的外部必然没有重叠。这个思路把“面与面的重叠”转化成了“点到面的最近距离”把二维的空间关系判定降维成了一个单点计算。严格来说这其实是计算几何里“点到凸多边形距离”的一种特例。矩形是凸多边形所以矩形上离给定点最近的点必然是唯一的而且可以通过简单的坐标夹逼clamp计算出来。2. 数学原理clamp与最近点计算2.1 clamp操作到底在干什么“矩形上离圆心最近的点”实现起来可以抽象成一句话把圆心坐标分别限制clamp到矩形在x轴和y轴的取值范围内。先说x方向。假设矩形的左边界是x1右边界是x2那么圆心横坐标xCenter落在这个区间内时最近点的横坐标就是xCenter本身如果xCenter在区间左边最近点的横坐标就是x1如果在区间右边就是x2。用代码表达就是closestX max(x1, min(xCenter, x2))同理y方向也做同样的操作。这里有个细节容易搞错LeetCode给的矩形坐标是左上角(x1, y1)和右下角(x2, y2)也就是y1大于y2y轴的合法范围其实是[y2, y1]。所以closestY max(y2, min(yCenter, y1))得到(closestX, closestY)之后这个点一定在矩形上而且它到圆心的距离一定是最小的。然后计算距离的平方和半径的平方比较大小就能得出最终结论。2.2 三种区域的分类讨论把矩形画在坐标系里矩形本身可以向外扩展成九个区域。圆心落在不同区域clamp的结果也完全不同。圆心在矩形内部时clamp之后得到的点就是圆心自身距离为0直接判重叠。圆心在矩形正上方或正下方、但横坐标在矩形范围内时最近点是圆心的垂直投影点距离就是圆心到那条边的垂直距离。圆心在矩形四个角所在的角区域时最近点是距离圆心最近的矩形顶点距离公式退化成了点到点的距离公式。这正好对应了数学里的分类讨论思路按圆心相对矩形的位置把问题分成内部、边上、角上三类。clamp用一行代码就把这三个分支全部合并了这是这个解法最漂亮的地方。2.3 为什么可以推广到三维的球体与盒子这个思路其实不止适用于二维。把矩形推广到三维就是判断球体和一个轴对齐的立方体盒子是否有交叠同样的clamp逻辑可以直接照搬——把球心坐标分别夹逼到盒子在x、y、z三个方向的范围得到盒子上离球心最近的点然后比较距离和半径。我在做游戏开发相关练习时经常用到这个思路。碰撞检测里包围盒和包围球是两种最基础的碰撞体而判断两者相交的算法恰好就是这道题的推广。所以别看LeetCode 1401只是个中等难度的几何题背后的思想在很多实际工程场景里都能直接复用。3. 代码实现与边界处理3.1 一份可以直接用的Python实现class Solution: def checkOverlap( self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int ) - bool: closest_x max(x1, min(xCenter, x2)) closest_y max(y2, min(yCenter, y1)) dx xCenter - closest_x dy yCenter - closest_y return dx * dx dy * dy radius * radius这份代码通过比较距离的平方和半径的平方完全避免了一次开根号的浮点运算。坐标范围最大到10^9平方之后是10^18还在Python整数类型的舒适区里完全不用担心溢出。这也是我坚持用dx * dx dy * dy而不是math.sqrt的原因。3.2 坐标顺序与变量命名陷阱LeetCode这道题的参数顺序是x1, y1, x2, y2其中(x1, y1)是左上角(x2, y2)是右下角。这意味着y1 y2。我第一遍写的时候想当然地把坐标范围当成了[y1, y2]结果用题目给的示例一跑就发现方向反了。这个错误在语法上完全看不出来因为编译器不会报错代码逻辑也符合Python的语法规则但计算结果就是错的。我的建议是把参数在函数开头先整理一遍统一成比较直观的方向降低心智负担left, right x1, x2 top, bottom y1, y2当然也可以不整理直接在clamp的时候用max(y2, min(yCenter, y1))。但无论用哪种方式心里要时刻清楚矩形y轴的合法区间是[y2, y1]不是[y1, y2]。3.3 边界条件对照速查表我自己做这道题时整理了一个边界测试表格把各种特殊情况都过了一遍场景描述圆心与矩形关系预期输出圆心在矩形内部(0,0)矩形[-1,1]x[-1,1]true圆心在矩形正上方距离大于半径(0,5)r1矩形[-1,1]x[-1,1]false圆心在矩形正上方距离小于半径(0,1.5)r2矩形[-1,1]x[-1,1]true圆心恰好和矩形边相切(0,2)r1矩形[-1,1]x[-1,1]true圆心在矩形左上角区域距离等于顶点距离(-2,2)r1矩形[-1,1]x[-1,1]true圆心在矩形左上角区域距离大于顶点距离(-2.5,2.5)r1矩形[-1,1]x[-1,1]false矩形完全包含圆(0,0)r1矩形[-10,10]x[-10,10]true矩形和圆完全分离(10,10)r1矩形[0,2]x[0,2]false括号里这些例子的坐标我都实际跑过输出和预期完全一致。相切和圆心在矩形内部这两个用例是最容易出问题的建议重点测。4. 常见错误与排查实录4.1 错误一拿矩形的四个角当判据这是我见过最多的错误解法算出圆心到矩形四个顶点的距离取最小值如果小于半径就判定有重叠。这个问题非常隐蔽。当圆心恰好位于矩形的正上方或正下方时离圆心最近的矩形点并不是四个角中的任何一个而是边上的垂足。垂足距离可能远小于到任意一个顶点的距离只看四个顶点会把大量本该判定有重叠的情况误判为无重叠。说白了四个顶点只是矩形边界上的四个离散点用几个离散点去代表一整段连续的边中间的区间全被漏掉了。这种思路在圆心靠近顶点时恰好成立会让一两个测试用例蒙混过关但到了圆心对准边中间位置时立刻露馅。4.2 错误二把矩形当作上下左右的对称区间还有的人会把矩形误理解成以(x1,y1)为中心、向四周扩展的对称区域于是把x的合法范围写成[x1-x2, x1x2]。这个理解跟题目定义完全对不上。看题要仔细。LeetCode原题描述是矩形由左上角(x1, y1)和右下角(x2, y2)定义x1 x2y1 y2。也就是说它是标准的左上角右下角表示法不是什么中心点加宽高的表示法。拿到题目第一件事不是写代码而是先确认坐标系的定义。这块理解错了后面全是白做。4.3 错误三平方比较时忽略符号计算距离的时候dx xCenter - closest_xdy yCenter - closest_y这两个值完全可能为负。但是如果紧接着做平方运算负号就被消掉了所以用dx * dx dy * dy不会有问题。真正有问题的情况是只计算一维距离比如只用abs(xCenter - closest_x)小于半径来判断。这会让所有圆心与矩形在y方向上有偏差、但x方向上刚好满足条件的情况产生误判。二维问题必须用二维距离不要试图用一维距离去近似。4.4 时间和空间复杂度分析时间复杂度是O(1)因为无论坐标多大都只做常数次比较和算术运算。空间复杂度同样是O(1)只用了一个固定数量的临时变量。这就是为什么这个解法能在LeetCode上跑出“耗时100”的水平——题目叫“耗时100”指的是用时排进了所有提交的前1%而一个O(1)的解法在大数据量面前天然拥有优势。如果你看到自己的提交只击败了百分之二三十的人不用太担心很多时候只是网络波动或者判断基准不同。O(1)的解法和O(1)的解法比差的只有常系数这部分通常可以忽略不计。5. 变体扩展与实际应用5.1 圆与线段、圆与三角形的判断理解了最近点法之后很多相关题目都会做。比如判断圆和任意线段是否相交本质就是把线段的端点做clamp——把圆心投影到线段所在直线上把投影点夹逼到线段两个端点之间这个clamp就是最近点。再看圆和三角形是否相交可以把三角形拆成三条边分别做点到线段的距离判断再额外判断圆心是否在三角形内部。这些题看起来不一样但解法内核都一样找到目标图形上离圆心最近的点无非是加了一个“最近点怎么找”的步骤。矩形用clamp线段也用clamp三角形则要拆边加内部判断。5.2 游戏与图形学里的碰撞检测判断圆和轴对齐矩形是否重叠这个需求在2D游戏里到处都是。玩家的角色碰撞体是圆形墙体和障碍物是AABB矩形两者是否发生碰撞用的就是LeetCode 1401的算法。在真实游戏引擎里为了效率还会提前做一个快速排除如果两个图形的包围圆不相交或者包围盒不相交那就直接判定不相交。判断圆和AABB重叠的精确算法和这道题是完全一致的。面试的时候如果能把“这题在游戏引擎里对应什么场景”说出来是很加分的。5.3 用面向对象的方式重写如果是在项目里而不是在LeetCode上写我更倾向把核心逻辑封装成一个函数方便复用def clamp(value: float, lower: float, upper: float) - float: return max(lower, min(value, upper)) def circle_rect_overlap( cx: float, cy: float, r: float, x1: float, y1: float, x2: float, y2: float ) - bool: left, right min(x1, x2), max(x1, x2) top, bottom max(y1, y2), min(y1, y2) closest_x clamp(cx, left, right) closest_y clamp(cy, bottom, top) return (cx - closest_x) ** 2 (cy - closest_y) ** 2 r * r这段代码对输入坐标做了一个前处理先把左右边界和上下边界重新排序保证传入的矩形坐标顺序无论多乱都能正确处理。我实际使用中发现很多工程场景里传入的坐标根本没有保证左上角在前提前做归一化能省掉后续大量bug。做这道题的过程中我最大的体会是几何题的难度往往不在数学公式本身而在于边界情况和坐标定义。clamp这个操作看上去人畜无害但如果你没想清楚矩形y轴的方向写反了就能让你调一晚上。建议拿到题先花两分钟把坐标系画出来把所有边界情况列一遍再动手写代码。很多时候想清楚的那两分钟能替你省下调试的两小时。