[测绘]自动联结三角形网

yfy2003

自动联结三角形网是将平面上的离散点中最靠近的三点构成三角形，从而形成三角形网。在使用周围临近的离散点组成三角形时，应确保每个三角形都是锐角三角形或三边的长度近似相等，避免出现过大的钝角和过小的锐角。
确定第一个三角形
    首先要确定第一个三角形。设L为形成的三角形计数号，K为用来扩展的三角形的计数号，用V（L，1），V（L，2），V（L，3）分别表示为L号三角形的三个顶点编号。开始联结三角形时，设L=1，然后从N个离散点中找出左下角的点送入V（L，1）中，作为第一个三角形的第一个顶点，找出距离该点最近的点送入V（L，2）中，作为第一个三角形的第二个顶点，找出距离这两点连线中点最近而且不和这两点在一直线上的点送入V（L，3）中，作为第一个三角形的第三个顶点。
三角形的扩展
    利用计数器K、L来确保三角形中没有重复和交叉的三角形。在形成第一个三角形时，L=1，K=1，首先从K号三角形的第一边（V（L，1）、V（L，2））往外扩展，显然位于顶点V（L，3）同侧的点应排除，利用直线判断正负区的原理可以实现这一要求：
F（x,y）=y-Ax-B
A=(y2-y1)/(x2-x1)
B=(y1*x2-y2*x1)/(x2-x1)
很明显：
F(x,y)>0  观测点位于正区；
F(x,y)=0  观测点位于直线上；
F(x,y)<0  观测点位于负区；
将V（L，3）代入F(x,y)，记下F(x,y)值的符号，然后将其余的离散点代入F(x,y)，逐个比较值的符号，凡是同V（L，3）点的符号不同的点才具有被扩展使用的可能性。从这些点中挑选一点送入V（L，3）中（条件：三角形边角的余弦定理，如果该点与扩展边上的两点组成的角在所有形成的三角形中为最大，该点就作为三角形的第三个顶点送入V（L，3）中）。新的三角形基本形成，并使L=L+1。但为了避免重复和交叉，还要进行检查判断，方法是：利用三角形的任一边最多只能被二个三角形公用这一条件，进行全等比较。即要判断新组成的三角形的三条边是否已经被前面形成的三角形用过两次，如果是该三角形无效，则L=L-1，否则，该三角形成立。
    K号三角形的第一边扩展完后，就可转向其他二条边，继续重复上述扩展。当形成一个新的三角形时，必须使L=L+1。直到K号三角形的三边都扩展完。再转向K=K+1号三角形做扩展。
如何判断扩展终止
可以用两个条件检查：（1）、K=L，（2）、K号三角形的三条边都做完扩展工作。因为开始生成的三角形数L总是要大于要扩展的三角形数K，只有K=L时，表示不可能再有新的三角形生成，扩展工作结束。三角网就形成了。

topirol

多谢楼主的热心帮助！！！

chb801

好帖！

topirol

第一个三角形的v（l，1）是不是一定要左下角呢？左下角是不是指x+y最小的点呢？

我总是进行到一部分就停了，还有一个问题，v（）数组中定义V的上限是多少呢？也就是说n个点最多能组合多少个三角形呢？

yfy2003

topirol发表于2004-1-14 12:47:00第一个三角形的v（l，1）是不是一定要左下角呢？左下角是不是指x+y最小的点呢？

我总是进行到一部分就停了，还有一个问题，v（）数组中定义V的上限是多少呢？也就是说n个点最多能组合多少个

1、可以是左下角点，也可以是右上角点。
2、n个点最多能组合2*n-5个三角形。

topirol

看看我的程序，找不出问题出在哪里

topirol

我怀疑是这里出问题：

2. '确定第一个三角形
   
3.     '确定第一个顶点（最左）
   
4. 
   
5.     Dim sum_x_y As Double
   
6.    
   
7.     sum_x_y = X(1) + Y(1)
   
8.     v(1, 1) = 1
   
9.     For i = 2 To arrary_nub
   
10.     If (X(i) + Y(i)) < sum_x_y Then
    
11.     sum_x_y = X(i) + Y(i)
    
12.     v(1, 1) = i
    
13.     End If
    
14.     Next i
    
15. 
    
16.    
    
17.     '确定第二隔顶点（距离第一个顶点最近的点）
    
18.    
    
19.     v(1, 2) = search_min_dis(v(1, 1))'找出最近点
    
20.    
    
21.     '确定第三隔顶点（这两顶点连线中点最近而且不和这两点在一直线上的点）
    
22.     Dim tx As Double
    
23.     Dim Ty As Double
    
24.     Dim Tz As Double
    
25.     tx = (X(v(1, 1)) + X(v(1, 2))) / 2
    
26.     Ty = (Y(v(1, 1)) + Y(v(1, 2))) / 2
    
27.     Tz = (Z(v(1, 1)) + Z(v(1, 2))) / 2
    
28.     v(1, 3) = search_min_dis1(tx, Ty, Tz, v(1, 1), v(1, 2))’找出最近点，而且不在同一直线上
    
29.    
    
30. '三角形的扩展
    
31.     K = 1
    
32.     L = 1
    
33.     Dim index_v3 As Integer '记录扩展三角形的第三个顶点
    
34.     Do
    
35.       '扩展第1边n1-n2
    
