Delaunay三角剖分

2）public
{
List<Point_T> EnvelopeTin(List<Point_T> pts)//构建凸包
List<Point_T> envpts = new List<Point_T>(); List<Point_T> othpts = new List<Point_T>(); foreach (Point_T pt in pts) { othpts.Add(pt); } //构建以x-y，x+y最大最小值组成的初始矩形框 CompareXaddY comxandy = new CompareXaddY(); CompareXsubY comxsuby = new CompareXsubY(); pts.SoLeabharlann Baidut(comxsuby);
public Tin(Point_T p1, Point_T p2, Point_T p3) { pthree[0] = p1; pthree[1] = p2; pthree[2] = p3; lthree[0] = new Line_T(p1, p2); lthree[1] = new Line_T(p2, p3); lthree[2] = new Line_T(p3, p1); } }
Delauney 三角网剖分
算法原理：分为三步： 一、 凸包生成： 1） 求出如下四点： min(x-y)、 min(x+y)、 max(x-y)、 max(x+y)并顺次放入一个数组，组成初始凸包；2）对于凸包上的 点 I，设它的后续点为 J，计算矢量线段 IJ 右侧的所有点到 IJ 的距 离，求出距离最大的点 K；3）将 K 插入 I,J 之间，并将 K 赋给 J； 4）重复 2，3 步，直到点集中没有在 IJ 右侧的点为止；5）将 J 赋 给 I，J 取其后续点，重复 2，3，4 步，当遍历了一次凸包后，凸 包生成完成。 二、环切边界法凸包三角剖分：在凸包数组中，每次寻找一 个由相邻两条凸包边组成的三角形，在该三角形的内部和边界上 都不包含凸包上的任何其他点，然后去掉该点得到新的凸包链表， 重复这个过程，最终对凸包数组中的点进行三角剖分成功。 三、离散的内插：1）建立三角形的外接圆，找出外接圆包含 待插入点的所有三角形，构成插入区域；2）删除插入区域内的三 角形公共边，形成由影响三角形顶点构成的多边形；3）将插入点 与多边形所有顶点相连，构成新的 Delaunay 三角形；4）重复 1， 2，3，直到所有非凸包上的离散点都插入完为止。 功能实现流程： 并且在工具栏 1. 在绘图菜单栏下添加一个子菜单项为 Delauney， 上添加一个工具项。 设置 text 为 Delaunay 三角剖分， name 为 delaunay
over = false; } } } if (over) { i++; } else { //envpts.RemoveAt(i); envpts.Insert(i+1, othpts[tag]); over = true; } } return envpts; } public List<Tin> EnvelopeDivision(List<Point_T> pts)//凸包剖分 { List<Tin> envtins = new List<Tin>(); List<Point_T> cpts = new List<Point_T>(); foreach (Point_T pt in pts) { cpts.Add(pt); } while (cpts.Count > 2) { int tag = 0; double minangle = 120; for (int i = 0; i < cpts.Count; i++) { double angle; if (i == 0) { angle = CalcuAngle(cpts[cpts.Count - 1], cpts[i], cpts[i + 1]); } else if (i == cpts.Count - 1) { angle = CalcuAngle(cpts[i-1], cpts[i], cpts[0]); } else { angle = CalcuAngle(cpts[i-1], cpts[i], cpts[i + 1]);
} if ((angle - 60) < minangle) { minangle = angle - 60; tag = i; } } int btag=tag-1; int atag=tag+1; if (tag == 0) { btag = cpts.Count - 1; } else if (tag == cpts.Count - 1) { atag = 0; } Tin ctin = new Tin(cpts[btag], cpts[tag], cpts[atag]); envtins.Add(ctin); cpts.RemoveAt(tag); } return envtins; } public List<Tin> TinInsert(List<Tin> tins, List<Point_T> pts)//离散点内插 { List<Tin> deltins = new List<Tin>(); List<Tin> ctins = new List<Tin>();//临时凸包 foreach (Tin tin in tins) { ctins.Add(tin); } foreach (Point_T pt in pts)//对离散点遍历，内插 { List<Point_T> cpts = new List<Point_T>();//临时点集 foreach (Tin tin in ctins)//找到外接圆包含离散点的三角形 { Circle_T ccir = DelauneyCicle(tin);//构造外接圆 if (IsPointInCircle(pt, ccir))//点是否包含在圆内 { //for (int i = 0; i < 3; i++) //{ // if (!cpts.Contains(tin.Pthree[i]))
等属性，添加单击事件，并为单击事件代码 2.为事件函数添加如下代码
Graphics gra = panel1.CreateGraphics(); List<Point_T> pts = new List<Point_T>(); foreach (Geometry_T geo in choosegeos.Geofeatures) { if (geo.GetType() == typeof(Point_T)) { Point_T pt = (Point_T)geo; pts.Add(pt); } } List<Tin> deltins = DelauneyTin(pts);//根据多点构建delauney三角网 foreach (Tin tin in deltins) { Point[] ctin = new Point[3]; for (int i = 0; i < 3; i++) { cp = new Point((int)tin.Pthree[i].X, (int)tin.Pthree[i].Y); ctin[i] = cp; } gra.DrawPolygon(Pens.Red, ctin); }
List<Tin> deltins = new List<Tin>(); List<Point_T> envpts = EnvelopeTin(pts);//构建凸包 //for (int i = 0; i < envpts.Count - 1; i++) //{ // //} //gra.DrawLine(Pens.Black, new Point((int)envpts[0].X, (int)envpts[0].Y), new Point((int)envpts[envpts.Count - 1].X, (int)envpts[envpts.Count - 1].Y)); List<Point_T> dispts = new List<Point_T>();//非凸包上的离散点 foreach (Point_T pt in pts) { if (!envpts.Contains(pt)) { dispts.Add(pt); } } List<Tin> envtins = EnvelopeDivision(envpts);//凸包剖分 //foreach (Tin tin in envtins) //{ // // // // // // // //} deltins = TinInsert(envtins, dispts);//离散点内插 return deltins; } } gra.DrawPolygon(Pens.Blue, ctin); Point[] ctin = new Point[3]; for (int i = 0; i < 3; i++) { cp = new Point((int)tin.Pthree[i].X, (int)tin.Pthree[i].Y); ctin[i] = cp; gra.DrawLine(Pens.Black, new Point((int)envpts[i].X, (int)envpts[i].Y), new Point((int)envpts[i + 1].X, (int)envpts[i + 1].Y));
envpts.Add(pts[0]); envpts.Add(pts[pts.Count - 1]); othpts.Remove(pts[0]); othpts.Remove(pts[pts.Count-1]); pts.Sort(comxandy); if(!envpts.Contains(pts[0])) { envpts.Insert(1, pts[0]); } if (!envpts.Contains(pts[pts.Count - 1])) { envpts.Add(pts[pts.Count - 1]); } othpts.Remove(pts[0]); othpts.Remove(pts[pts.Count-1]); //构建以x-y，x+y最大最小值组成的初始矩形框 int i = 0; int tag = 0; bool over = true; while(i<envpts.Count) { Line_T cline; if (i==envpts.Count-1) { cline = new Line_T(envpts[i], envpts[0]); } else { cline = new Line_T(envpts[i], envpts[i + 1]); } double dismax=0; for (int j = 0; j < othpts.Count ;j++ ) { if (IsLeftPoint(othpts[j], cline)) { double distance = PointToLine(othpts[j], cline); if (distance > dismax) { dismax = distance; tag = j;
4.圆的数据结构
public class Circle_T:Geometry_T { private Point_T cpt; public Point_T Cpt { get { return cpt; } set { cpt = value; } } double radius; public double Radius { get { return radius; } set { radius = value; } } public Circle_T() { } public Circle_T(Point_T pt, double r) { cpt = pt; radius = r; } }
5.实现 Delaunay 三角剖分算法 1）
public List<Tin> DelauneyTin(List<Point_T> pts)//根据多点构建delauney三角网；
分三步：构建凸包；凸包剖分；离散点内插 { Graphics gra = panel1.CreateGraphics();
3．三角形 TIN 的数据结构
public class Tin { Point_T[] pthree = new Point_T[3]; Line_T[] lthree = new Line_T[3]; public Line_T[] Lthree { get { return lthree; } set { lthree = value; } } public Point_T[] Pthree { get { return pthree; } set { pthree = value; } } public Tin() { }