几何基元碰撞检测：点、线、圆、矩形与多边形
各位同学，今天我们来聊聊路径规划里最基础、也最绕不开的一环——碰撞检测。
说白了，机器人要在环境里走，就得知道自己有没有撞上东西。而环境里的障碍物，抽象出来无非就是点、线、圆、矩形、多边形这些几何基元。你想想看，如果连这些基本形状的碰撞都搞不定，后面的路径规划算法再漂亮也是白搭。
我个人习惯把碰撞检测分成两类：静态检测（两个物体都不动，判断是否相交）和动态检测（物体在运动过程中是否发生碰撞）。今天我们先啃静态检测这块硬骨头。
1. 点与点的碰撞检测
这个最简单，但别小看它。很多复杂碰撞最终都会退化到点与点的距离判断。
原理： 两个点重合，即坐标完全相等。
def point_point_collision(p1, p2):
return p1.x == p2.x and p1.y == p2.y嗯，这里要注意：浮点数比较时别直接用 ==，容易踩坑。我建议用距离阈值判断：
def point_point_collision(p1, p2, eps=1e-6):
dx = p1.x - p2.x
dy = p1.y - p2.y
return dx*dx + dy*dy < eps*eps== 比较浮点坐标，结果定位误差导致碰撞检测漏报，差点让两台小车亲上。后来全部改成阈值判断，再没出过问题。
2. 点与线的碰撞检测
判断一个点是否在一条线段上。注意是线段，不是无限延伸的直线。
核心思路： 先判断点是否在直线上（叉积为0），再判断点是否在线段范围内（点积投影）。
def point_line_collision(p, line_start, line_end):
# 叉积判断共线
cross = (p.x - line_start.x) * (line_end.y - line_start.y) - \
(p.y - line_start.y) * (line_end.x - line_start.x)
if abs(cross) > 1e-6:
return False
# 点积判断投影范围
dot = (p.x - line_start.x) * (line_end.x - line_start.x) + \
(p.y - line_start.y) * (line_end.y - line_start.y)
if dot < 0:
return False
squared_length = (line_end.x - line_start.x)**2 + \
(line_end.y - line_start.y)**2
if dot > squared_length:
return False
return True我在做扫地机器人路径规划时，经常用这个检测机器人中心点是否压到了墙线。你想想看，如果点刚好在线段端点附近，上面的代码也能正确处理。
3. 圆与圆的碰撞检测
这个太常用了。机器人本体、障碍物、传感器范围，很多都可以用圆来近似。
原理： 两圆圆心距离 ≤ 半径之和，则碰撞。
def circle_circle_collision(c1, c2):
dx = c1.center.x - c2.center.x
dy = c1.center.y - c2.center.y
distance_sq = dx*dx + dy*dy
radius_sum = c1.radius + c2.radius
return distance_sq <= radius_sum * radius_sum4. 圆与矩形的碰撞检测
这个稍微复杂一点。我见过不少新手直接拿圆心到矩形中心的距离去判断，结果各种漏报。
正确做法： 找到矩形上离圆心最近的点，然后判断该点与圆心的距离是否小于半径。
def circle_rect_collision(circle, rect):
# 找到矩形上离圆心最近的点
closest_x = max(rect.left, min(circle.center.x, rect.right))
closest_y = max(rect.bottom, min(circle.center.y, rect.top))
dx = circle.center.x - closest_x
dy = circle.center.y - closest_y
return dx*dx + dy*dy <= circle.radius * circle.radius说白了，就是把矩形看作一个「夹紧」的区域。圆心被夹到矩形边界上，再算距离。这个方法也适用于圆与任意凸多边形的碰撞检测——找到多边形上离圆心最近的点即可。
5. 矩形与矩形的碰撞检测（AABB）
轴对齐矩形（AABB）的碰撞检测是游戏和机器人领域的标配。两个矩形不碰撞的条件是：一个矩形完全在另一个的左边、右边、上边或下边。
def rect_rect_collision(r1, r2):
if r1.right < r2.left or r1.left > r2.right:
return False
if r1.top < r2.bottom or r1.bottom > r2.top:
return False
return True这个算法叫分离轴定理的简化版。对于AABB，只需要检测两个轴（x和y）就够了。如果是旋转矩形，那就得用完整的分离轴定理了。
6. 多边形与多边形的碰撞检测
这是最通用的方法，也是性能开销最大的。核心算法是分离轴定理（SAT）。
原理： 如果能找到一条轴，使得两个多边形在该轴上的投影不重叠，则它们不相交。
def polygon_polygon_collision(poly1, poly2):
# 获取所有边的法向量作为候选轴
axes = get_axes(poly1) + get_axes(poly2)
for axis in axes:
proj1 = project_polygon(poly1, axis)
proj2 = project_polygon(poly2, axis)
if not overlap(proj1, proj2):
return False # 找到分离轴，不相交
return True # 所有轴都重叠，相交知识体系总览
下面这张图总结了本章的核心逻辑。从最简单的点-点检测，逐步扩展到通用的多边形-多边形检测。每个算法都可以作为更复杂碰撞检测的基石。
实际项目中的选择建议
讲了这么多算法，你可能会问：到底该用哪个？
我的经验是：能用简单就别用复杂。如果障碍物可以用圆近似，就别用多边形。如果矩形就够了，就别用通用多边形。
| 场景 | 推荐算法 | 原因 |
|---|---|---|
| 机器人本体与静态障碍物 | 圆-圆 / 圆-矩形 | 速度快，精度够用 |
| 地图边界检测 | 点-线 | 精确判断是否越界 |
| 复杂形状障碍物 | 多边形-多边形（SAT） | 通用性强，但注意性能 |
| 动态障碍物预测 | 圆-圆 | 计算量小，适合高频更新 |
好了，几何基元的碰撞检测就讲到这里。这些算法看起来简单，但它们是整个路径规划系统的地基。地基不稳，上层建筑再漂亮也是危楼。希望你能把这些基础打牢，后面学起来会轻松很多。
可可精品资料库