分离轴算法(SAT)的前置步骤：手把手教你用Python实现凹多边形切割
分离轴算法(SAT)的前置步骤：手把手教你用Python实现凹多边形切割
在计算机图形学和游戏物理引擎开发中，碰撞检测是一个基础而关键的问题。分离轴定理(SAT)作为高效的碰撞检测算法，要求输入必须是凸多边形。但现实中的物体形状往往包含凹多边形，这就需要在应用SAT前进行凹多边形切割。本文将带你从零开始，用Python实现这一关键预处理步骤。
1. 理解凹多边形与凸多边形
凹多边形和凸多边形是几何学中的基本概念。简单来说，凸多边形是指所有内角都不超过180度的多边形，而凹多边形则至少有一个内角大于180度。这种结构差异直接影响碰撞检测算法的选择：
凸多边形特性：
- 任意两点连线都在多边形内部
- 所有内角均小于180度
- 适合使用分离轴算法
凹多边形特性：
- 存在至少一个内角大于180度
- 可能存在两点连线在多边形外部
- 需要先切割为凸多边形才能应用SAT
class 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[(i+1)%n] c = self.points[(i+2)%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[(i+1)%n] c = polygon[(i+2)%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 (i+1)%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[(i+1)%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_idx+1:intersect_idx+1] + [intersection] part2 = [intersection] + current[intersect_idx+1:] + current[:prev_idx+1] else: part1 = current[prev_idx+1:] + current[:intersect_idx+1] + [intersection] part2 = [intersection] + current[intersect_idx+1:prev_idx+1] 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, closed=True, facecolor=color, edgecolor='black', alpha=0.5, label=f'Polygon {i+1}') 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_depth=10): """带优化的凹多边形分割""" 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[(i+1)%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[(i+1)%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算法能够高效处理复杂形状的碰撞检测，是游戏引擎和物理模拟中的常用技术组合。