从锥桶迷宫到最优路径：Delaunay三角剖分如何让FSD赛车"看见"赛道？
当一辆自动驾驶赛车以200公里时速冲入弯道时，它的"眼睛"看到的不是传统赛道，而是散落在两侧的红蓝锥桶——这些离散的标记点就像黑暗中的灯塔，而Delaunay三角剖分正是将这些孤立光点编织成完整赛道地图的魔法。本文将揭示这项几何学技术如何成为FSD赛车路径规划的核心算法，以及它如何通过数学之美解决现实中的导航难题。
1. 离散环境中的赛道认知革命
传统自动驾驶依赖高精地图和连续边界检测，但在锥桶标记的临时赛道上，这套系统完全失效。红蓝锥桶构成的离散点阵，就像被随机撒落的糖果，无法直接形成连贯的赛道边界。这正是Delaunay三角剖分大显身手的场景——它能从混乱中创造秩序。
三角剖分的认知优势：
- 空间填补：将相邻锥桶连接成三角形网格，构建连续的赛道拓扑结构
- 障碍物规避：三角形边自然形成远离锥桶的安全通道
- 计算高效：相比栅格地图，三角网只需存储顶点和连接关系
在FSD算法中，初始处理阶段会过滤掉无效锥桶（如距离超过15米或位于车辆后方的标记）。以下是一个简化的过滤逻辑示例：
def filter_cones(cones, max_distance=15): valid_cones = [] for cone in cones: if cone.x > 0 and math.hypot(cone.x, cone.y) < max_distance: valid_cones.append(cone) return valid_cones提示：Delaunay三角剖分的"空圆特性"确保生成的三角形尽可能等边，这为路径规划提供了几何学上的最优基础
2. 三角剖分的几何魔法：从数学原理到赛道重建
Delaunay三角剖分的核心在于两个黄金法则：空外接圆准则和最大化最小角原则。当应用于赛道场景时，这些抽象数学概念展现出惊人的实用价值。
关键特性对比：
| 特性 | 数学定义 | 赛道应用价值 |
|---|---|---|
| 空圆准则 | 三角形外接圆内不含其他点 | 确保路径远离锥桶，提高安全性 |
| 最大化最小角 | 所有三角剖分中最小角最大 | 生成更平滑的路径，减少急转弯 |
| Voronoi对偶 | 与Voronoi图互为对偶图 | 提供自然的中线路径候选 |
构建三角网的过程就像在锥桶间拉伸橡皮筋——算法会自动寻找最"均匀"的连接方式。OpenCV中的Subdiv2D类提供了高效的实现：
cv::Rect rect(-200, -200, 400, 400); // 定义工作区域 cv::Subdiv2D coneSet(rect); // 创建三角剖分对象 // 插入红色锥桶点 for (const auto &cone : red_cones) { cv::Point2f fp(cone.position.x, cone.position.y); coneSet.insert(fp); }3. 从三角网到最优路径：FSD算法的决策逻辑
三角剖分完成后，算法需要将这些几何结构转化为可行驶路径。FSD采用了一种创新的"中点搜索"策略，在三角网的边上寻找最佳通过点。
路径生成四步法：
- 边中点计算：提取所有有效三角边的中点作为候选路径点
- 颜色校验：优先选择连接红蓝锥桶的边（代表赛道两侧）
- 树形搜索：使用beam search算法探索可能路径组合
- 成本优化：根据曲率、距离、平滑度等权重选择最佳路径
中点计算阶段会特别处理车辆当前位置（坐标原点）作为路径起点，并过滤掉与虚拟三角形相连的无效边。以下代码片段展示了这一过程：
void getMidPoint(cv::Subdiv2D coneSet, std::map<ConePos,char> colorMap, std::map<int, PathPoint> &MidSet) { std::vector<cv::Vec4f> edges; coneSet.getEdgeList(edges); // 添加车辆位置作为起点(ID=0) PathPoint car; car.id = 0; car.x = 0; car.y = 0; MidSet[0] = car; // 处理所有实际边 for (int i = 0, j = 0; i < edges.size(); i++) { // 跳过虚拟三角形边的逻辑... PathPoint tmp; // 颜色处理和边界计算... tmp.CalculateMidPoint(); // 计算中点坐标 MidSet[2*j+1] = tmp; // 正向连接 MidSet[2*j+2] = tmp.ReverseCone(); // 反向连接 j++; } }4. 实战优化：让算法适应真实赛道挑战
理论完美的算法在真实赛道上会遇到各种意外情况。FSD团队通过多项技术创新使Delaunay三角剖分真正具备实战能力。
常见问题与解决方案：
| 挑战 | 现象 | 解决策略 |
|---|---|---|
| 锥桶缺失 | 局部赛道侧无标记 | 引入历史路径记忆和预测 |
| 颜色错误 | 红蓝锥桶误识别 | 建立颜色一致性校验机制 |
| 动态障碍 | 赛道上出现车辆 | 实时更新三角网并重规划 |
| 极端弯道 | 急弯处路径震荡 | 增加曲率平滑度权重 |
搜索算法采用加权成本函数来平衡多个路径指标：
struct CostWeights { double w_c; // 曲率成本 double w_k; // 距离中线偏移 double w_w; // 路径波动 double w_d; // 与障碍物距离 };在慕尼黑工业大学的测试中，这套系统成功处理了连续S弯接发卡弯的复合赛道，平均路径偏离误差控制在0.2米以内，计算延迟仅8毫秒——这足以支持300公里/小时的竞技级自动驾驶。