36.      ProgressBar1.Value = ProgressBar1.Value + 1
    
37.       index_v3 = Search_Arc_Max(v(K, 1), v(K, 2), v(K, 3))
    
38.       
    
39.       If index_v3 <> 0 Then
    
40.       L = L + 1
    
41.       v(L, 1) = v(K, 1)
    
42.       v(L, 2) = v(K, 2)
    
43.       v(L, 3) = index_v3
    
44.       
    
45.       If Is_twice_used(L) Then’'判断该三角形3边是否被前面三角形用过2次
    
46.          L = L - 1
    
47.       End If
    
48.       End If
    
49.           '扩展第2边n2-n3
    
50. 
    
51.       index_v3 = Search_Arc_Max(v(K, 2), v(K, 3), v(K, 1))‘'找出与v(K, 2), v(K, 3)夹角 最大的点(跟v(K, 1)在不同区)
    
52.      
    
53.       If index_v3 <> 0 Then
    
54.       L = L + 1
    
55.       v(L, 1) = v(K, 2)
    
56.       v(L, 2) = v(K, 3)
    
57.       v(L, 3) = index_v3
    
58.       If Is_twice_used(L) Then
    
59.         L = L - 1
    
60.       End If
    
61.       End If
    
62.               '扩展第3边n1-n3
    
63. 
    
64.       index_v3 = Search_Arc_Max(v(K, 1), v(K, 3), v(K, 2))
    
65.      
    
66.       If index_v3 <> 0 Then
    
67.       L = L + 1
    
68.       v(L, 1) = v(K, 1)
    
69.       v(L, 2) = v(K, 3)
    
70.       v(L, 3) = index_v3
    
71.       If Is_twice_used(L) Then
    
72.         L = L - 1
    
73.       End If
    
74.       End If
    
75.       
    
76.       
    
77.       K = K + 1
    
78. 
    
79.     Loop Until K = L

'确定第一个三角形<br />     '确定第一个顶点（最左）<br /> <br />     Dim sum_x_y As Double<br />     <br />     sum_x_y = X(1) + Y(1)<br />     v(1, 1) = 1<br />     For i = 2 To arrary_nub<br />     If (X(i) + Y(i)) < sum_x_y Then<br />     sum_x_y = X(i) + Y(i)<br />     v(1, 1) = i<br />     End If<br />     Next i<br /> <br />    <br />     '确定第二隔顶点（距离第一个顶点最近的点）<br />     <br />     v(1, 2) = search_min_dis(v(1, 1))'找出最近点<br />     <br />     '确定第三隔顶点（这两顶点连线中点最近而且不和这两点在一直线上的点）<br />     Dim tx As Double<br />     Dim Ty As Double<br />     Dim Tz As Double<br />     tx = (X(v(1, 1)) + X(v(1, 2))) / 2<br />     Ty = (Y(v(1, 1)) + Y(v(1, 2))) / 2<br />     Tz = (Z(v(1, 1)) + Z(v(1, 2))) / 2<br />     v(1, 3) = search_min_dis1(tx, Ty, Tz, v(1, 1), v(1, 2))’找出最近点，而且不在同一直线上<br />     <br /> '三角形的扩展<br />     K = 1<br />     L = 1<br />     Dim index_v3 As Integer '记录扩展三角形的第三个顶点<br />     Do<br />       '扩展第1边n1-n2<br />      ProgressBar1.Value = ProgressBar1.Value + 1<br />       index_v3 = Search_Arc_Max(v(K, 1), v(K, 2), v(K, 3))<br />       <br />       If index_v3 <> 0 Then<br />       L = L + 1<br />       v(L, 1) = v(K, 1)<br />       v(L, 2) = v(K, 2)<br />       v(L, 3) = index_v3<br />       <br />       If Is_twice_used(L) Then’'判断该三角形3边是否被前面三角形用过2次<br />          L = L - 1<br />       End If<br />       End If<br />           '扩展第2边n2-n3<br /> <br />       index_v3 = Search_Arc_Max(v(K, 2), v(K, 3), v(K, 1))‘'找出与v(K, 2), v(K, 3)夹角 最大的点(跟v(K, 1)在不同区)<br />      <br />       If index_v3 <> 0 Then<br />       L = L + 1<br />       v(L, 1) = v(K, 2)<br />       v(L, 2) = v(K, 3)<br />       v(L, 3) = index_v3<br />       If Is_twice_used(L) Then<br />         L = L - 1<br />       End If<br />       End If<br />               '扩展第3边n1-n3<br /> <br />       index_v3 = Search_Arc_Max(v(K, 1), v(K, 3), v(K, 2))<br />      <br />       If index_v3 <> 0 Then<br />       L = L + 1<br />       v(L, 1) = v(K, 1)<br />       v(L, 2) = v(K, 3)<br />       v(L, 3) = index_v3<br />       If Is_twice_used(L) Then<br />         L = L - 1<br />       End If<br />       End If<br />       <br />       <br />       K = K + 1<br /> <br />     Loop Until K = L

myfreemind

好帖，楼主的帖总是让我获益匪浅，呵呵！送花一朵！

topirol

做好了，不过不知道是不是VB效率低的原因，好像比较慢

yfy2003

速度真快！
提个建议：加入角度或距离判断，这样周边的三角形就可以不连！