引言
德劳内三角剖分（Delaunay Triangulation）是计算几何中的经典算法，它对于平面上的一组离散点，生成一组三角形，使得每个三角形的外接圆内部不包含其他任何输入点。这一性质被称为”空外接圆准则”，它保证了生成的三角形尽可能”匀称”，避免出现过于细长的退化三角形。在游戏开发中，德劳内三角剖分被广泛用于导航网格（NavMesh）生成、地形三角化、Voronoi图构建以及物理模拟中的粒子邻域查询。本文将用Java实现Bowyer-Watson增量插入算法，完整展示从点集到三角网格的构建过程。
算法核心思想
Bowyer-Watson算法采用增量插入策略：
- 初始化超级三角形：构造一个包含所有输入点的大三角形作为初始三角网格。
- 逐点插入：对于每个输入点：
- 找出所有外接圆包含该点的三角形（这些三角形违反了空外接圆准则）。
- 删除这些”坏”三角形，形成一个空腔（cavity）。
- 将空腔边界上的边与新点连接，形成新的三角形。
- 清理：删除与超级三角形顶点相关的所有三角形。
这一增量策略的核心在于局部重构：每次插入只影响包含该点的局部区域，通过”删除坏三角+重新连接边界”的操作恢复德劳内性质。
Java实现
import java.util.*;
/**
* 德劳内三角剖分（Delaunay Triangulation）
* 使用Bowyer-Watson增量插入算法实现
*/
public class DelaunayTriangulation {
// 二维点
static class Point {
double x, y;
int id; // 点编号（调试用）
public Point(double x, double y, int id) {
this.x = x;
this.y = y;
this.id = id;
}
public Point(double x, double y) {
this(x, y, -1);
}
@Override
public String toString() {
return String.format("P%d(%.1f,%.1f)", id, x, y);
}
}
// 三角形
static class Triangle {
Point a, b, c; // 三个顶点
Point circumCenter; // 外接圆圆心
double circumRadius; // 外接圆半径
public Triangle(Point a, Point b, Point c) {
this.a = a;
this.b = b;
this.c = c;
computeCircumcircle();
}
// 计算外接圆
private void computeCircumcircle() {
double d = 2 * (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y));
if (Math.abs(d) < 1e-10) {
// 三点共线，退化为大圆
circumCenter = new Point(0, 0);
circumRadius = Double.MAX_VALUE;
return;
}
double ux = ((a.x * a.x + a.y * a.y) * (b.y - c.y)
+ (b.x * b.x + b.y * b.y) * (c.y - a.y)
+ (c.x * c.x + c.y * c.y) * (a.y - b.y)) / d;
double uy = ((a.x * a.x + a.y * a.y) * (c.x - b.x)
+ (b.x * b.x + b.y * b.y) * (a.x - c.x)
+ (c.x * c.x + c.y * c.y) * (b.x - a.x)) / d;
circumCenter = new Point(ux, uy);
circumRadius = Math.hypot(a.x - ux, a.y - uy);
}
// 判断点p是否在外接圆内部（在圆上也算内部）
boolean containsInCircumcircle(Point p) {
double dist = Math.hypot(p.x - circumCenter.x, p.y - circumCenter.y);
return dist < circumRadius + 1e-8;
}
// 判断点是否是三角形的顶点
boolean hasVertex(Point p) {
return p == a || p == b || p == c;
}
// 获取有向边（保证顺序一致性）
Edge[] getEdges() {
return new Edge[]{
new Edge(a, b),
new Edge(b, c),
new Edge(c, a)
};
}
@Override
public String toString() {
return String.format("[%s-%s-%s]", a, b, c);
}
}
// 边（无向，但保存方向用于比较）
static class Edge {
Point p1, p2;
public Edge(Point p1, Point p2) {
this.p1 = p1;
this.p2 = p2;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Edge)) return false;
Edge other = (Edge) o;
return (p1 == other.p1 && p2 == other.p2) || (p1 == other.p2 && p2 == other.p1);
}
@Override
public int hashCode() {
return System.identityHashCode(p1) + System.identityHashCode(p2);
}
@Override
public String toString() {
return String.format("(%s-%s)", p1, p2);
}
}
private List<Triangle> triangles;
private List<Point> points;
public DelaunayTriangulation() {
this.triangles = new ArrayList<>();
this.points = new ArrayList<>();
}
/**
* 对点集执行德劳内三角剖分
*/
public List<Triangle> triangulate(List<Point> inputPoints) {
this.points = new ArrayList<>(inputPoints);
triangles.clear();
if (points.size() < 3) {
return triangles;
}
// 计算包围盒
double minX = Double.MAX_VALUE, minY = Double.MAX_VALUE;
double maxX = -Double.MAX_VALUE, maxY = -Double.MAX_VALUE;
for (Point p : points) {
minX = Math.min(minX, p.x);
minY = Math.min(minY, p.y);
maxX = Math.max(maxX, p.x);
maxY = Math.max(maxY, p.y);
}
double dx = maxX - minX;
double dy = maxY - minY;
double dMax = Math.max(dx, dy);
double midX = (minX + maxX) / 2;
double midY = (minY + maxY) / 2;
// 创建超级三角形，确保包含所有点
Point p1 = new Point(midX - 20 * dMax, midY - dMax, -1);
Point p2 = new Point(midX, midY + 20 * dMax, -2);
Point p3 = new Point(midX + 20 * dMax, midY - dMax, -3);
triangles.add(new Triangle(p1, p2, p3));
// 逐点插入
for (Point p : points) {
insertPoint(p);
}
// 删除与超级三角形相关的三角形
triangles.removeIf(t -> t.hasVertex(p1) || t.hasVertex(p2) || t.hasVertex(p3));
return triangles;
}
private void insertPoint(Point p) {
// 1. 找出所有外接圆包含p的"坏"三角形
List<Triangle> badTriangles = new ArrayList<>();
for (Triangle t : triangles) {
if (t.containsInCircumcircle(p)) {
badTriangles.add(t);
}
}
// 2. 找出坏三角形的边界边（只属于一个坏三角形的边）
List<Edge> boundaryEdges = new ArrayList<>();
for (Triangle t : badTriangles) {
for (Edge e : t.getEdges()) {
boolean isShared = false;
for (Triangle other : badTriangles) {
if (other == t) continue;
for (Edge oe : other.getEdges()) {
if (e.equals(oe)) {
isShared = true;
break;
}
}
if (isShared) break;
}
if (!isShared) {
boundaryEdges.add(e);
}
}
}
// 3. 删除坏三角形
triangles.removeAll(badTriangles);
// 4. 用边界边与新点连接形成新三角形
for (Edge e : boundaryEdges) {
triangles.add(new Triangle(e.p1, e.p2, p));
}
}
/**
* 计算三角形的面积（用于验证）
*/
public static double triangleArea(Point a, Point b, Point c) {
return Math.abs((b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y)) / 2.0;
}
/**
* 获取所有唯一的边（用于渲染或构建图结构）
*/
public Set<Edge> getUniqueEdges() {
Set<Edge> edges = new HashSet<>();
for (Triangle t : triangles) {
edges.addAll(Arrays.asList(t.getEdges()));
}
return edges;
}
/**
* 生成随机点集用于测试
*/
public static List<Point> generateRandomPoints(int count, double range) {
List<Point> points = new ArrayList<>();
Random rand = new Random(42); // 固定种子保证可重复
for (int i = 0; i < count; i++) {
points.add(new Point(rand.nextDouble() * range, rand.nextDouble() * range, i));
}
return points;
}
// ========== 游戏应用：导航网格生成 ==========
/**
* 从三角网格构建邻接图（用于A*寻路）
*/
public Map<Triangle, Set<Triangle>> buildAdjacencyGraph() {
Map<Triangle, Set<Triangle>> adj = new HashMap<>();
for (Triangle t : triangles) {
adj.put(t, new HashSet<>());
}
for (int i = 0; i < triangles.size(); i++) {
for (int j = i + 1; j < triangles.size(); j++) {
Triangle t1 = triangles.get(i);
Triangle t2 = triangles.get(j);
// 如果共享一条边，则相邻
for (Edge e1 : t1.getEdges()) {
for (Edge e2 : t2.getEdges()) {
if (e1.equals(e2)) {
adj.get(t1).add(t2);
adj.get(t2).add(t1);
}
}
}
}
}
return adj;
}
/**
* 获取三角形中心点（用于寻路节点）
*/
public static Point centroid(Triangle t) {
return new Point((t.a.x + t.b.x + t.c.x) / 3.0,
(t.a.y + t.b.y + t.c.y) / 3.0);
}
public static void main(String[] args) {
System.out.println("=== 德劳内三角剖分测试 ===");
// 测试1：简单四边形点集
List<Point> simplePoints = Arrays.asList(
new Point(0, 0, 0),
new Point(10, 0, 1),
new Point(10, 10, 2),
new Point(0, 10, 3),
new Point(5, 5, 4)
);
DelaunayTriangulation dt = new DelaunayTriangulation();
List<Triangle> result = dt.triangulate(simplePoints);
System.out.println("输入点数: " + simplePoints.size());
System.out.println("生成三角形数: " + result.size());
for (Triangle t : result) {
System.out.println(" " + t + " 面积=" + String.format("%.1f", triangleArea(t.a, t.b, t.c)));
}
// 测试2：随机点集
System.out.println("\n=== 随机点集测试（20个点） ===");
List<Point> randomPoints = generateRandomPoints(20, 100);
DelaunayTriangulation dt2 = new DelaunayTriangulation();
List<Triangle> result2 = dt2.triangulate(randomPoints);
System.out.println("输入点数: " + randomPoints.size());
System.out.println("生成三角形数: " + result2.size());
System.out.println("唯一边数: " + dt2.getUniqueEdges().size());
// 验证空外接圆准则（抽样检查）
System.out.println("\n=== 空外接圆准则验证 ===");
int violations = 0;
for (Triangle t : result2) {
for (Point p : randomPoints) {
if (!t.hasVertex(p) && t.containsInCircumcircle(p)) {
violations++;
}
}
}
System.out.println("违反空外接圆准则次数: " + violations + " (应为0)");
// 导航网格演示
System.out.println("\n=== 导航网格邻接图 ===");
Map<Triangle, Set<Triangle>> adj = dt2.buildAdjacencyGraph();
System.out.println("三角形邻接关系（前3个）:");
int count = 0;
for (Map.Entry<Triangle, Set<Triangle>> entry : adj.entrySet()) {
if (count++ >= 3) break;
Point c = centroid(entry.getKey());
System.out.println(" 中心(" + String.format("%.1f,%.1f", c.x, c.y) + ") 相邻=" + entry.getValue().size());
}
}
}
复杂度分析
- 时间复杂度：
- 朴素实现中，每次插入需要检查所有现有三角形，单次插入为O(n)，总复杂度O(n²)。
- 若使用点定位数据结构（如Dag of Triangles），可将总复杂度优化至O(n log n)。
- 空间复杂度：O(n)，存储三角形和边信息。
Bowyer-Watson算法的优势在于实现直观、易于理解。对于游戏开发中常见的几百到几千个点的导航网格生成，O(n²)的复杂度完全可以接受。若需要处理更大规模数据（如地形LOD的百万级点云），可结合空间哈希或Delaunay树进行优化。
总结
德劳内三角剖分通过空外接圆准则保证了三角形的质量，是计算几何和游戏开发中不可或缺的工具。本文实现的Bowyer-Watson增量算法清晰地展示了”识别坏三角→提取边界→局部重构”的核心流程。在实际游戏引擎中，生成的三角网格可进一步转化为凸多边形导航网格、Voronoi势力图，或与A*算法结合实现高效的三角形级别寻路。
