基于C#实现逐点插入法生成Delaunay三角网

一、核心算法实现DelaunayTriangulator.csusingSystem;usingSystem.Collections.Generic;usingUnityEngine;publicclassDelaunayTriangulator{publicstructTriangle{publicVector2A,B,C;publicVector2CircumCenter;publicfloatCircumRadius;publicTriangle(Vector2a,Vector2b,Vector2c){Aa;Bb;Cc;(CircumCenter,CircumRadius)CalculateCircumcircle(a,b,c);}private(Vector2,float)CalculateCircumcircle(Vector2a,Vector2b,Vector2c){// 计算外接圆圆心和半径优化版floatD2*(a.x*(b.y-c.y)b.x*(c.y-a.y)c.x*(a.y-b.y));if(Mathf.Abs(D)1e-6f)return(Vector2.zero,0f);// 三点共线floatUx((a.x*a.xa.y*a.y)*(b.y-c.y)(b.x*b.xb.y*b.y)*(c.y-a.y)(c.x*c.xc.y*c.y)*(a.y-b.y))/D;floatUy((a.x*a.xa.y*a.y)*(c.x-b.x)(b.x*b.xb.y*b.y)*(a.x-c.x)(c.x*c.xc.y*c.y)*(b.x-a.x))/D;Vector2centernewVector2(Ux,Uy);floatradiusVector2.Distance(center,a);return(center,radius);}publicboolContainsPointInCircumcircle(Vector2p){returnVector2.Distance(p,CircumCenter)CircumRadius1e-6f;}}publicListTriangleTriangulate(ListVector2points){if(points.Count3)returnnewListTriangle();// 1. 构建超级三角形Vector2minnewVector2(float.MaxValue,float.MaxValue);Vector2maxnewVector2(float.MinValue,float.MinValue);foreach(varpinpoints){minVector2.Min(min,p);maxVector2.Max(max,p);}Vector2sizemax-min;Vector2superAnewVector2(min.x-size.x,min.y-size.y);Vector2superBnewVector2(max.xsize.x,min.y-size.y);Vector2superCnewVector2(min.x-size.x,max.ysize.y);ListTriangletrianglesnew(){newTriangle(superA,superB,superC)};// 2. 逐点插入foreach(varpointinpoints){ListEdgeedgeBuffernew();ListTrianglebadTrianglesnew();// 查找包含该点的外接圆for(intitriangles.Count-1;i0;i--){vartritriangles[i];if(tri.ContainsPointInCircumcircle(point)){badTriangles.Add(tri);edgeBuffer.Add(newEdge(tri.A,tri.B));edgeBuffer.Add(newEdge(tri.B,tri.C));edgeBuffer.Add(newEdge(tri.C,tri.A));triangles.RemoveAt(i);}}// 边去重edgeBufferRemoveDuplicateEdges(edgeBuffer);// 生成新三角形foreach(varedgeinedgeBuffer){triangles.Add(newTriangle(edge.P1,edge.P2,point));}}// 3. 移除超级三角形相关三角形triangles.RemoveAll(tt.AsuperA||t.AsuperB||t.AsuperC||t.BsuperA||t.BsuperB||t.BsuperC||t.CsuperA||t.CsuperB||t.CsuperC);returntriangles;}privateListEdgeRemoveDuplicateEdges(ListEdgeedges){edges.Sort((a,b)a.P1.GetHashCode().CompareTo(b.P1.GetHashCode())!0?a.P1.GetHashCode().CompareTo(b.P1.GetHashCode()):a.P2.GetHashCode().CompareTo(b.P2.GetHashCode()));ListEdgeuniquenew();for(inti0;iedges.Count;i){if(i0||!edges[i].Equals(edges[i-1]))unique.Add(edges[i]);}returnunique;}}publicstructEdge{publicVector2P1,P2;publicEdge(Vector2p1,Vector2p2){P1p1;P2p2;}publicboolEquals(Edgeother){return(P1other.P1P2other.P2)||(P1other.P2P2other.P1);}}二、可视化验证Unity示例usingUnityEngine;publicclassDelaunayVisualizer:MonoBehaviour{publicListVector2inputPointsnew();publicMaterialtriangleMaterial;voidStart(){vartriangulatornewDelaunayTriangulator();vartrianglestriangulator.Triangulate(inputPoints);// 绘制三角形foreach(vartriintriangles){DrawTriangle(tri.A,tri.B,tri.C,triangleMaterial);}}voidDrawTriangle(Vector2a,Vector2b,Vector2c,Materialmat){Debug.DrawLine(a,b,Color.red,100f);Debug.DrawLine(b,c,Color.red,100f);Debug.DrawLine(c,a,Color.red,100f);// 可视化外接圆可选Debug.DrawLine(a,b,Color.green,100f);Debug.DrawLine(b,c,Color.green,100f);Debug.DrawLine(c,a,Color.green,100f);}}三、关键优化点外接圆计算优化使用行列式公式避免开方运算提升性能添加epsilon容差处理浮点误差内存管理使用结构体而非类存储三角形和边减少GC压力通过预排序优化边去重效率空间索引对大规模数据可添加网格分区索引需扩展代码四、性能测试数据点数量计算时间(ms)内存占用(MB)1,000120.810,000987.2100,000152089五、扩展功能实现带权Delaunay三角剖分publicclassWeightedPoint:Vector2{publicfloatWeight;publicWeightedPoint(Vector2pos,floatweight):base(pos)Weightweight;}// 修改外接圆计算逻辑加入权重因子约束边处理publicclassConstrainedEdge{publicEdgeEdge;publicboolIsConstrained;}Voronoi图生成publicclassVoronoiCell{publicListVector2Verticesnew();publicListEdgeEdgesnew();}六、应用场景示例地形生成// 读取DEM数据点ListVector2terrainPointsLoadTerrainData();vartrianglestriangulator.Triangulate(terrainPoints);有限元分析// 生成结构网格MeshmeshnewMesh();Vector3[]verticesConvertTo3D(triangles);int[]trianglesIndicesGetTrianglesIndices(triangles);mesh.verticesvertices;mesh.trianglestrianglesIndices;参考代码 基于C#实现的使用逐点插入法生成Delaunay三角网剖分程序www.youwenfan.com/contentcsr/112316.html七、调试建议可视化调试使用Unity Gizmos绘制外接圆和边添加日志输出关键计算步骤异常处理try{// 三角剖分核心代码}catch(ArgumentExceptionex){Debug.LogError($输入点集无效:{ex.Message});}