分离轴算法(SAT)的前置步骤：手把手教你用Python实现凹多边形切割

分离轴算法(SAT)的前置步骤手把手教你用Python实现凹多边形切割在计算机图形学和游戏物理引擎开发中碰撞检测是一个基础而关键的问题。分离轴定理(SAT)作为高效的碰撞检测算法要求输入必须是凸多边形。但现实中的物体形状往往包含凹多边形这就需要在应用SAT前进行凹多边形切割。本文将带你从零开始用Python实现这一关键预处理步骤。1. 理解凹多边形与凸多边形凹多边形和凸多边形是几何学中的基本概念。简单来说凸多边形是指所有内角都不超过180度的多边形而凹多边形则至少有一个内角大于180度。这种结构差异直接影响碰撞检测算法的选择凸多边形特性任意两点连线都在多边形内部所有内角均小于180度适合使用分离轴算法凹多边形特性存在至少一个内角大于180度可能存在两点连线在多边形外部需要先切割为凸多边形才能应用SATclass Polygon: def __init__(self, points): self.points points # 顶点列表按逆时针顺序存储 self.is_convex self._check_convexity() def _check_convexity(self): 检查多边形是否为凸多边形 n len(self.points) if n 3: return False sign 0 for i in range(n): # 获取连续的三个点 a self.points[i] b self.points[(i1)%n] c self.points[(i2)%n] # 计算叉积 cross (b[0]-a[0])*(c[1]-b[1]) - (b[1]-a[1])*(c[0]-b[0]) if cross 0: continue # 共线情况 if sign 0: sign 1 if cross 0 else -1 else: if (cross 0 and sign 0) or (cross 0 and sign 0): return False # 发现凹点 return True2. 凹多边形切割的核心算法凹多边形切割的核心思路是递归地消除凹点直到所有多边形都变为凸多边形。具体步骤如下找到第一个凹点延长该凹点的起始边计算延长线与多边形其他边的交点根据交点将多边形分割为两部分对分割后的多边形重复上述过程2.1 寻找凹点在逆时针排列的多边形顶点中凹点的判定标准是内角大于180度。通过向量叉积可以高效判断def find_concave_point(polygon): 寻找多边形中的凹点 n len(polygon) for i in range(n): a polygon[i] b polygon[(i1)%n] c polygon[(i2)%n] # 计算向量ab和bc ab (b[0]-a[0], b[1]-a[1]) bc (c[0]-b[0], c[1]-b[1]) # 计算叉积 cross ab[0]*bc[1] - ab[1]*bc[0] # 在逆时针排列下叉积为负表示凹点 if cross 0: return (i1)%n # 返回凹点索引 return None # 没有凹点是凸多边形2.2 延长边与求交点找到凹点后我们需要延长其起始边并计算与多边形其他边的交点def line_intersection(line1, line2): 计算两条直线的交点 (x1, y1), (x2, y2) line1 (x3, y3), (x4, y4) line2 # 计算分母 denom (y4-y3)*(x2-x1) - (x4-x3)*(y2-y1) if denom 0: # 平行或共线 return None # 计算参数 ua ((x4-x3)*(y1-y3) - (y4-y3)*(x1-x3)) / denom ub ((x2-x1)*(y1-y3) - (y2-y1)*(x1-x3)) / denom # 检查交点是否在线段上 if ua 0 or ua 1 or ub 0 or ub 1: return None # 计算交点坐标 x x1 ua * (x2 - x1) y y1 ua * (y2 - y1) return (x, y)3. 实现完整的切割流程将上述步骤组合起来我们可以实现完整的凹多边形切割算法def split_concave_polygon(polygon): 将凹多边形分割为凸多边形列表 from collections import deque convex_polygons [] queue deque([polygon]) while queue: current queue.popleft() concave_idx find_concave_point(current) if concave_idx is None: # 已经是凸多边形 convex_polygons.append(current) continue # 获取凹点和其相邻点 n len(current) prev_idx (concave_idx - 1) % n next_idx (concave_idx 1) % n prev_point current[prev_idx] concave_point current[concave_idx] next_point current[next_idx] # 延长prev_point到concave_point的边 extended_line (prev_point, concave_point) # 寻找与延长线相交的边 intersection None intersect_idx None for i in range(n): if i prev_idx or i concave_idx: continue line (current[i], current[(i1)%n]) intersect line_intersection(extended_line, line) if intersect: intersection intersect intersect_idx i break if not intersection: # 没有找到交点可能是特殊情况 # 处理延长线与顶点相交的情况 for i in range(n): if i prev_idx or i concave_idx: continue # 检查点是否在延长线上 point current[i] if point_on_line(point, extended_line): intersection point intersect_idx i break if not intersection: continue # 无法分割保留原多边形 # 分割多边形 if prev_idx intersect_idx: part1 current[prev_idx1:intersect_idx1] [intersection] part2 [intersection] current[intersect_idx1:] current[:prev_idx1] else: part1 current[prev_idx1:] current[:intersect_idx1] [intersection] part2 [intersection] current[intersect_idx1:prev_idx1] queue.append(part1) queue.append(part2) return convex_polygons4. 可视化与性能优化为了更好理解算法过程我们可以使用matplotlib进行可视化import matplotlib.pyplot as plt from matplotlib.patches import Polygon as MplPolygon def plot_polygons(polygons, title): 绘制多边形列表 fig, ax plt.subplots(figsize(8, 8)) for i, poly in enumerate(polygons): color (random.random(), random.random(), random.random()) patch MplPolygon(poly, closedTrue, facecolorcolor, edgecolorblack, alpha0.5, labelfPolygon {i1}) ax.add_patch(patch) ax.set_xlim(min(p[0] for poly in polygons for p in poly)-1, max(p[0] for poly in polygons for p in poly)1) ax.set_ylim(min(p[1] for poly in polygons for p in poly)-1, max(p[1] for poly in polygons for p in poly)1) ax.set_aspect(equal) ax.set_title(title) ax.legend() plt.grid(True) plt.show()4.1 性能优化技巧提前终止检查在分割过程中一旦发现多边形已经是凸多边形立即停止进一步分割缓存计算结果对于大型多边形可以缓存已经计算过的边交点并行处理对于多个独立的多边形可以采用并行处理方式def optimized_split(polygon, max_depth10): 带优化的凹多边形分割 if max_depth 0: return [polygon] if is_convex(polygon): return [polygon] # ... 分割逻辑 ... part1_convex is_convex(part1) part2_convex is_convex(part2) result [] if not part1_convex: result optimized_split(part1, max_depth-1) else: result.append(part1) if not part2_convex: result optimized_split(part2, max_depth-1) else: result.append(part2) return result5. 与分离轴算法(SAT)的集成完成凹多边形切割后我们可以将结果直接用于SAT碰撞检测def sat_collision(poly1, poly2): 分离轴算法实现 polygons1 split_concave_polygon(poly1) if not is_convex(poly1) else [poly1] polygons2 split_concave_polygon(poly2) if not is_convex(poly2) else [poly2] # 检查所有凸多边形组合 for p1 in polygons1: for p2 in polygons2: if convex_sat(p1, p2): return True return False def convex_sat(poly1, poly2): 凸多边形SAT检测 axes [] # 获取所有边的法线作为投影轴 for i in range(len(poly1)): a poly1[i] b poly1[(i1)%len(poly1)] edge (b[0]-a[0], b[1]-a[1]) normal (-edge[1], edge[0]) # 左手法则得到的法线 axes.append(normal) for i in range(len(poly2)): a poly2[i] b poly2[(i1)%len(poly2)] edge (b[0]-a[0], b[1]-a[1]) normal (-edge[1], edge[0]) axes.append(normal) # 归一化所有轴 axes [normalize(axis) for axis in axes] # 在所有轴上检查投影重叠 for axis in axes: if not overlap_on_axis(poly1, poly2, axis): return False return True在实际项目中这种凹多边形预处理配合SAT算法能够高效处理复杂形状的碰撞检测是游戏引擎和物理模拟中的常用技术组合。