Construction_TIN核心代码
class Construction_TIN
{
//声明一个点列表和一个三角形列表对象
private PointList pointlist;
private TriangleList triangles;
//构造函数用于给以上声明的两个列表初始化
public Construction_TIN(PointList points)
{
this.pointlist = points;
this.triangles = new TriangleList();
}
//构建三角网
public TriangleList Triangle_const()
{
//当点数大于等于三个时再进行三角网构建
if (this.pointlist.Count < 3)
{
return null;
}
//点数超过两个个时，继续进行，第一步是生成超级三角形
//调用PointList类中的SuperTriangle方法，获取超三角形
//赋给Triangle的对象superTriangle
Triangle superTriangle = this.pointlist.SuperTriangle();
//将超三角形放入三角形集合（this.对象.泛型列表.对列表的操作）
this.triangles.triangleList.Add(superTriangle);
//定义超三角形顶点列表，仅用于装超三角形顶点
Point[] superpoints
= new Point[] { superTriangle.A, superTriangle.B, superTriangle.C };
//遍历点列表中所有点
for (int i = 0; i < this.pointlist.Count;i++ )
{
//将点列表中第i点赋给新点类对象
Point anewpoint = pointlist[i];
//定义边列表类对象
EdgeList edges = new EdgeList();
//遍历形成的每个三角形，找出点所在的三角形
for (int j = 0; j < triangles.Count;j++ )
{
//三角形列表对象（其外接圆包含插入点的三角形）
Triangle contain_triangle = triangles[j];
//当点在某个三角形（第j个）外接圆中
if(contain_triangle.IsInCirclecircle(anewpoint))
{
//将包含新插入点的三角形三条边插入边列表的末端
edges.edgeList.AddRange(new Edge []{contain_triangle.Edge1,contain_triangle.Edge2,contain_triangle.Edge3});
//在三角形列表中删除这个三角形
this.triangles.triangleList.Remove(contain_triangle);
//三角形列表减少一个，指针后退
j--;
}
}
//在边列表中删除重复边
edges.RemoveDiagonal();
//将新插点与所有边连接成三角形
for(int m=0;m<edges.Count;m++)
{
this.triangles.triangleList.Add(new Triangle(anewpoint, edges[m]));
}
}
// 遍历超级三角形的顶点，并删除超级三角形
foreach (Point sp_point in superpoints)
{
// 寻找包含超级三角形顶点的三角形，存入“被删三角形列表”
List<Triangle> rmvTriangles = this.triangles.FindByPoint(sp_point);
// 判断“被删三角形列表”是否为空
if (rmvTriangles != null)
{
// 遍历被删三角形集合
foreach (Triangle rmvTriangle in rmvTriangles)
{
// 移除被删三角形
this.triangles.Remove(rmvTriangle);
}
}
}
//返回三角形列表
return this.triangles;
}
}
点类和点列表类
1 class Point
2 {
3 //成员有两个——点的坐标
4 public float X { get; private set; }
5 public float Y { get; private set; }
6
7 //构造函数：初始化点的成员
8 public Point(float x, float y)
9 {
10 this.X = x;
11 this.Y = y;
12 }
13
14 //方法：判断两个点是否重合，重合返回true，否则返回false
15 public bool EqualPoints(Point newPoint)
16 {
17 const float tolerance = 0.00001f;
18 if (Math.Abs(this.X - newPoint.X) < tolerance && Math.Abs(this.Y - newPoint.Y) < tolerance)
19 {
20 return true;
21 }
22 return false;
23 }
24
25 }
26
27
28
29 //点列表的定义
30 class PointList
31 {
32 //泛型，定义点列表
33 public List<Point> pointList = new List<Point>();
34
35 //将第i个单个点存入点列表
36 public Point this[int i] { get { return pointList[i]; } }
37
38 //定义变量Count用于存储点列表长度
39 public int Count { get { return this.pointList.Count; } }
40
41 //遍历所有已经点过的点，获取超三角形
42 public Triangle SuperTriangle()
43 {
44 //定义四个变量，存储最大最小的横纵坐标值
45 float xmax = this.pointList[0].X;
46 float ymax = this.pointList[0].Y;
47
48 float xmin = this.pointList[0].X;
49 float ymin = this.pointList[0].Y;
50
51 //遍历获取最大最小坐标值
52 foreach (Point point in this.pointList)
53 {
54 if (point.X > xmax)
55 {
56 xmax = point.X;
57 }
58 if (point.Y > ymax)
59 {
60 ymax = point.Y;
61 }
62 if (point.X < xmin)
63 {
64 xmin = point.X;
65 }
66 if (point.Y < ymin)
67 {
68 ymin = point.Y;
69 }
70 }
71
72 //用获取的最大最小横纵坐标值定义超三角形的三个顶点坐标
73 //为保证能“包住”所有点，方法如此，不知怎么解释，不解释
74 float dx = xmax - xmin;
75 float dy = ymax - ymin;
76 float d = (dx > dy) ? dx : dy;
77
78 float xmid = (xmin + xmax)* 0.5f;
79 float ymid = (ymin + ymax) * 0.5f;
80
81 //用点类的构造函数定义超三角形三个顶点，并赋值
82 Point superTA = new Point(xmid, ymid + 2 * d);
83 Point superTB = new Point(xmid + 2 * d, ymid - d);
84 Point superTC = new Point(xmid - 2 * d, ymid - d);
85
86 //返回超三角形
87 //构造函数Triangle（PointA，PointB,PointC）定义在Triangle类中
88 return new Triangle(superTA, superTB, superTC);
89 }
90 }
边类和边列表类
1 class Edge
2 {
3 //边成员声明并初始化
4 public Point pa { get; private set; }
5 public Point pb { get; private set; }
6
7 //边类构造函数
8 public Edge(Point pa, Point pb)
9 {
10 this.pa = pa;
11 this.pb = pb;
12 }
13
14 //判断两条边是否相等（重合）
15 public bool EqualsEdge(Edge other)
16 {
17 if ((this.pa.Equals(other.pa) && this.pb.Equals(other.pb))
18 || (this.pa.Equals(other.pb) && this.pb.Equals(other.pa)))
19 {
20 return true;
21 }
22
23 return false;
24 }
25 }
26
27 //边列表
28 class EdgeList
29 {
30 //定义边列表
31 public List<Edge> edgeList = new List<Edge>();
32
33 public int Count { get { return this.edgeList.Count; } }
34
35 public Edge this[int i] { get { return this.edgeList[i] ; } }
36
37 //删除重合边，并将重合边在列表中的序号存入indexList列表
38 public void RemoveDiagonal()
39 {
40 List<int> indexList = new List<int>();
41
42 for (int i = 0; i < this.edgeList.Count; i++)
43 {
44 for (int j = i + 1; j < this.edgeList.Count;j++ )
45 {
46 if (this.edgeList[i].EqualsEdge(this.edgeList[j]))
47 {
48 indexList.Add(i);
49 indexList.Add(j);
50 break;
51 }
52
53 }
54 }
55 //排序
56 indexList.Sort();
57 //反序
58 indexList.Reverse();
59 //先删后画出的重合边
60 foreach (int i in indexList)
61 {
62 this.edgeList.RemoveAt(i);
63 }
64 }
65 }
三角形类及三角形列表类
1 class Triangle
2 {
3 //定义三角形类中点成员
4 public Point A { get; private set; }
5 public Point B { get; private set; }
6 public Point C { get; private set; }
7
8 //定义三角形类中的边成员
9 public Edge Edge1 { get; private set; }
10 public Edge Edge2 { get; private set; }
11 public Edge Edge3 { get; private set; }
12
13 //定义三角形外接圆及其半径平方
14 public float circumCirlecenterX;
15 public float circumCirlecenterY;
16 public double circumCirleRadius2;
17
18 //构造函数由点构成边，由点构成三角形
19 public Triangle(Point A, Point B, Point C)
20 {
21 this.A = A;
22 this.B = B;
23 this.C = C;
24
25 this.Edge1 = new Edge(A, B);
26 this.Edge2 = new Edge(B, C);
27 this.Edge3 = new Edge(C, A);
28 }
29
30 //构造函数“重载”，由点和边构成三角形
31 public Triangle(Point point, Edge edge)
32 : this(point, edge.pa, edge.pb)
33 {
34 }
35
36 //判断点是否在三角形外接圆内部
37 public bool IsInCirclecircle(Point Point)
38 {
39 //定义三角形顶点
40 float x1, x2, x3, y1, y2, y3;
41
42 //两点之间距离的平方
43 double dist2;
44 x1 = this.A.X;
45 y1 = this.A.Y;
46 x2 = this.B.X;
47 y2 = this.B.Y;
48 x3 = this.C.X;
49 y3 = this.C.Y;
50
51 //计算三角形外接圆圆心
52 circumCirlecenterX = ((y2 - y1) * (y3 * y3 - y1 * y1 + x3 * x3 - x1 * x1) - (y3 - y1) * (y2 * y2 - y1 * y1 + x2 * x2 - x1 * x1)) / (2 * (x3 - x1) * (y2 - y1) - 2 * ((x2 - x1) * (y3 - y1)));
53 circumCirlecenterY = ((x2 - x1) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1) - (x3 - x1) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1)) / (2 * (y3 - y1) * (x2 - x1) - 2 * ((y2 - y1) * (x3 - x1)));
54 //计算外接圆半径的平方
55 circumCirleRadius2
56 = Math.Pow(circumCirlecenterX - x1, 2)
57 + Math.Pow(circumCirlecenterY - y1, 2);
58 //计算外接圆圆心和插入点距离的平方
59 dist2
60 = Math.Pow(Point.X - circumCirlecenterX, 2)
61 + Math.Pow(Point.Y - circumCirlecenterY, 2);
62
63 //在外接圆内部返回真，否则返回假
64 if (dist2 <= circumCirleRadius2)
65 {
66 return true;
67 }
68 else
69 {
70 return false;
71 }
72 }
73
74 //判断某一个三角形三个顶点A、B、C是否与stPoint相等，
75 //有一个相等，则说明此三角形为包含超级三角形顶点的三角形,
76 //则返回真
77 internal bool ContainPoint(Point stPoint)
78 {
79 if (this.A.EqualPoints(stPoint) || this.B.EqualPoints(stPoint) || this.C.EqualPoints(stPoint))
80 {
81 return true;
82 }
83
84 return false;
85 }
86 }
87
88 class TriangleList
89 {
90 //定义三角形列表
91 public List<Triangle> triangleList = new List<Triangle>();
92
93 public Triangle this[int i] { get { return this.triangleList[i]; } }
94
95 public int Count { get { return this.triangleList.Count; } }
96
97
98 //返回包含超三角形顶点的三角形列表（除去重复的，不重复的返回）
99 internal List<Triangle> FindByPoint(Point stPoint)
100 {
101
102 List<Triangle> pTriangleList = new List<Triangle>();
103 //遍历三角形列表
104 foreach (Triangle triangle in triangleList)
105 {
106 //将包含超三角形顶点的三角形加入pTriangleList列表
107 if (triangle.ContainPoint(stPoint))
108 {
109 pTriangleList.Add(triangle);
110 }
111 }
112 //去掉重复三角形
113 //pTriangleList.Distinct();
114
115 return pTriangleList;
116 }
117
118 //删除列表的第一个三角形
119 internal void Remove(Triangle rmvTriangle)
120 {
121 triangleList.Remove(rmvTriangle);
122 }
123 }
124
Form1
1 public partial class TIN_Board : Form
2 {
3 public TIN_Board()
4 {
5 InitializeComponent();
6 }
7
8 //实例化一个点列表对象
9 PointList points = new PointList();
10
11 //定义一个三角形列表对象，并将三角形列表对象初始化为null，作为后续条件
12 TriangleList triangles=null;
13
14
15
16 //点击左键
17 private void panel_MouseDown(object sender, MouseEventArgs e)
18 {
19 //GDI+定义画图对象
20 Image map = new Bitmap(panel.Width, panel.Height) ;
21 Graphics g = Graphics.FromImage(map);
22 //画线对象
23 Pen linePen = new Pen(Color.Black, 2);
24 //画点对象
25 Pen pointPen = new Pen(Color.Red, 2);
26
27 //实例化点对象
28 Point newPoint = new Point(e.X, e.Y);
29 //将点对象加入点列表中
30 points.pointList.Add(newPoint);
31
32
33
34 //当点数大于三时，实例化对象并调构造函数，存入点，创建三角形
35 if (points.pointList.Count > 2)
36 {
37 Construction_TIN delaunay = new Construction_TIN(this.points);
38 //此时triangles不再是null
39 triangles = delaunay.Triangle_const();
40 }
41
42 //定义状态栏显示的三角形个数
43 if (triangles == null)
44 {
45 this.Triangle_Count.Text = "Triangles: 0";
46 }
47 else
48 {
49 this.Triangle_Count.Text = "Triangles: " + triangles.Count;
50 }
51
52 //遍历点列表，画点
53 for (int j = 0; j < points.Count; j++)
54 {
55 g.DrawEllipse(pointPen, points[j].X, points[j].Y, 2f, 2f);
56 }
57
58 //定义状态栏显示的三角形个数
59 this.Point_Count.Text = "Point: " + this.points.Count;
60
61 //如果三角形列表不为空，画出三角形的边
62 if (triangles != null)
63 {
64 for (int i = 0;i < triangles.Count;i++)
65 {
66 Triangle triangle = triangles[i];
67 g.DrawLine(linePen, triangle.Edge1.pa.X, triangle.Edge1.pa.Y, triangle.Edge1.pb.X, triangle.Edge1.pb.Y);
68 g.DrawLine(linePen, triangle.Edge2.pa.X, triangle.Edge2.pa.Y, triangle.Edge2.pb.X, triangle.Edge2.pb.Y);
69 g.DrawLine(linePen, triangle.Edge3.pa.X, triangle.Edge3.pa.Y, triangle.Edge3.pb.X, triangle.Edge3.pb.Y);
70 }
71 }
72
73 //返回给面板，重绘面板，用于显示
74 this.panel.BackgroundImage = map;
75
76 }
77
78
79
80 //点击清除按钮
81 private void Clear_btn_Click(object sender, EventArgs e)
82 {
83 //重新初始化点列表（清空点列表）
84 this.points = new PointList();
85 //清空背景图
86 this.panel.BackgroundImage = null;
87 //状态栏数值清零
88 this.Point_Count.Text = "Point: 0";
89 this.Triangle_Count.Text = "Triangles: 0";
90 }
91
92 //点击退出按钮
93 private void Exit_btn_Click(object sender, EventArgs e)
94 {
95 this.Close();
96 }
97
98 //鼠标移动事件
99 private void panel_MouseMove(object sender, MouseEventArgs e)
100 {
101 this.Coordinate.Text = e.X + " ," + e.Y;
102 }
103 }
这个是生成TIN三角网的C#程序。
超级新手头一次，写50行以上代码，在众多高手指引下调试完成。欢迎各位高手指正。帮忙改进。
（PS：最好白话一点，专业了我看不懂）