一个简单的德劳内三角剖分实现

德劳内（Delaunay）三角剖分是一种经典的将点集进行三角网格化预处理的手段，在NavMesh、随机地牢生成等场景下都有应用。
具体内容百度一大堆，就不介绍了。
比较知名的算法是Bowyer-Watson算法，也就是逐点插入法。
下雨闲着没事简单实现了一下，效果如下：

思路很简单：

1. 收集点集，以及点集的范围
2. 初始构建一个超级三角形，将所有点包含在内，并将超级三角形加入三角形列表
3. 逐个点进行插入
   • 找到所有外接圆包含该插入点的三角形，标记为BadTriangle
   • 从三角形列表中移除所有BadTriangle，但需要记录这些BadTriangle的边，因为之后可能需要用这些边构建新的三角形
   • 将收集到的边进行去重，这里的去重指的是如果两条边的端点是同样的点，就将这两条边都删除，而不是只删除一条，实际是为了删除多个三角形之间的共享边
   • 这样所有BadTriangle剩余的边就围成了一个多边形空洞，也就是所谓的空洞化
   • 用这个多边形空洞的每条边跟插入点构建新的三角形，并加入三角形列表中，用于后续插入点的检查
4. 超级三角形只用于辅助构建，其顶点并不是真实存在的点，因此在所有点插入完成后，需要将包含SuperTriangle顶点的三角形从列表中删除
5. 构建完成

当然这只是趁午饭时间随手写的一个演示效果，没有考虑性能的问题.

代码如下：

using System.Collections.Generic;
using UnityEngine;namespace MapRandom.Delaunay
{public static class VectorExtension{public static bool Same(this Vector3 _this, Vector3 _other){return Mathf.Approximately(_this.x, _other.x) &&Mathf.Approximately(_this.y, _other.y) &&Mathf.Approximately(_this.z, _other.z);}}public class TestDelaunay : MonoBehaviour{private class Triangle{public Vector3 PointA,PointB,PointC;public List<Edge> Edges;public Vector3 Center;public float Radius;public float RadiusSqr;public Triangle(Vector3 _pointA, Vector3 _pointB, Vector3 _pointC){PointA = _pointA;PointB = _pointB;PointC = _pointC;CalcCircumcircle();CalcEdges();}/// <summary>/// 计算外接圆/// </summary>private void CalcCircumcircle(){float _ab = PointA.sqrMagnitude;float _cd = PointB.sqrMagnitude;float _ef = PointC.sqrMagnitude;float _circumX = (_ab * (PointC.y - PointB.y) + _cd * (PointA.y - PointC.y) + _ef * (PointB.y - PointA.y)) / (PointA.x * (PointC.y - PointB.y) + PointB.x * (PointA.y - PointC.y) + PointC.x * (PointB.y - PointA.y));float _circumY = (_ab * (PointC.x - PointB.x) + _cd * (PointA.x - PointC.x) + _ef * (PointB.x - PointA.x)) / (PointA.y * (PointC.x - PointB.x) + PointB.y * (PointA.x - PointC.x) + PointC.y * (PointB.x - PointA.x));Center = new Vector3(_circumX / 2, _circumY / 2);Radius = Vector3.Distance(Center, PointA);RadiusSqr = Radius * Radius;}/// <summary>/// 生成边信息/// </summary>private void CalcEdges(){Edges = new List<Edge>(3);Edges.Add(new Edge(PointA, PointB));Edges.Add(new Edge(PointB, PointC));Edges.Add(new Edge(PointC, PointA));}/// <summary>/// 检查点在外接圆内/// </summary>/// <param name="_point"></param>/// <returns></returns>public bool CheckCircumcircleContains(Vector3 _point){return Vector3.SqrMagnitude(_point - Center) < RadiusSqr;}/// <summary>/// 检查顶点包含某一点/// </summary>/// <param name="_point"></param>/// <returns></returns>public bool CheckHasVertex(Vector3 _point){return PointA.Same(_point) ||PointB.Same(_point) ||PointC.Same(_point);}}private class Edge{public Vector3 PointA,PointB;public bool IsBad;public Edge(Vector3 _pointA, Vector3 _pointB){PointA = _pointA;PointB = _pointB;IsBad = false;}/// <summary>/// 检查顶点包含某一点/// </summary>/// <param name="_point"></param>/// <returns></returns>public bool CheckHasVertex(Vector3 _point){return PointA.Same(_point) ||PointB.Same(_point);}/// <summary>/// 是否为重复边/// </summary>/// <param name="_other"></param>/// <returns></returns>public bool Same(Edge _other){return PointA.Same(_other.PointA) && PointB.Same(_other.PointB) ||PointA.Same(_other.PointB) && PointB.Same(_other.PointA);}}public Transform TestRoot;private List<Vector3> mPointList = new();private List<Triangle> mTriangleList = new();private List<Edge> mTmpEdgeList = new();private void Update(){if (null == TestRoot) return;Triangulate();}private void CollectPoints(){mPointList.Clear();for (int i = 0; i < TestRoot.childCount; i++){Transform _child = TestRoot.GetChild(i);Vector3 _point = new Vector3(_child.position.x, _child.position.y, 0);mPointList.Add(_point);}}private void Triangulate(){mTriangleList.Clear();//收集点的范围CollectPoints();float _minX = float.MaxValue, _minY = float.MaxValue;float _maxX = float.MinValue, _maxY = float.MinValue;foreach (Vector3 _point in mPointList){_minX = Mathf.Min(_minX, _point.x);_minY = Mathf.Min(_minY, _point.y);_maxX = Mathf.Max(_maxX, _point.x);_maxY = Mathf.Max(_maxY, _point.y);}//构建超级三角形float _dx = _maxX - _minX;float _dy = _maxY - _minY;float _maxDelta = Mathf.Max(_dx, _dy) * 2f;Triangle _superTriangle = new Triangle(new Vector3(_minX - 1, _minY - 1),new Vector3(_minX - 1, _maxY + _maxDelta),new Vector3(_maxX + _maxDelta, _minY - 1));mTriangleList.Add(_superTriangle);//逐点插入foreach (Vector3 _point in mPointList){//首先删除所有外接圆包含插入点的三角形//收集BadTriangle的边用于后续构建新三角形mTmpEdgeList.Clear();for (int i = mTriangleList.Count - 1; i >= 0; i--){Triangle _triangle = mTriangleList[i];if (_triangle.CheckCircumcircleContains(_point)){mTmpEdgeList.AddRange(_triangle.Edges);mTriangleList.RemoveAt(i);}}//空洞化，边查重，删除所有共享边for (int i = 0; i < mTmpEdgeList.Count; i++){Edge _edge_1 = mTmpEdgeList[i];if (_edge_1.IsBad) continue;for (int j = i + 1; j < mTmpEdgeList.Count; j++){Edge _edge_2 = mTmpEdgeList[j];if (_edge_1.Same(_edge_2)){_edge_1.IsBad = true;_edge_2.IsBad = true;}}}for (int i = mTmpEdgeList.Count - 1; i >= 0; i--){if (mTmpEdgeList[i].IsBad){mTmpEdgeList.RemoveAt(i);}   }//空洞边与插入点构建新三角形foreach (Edge _edge in mTmpEdgeList){Triangle _triangle = new Triangle(_edge.PointA, _point, _edge.PointB);mTriangleList.Add(_triangle);}}//超级三角形只起辅助构建的作用，其顶点并不是真实存在的点//因此最后需要将所有超级三角形相关的三角形删除for (int i = mTriangleList.Count - 1; i >= 0 ; i--){Triangle _triangle = mTriangleList[i];if (_triangle.CheckHasVertex(_superTriangle.PointA) ||_triangle.CheckHasVertex(_superTriangle.PointB) ||_triangle.CheckHasVertex(_superTriangle.PointC)){mTriangleList.RemoveAt(i);}}}private void OnDrawGizmos(){Gizmos.color = Color.red;foreach (Triangle _triangle in mTriangleList){foreach (Edge _edge in _triangle.Edges){Gizmos.DrawLine(_edge.PointA, _edge.PointB);}}}}
}