自来水管道连接规划模型
自来水管道连接规划模型
自来水管道连接规划问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
自来水管道连接规划模型
（一）摘要：自来水是人们日常生活中不可缺少的生活要素，我们分析自来水管道连接最优问题，即在自来水管道铺设过程中在绕开障碍物的前提下的最短路径问题，使自来水管道将各个供水点用最短路径链接。根据对目标点的数据进行筛选与分析，先用面积法排除障碍区域，再对剩余点采用Kruskal算法生成最优路的
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
。
初始给定的供水点中存在位于障碍区域中的点，需要采用合理的方法排除障碍区域中的点。本文将采用面积分析的方法，提供一种解决障碍区域判定的切实可行的方法，在二维坐标系上标定各点，障碍区域用由阴影覆盖的凸多边形
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
出，通过对点坐标之间的向量运算判定各点是否位于阴影区域，最终通过Matlab编程实现。
在确定并剔除障碍区中的点位后，采用Kruskal算法生成最优路径，对于通过阴影区域的线段，将其权值设定为无穷大，最终通过编程、绘图，给出管道最优连接方案，解决本问题。
最后我们对模型进行了整体评价，并提出改进之处。
（二）关键词：管道连接 面积法 障碍点筛选 最短路
Kruskal算法 权值 最小生成树
1. 问题重述
自来水是人们日常生活中不可缺少的生活要素，然而自来水管网的组建却有很多问题需要解决。一般来说，我们假设管网中任意两个用户之间存在直线段相连，但是在连接过程中，有些区域是必须绕开的，这些必须绕开的区域我们称为障碍区域。
表1给出了若干个可能的用户的地址的横纵坐标，可能的用户的含义是：如果用户的地址不在障碍区域内，那么该用户就是需要使用自来水的用户（即有效用户），否则如果用户的地址在障碍区域内，那么该用户就是无效用户（即不要将该用户连接在网络中）。
表2-表5是分别是4个障碍区域必须要覆盖的点的坐标，而对应障碍区域就是覆盖这些要覆盖的点的最小凸集。
(1) 请您判定表1中那些用户为有效用户。
(2) 请设计算法筛选有效用户之间的有效线段。
(3)请设计一个算法将有效用户用有效线段连接起来，并且连接的距离总和最小。
表1（见附录一）
表2障碍区域1必须要覆盖的点的坐标
顶点序号
顶点的横坐标
顶点的纵坐标
1
3.2060
12.9166
2
17.4571
19.3377
3
4.7576
20
表3障碍区域2必须要覆盖的点的坐标
顶点序号
顶点的横坐标
顶点的纵坐标
1
50
30
2
53.7465
48.4490
3
46.9222
57.1195
4
33.3207
39.8050
5
43.1123
56.3187
表4障碍区域3必须要覆盖的点的坐标
顶点序号
顶点的横坐标
顶点的纵坐标
1
54.6982
70
2
53.7465
90
3
46.9222
80
表5障碍区域4必须要覆盖的点的坐标
顶点序号
顶点的横坐标
顶点的纵坐标
1
90
75
2
80
95
3
70
80
二．模型假设
1， 用户之间以直线连接;
2， 障碍区中的用户可以忽略，认为是无效用户；
3， 以管道总距离最小为目的；
4， 障碍区域是障碍顶点围成的凸多边形区域；
5， 在非障碍区用户之间可确保用直线连接，且直线不通过障碍区域；
三．符号说明
表6 论文符号说明
符号
表示对象
A
用户点的坐标
B
障碍区1的各顶点坐标
C
障碍区2的各顶点坐标
D
障碍区3的各顶点坐标
E
障碍区4的各顶点坐标
SIGN
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
各用户点是否在障碍区，若在对应位置记为1；若不在，则对应位置记为0
OUTSIGN
无效用户点的序号
N
有效用户点的个数
NUM
记录任意两用户点之间可用线段连接起来且不过障碍区的线段
DIS
连接的长度
M
最小生成树的点以及连接的信息
sum
最小生成树管道的总长
四．问题分析
先排除障碍区域。如果用户点位于凸边型障碍物之外，则为有效用户，否则为无效用户。再将任意两个有效用户连接，如果连接通过障碍区域之内，则为无效线段。最后通过有效点和有效连接生成最小生成树，并且连接有效用户点，画出连接路线图形，并计算生成树所成长度。根据对模型的合理假设，障碍区域即为已知若干障碍区顶点围成的凸多边形，故解决此问题的关键在于在已建立的二维坐标系中，寻找到一种合理的算法能够判定出点是否位于障碍区域中。通过直观判断，阴影区域的构成由表7给出：
表7 障碍区域构成
障碍区域编号
构成
1
由3个无效用户坐标点围成的三角形
2
由5个无效用户坐标点围成的凸五边形
3
由3个无效用户坐标点围成的三角形
4
由3个无效用户坐标点围成的三角形
运用面积法进行筛选点，对所有点进行筛选，找到并排除障碍区域中的无效用户，
再把任意两个有效用户点之间用线段连接，运用向量法设计筛选线段的程序，筛选出所有不过障碍区的线段。
最后设计程序，将所有有效用户点连接起来，并使管道总距离最小。这是一个典型的最小生成树问题，但相较以往最小生成树问题又有着其特别之处，以往的无障碍的情况下只需要使用弗洛伊德算法即可。但因为障碍区域的干扰，这使得坐标系并非是一个连通区域，该无法直接使用。这就需要我们在对问题进行合理假设的前提下，对已有算法进行改良。我们通过对穿过障碍区的线段赋权值为无穷大的方法，利用Kruskal算法，生成最优路径。
五．模型的建立与求解：
5.1.问题一的模型建立和求解
5.1.1运用向量的方法求解障碍区面积S
若障碍区是三角形，对应各顶点坐标分别为(x1,y1)，(x2,y2), (x3,y3)。则a=(x2-x1,y2-y1),b=(x3-x1,y3-y1)。由于三角形面积S=|a|*|b|*sin
/2,向量a,b外积的模长|a×b|=|a|*|b|*sin;则有S=|a×b|/2;
若障碍区为五边形，对应点为(x1,y1)，(x2,y2), (x3,y3), (x4,y4)，(x5,y5)。则划分成三个三角形，各三角形的顶点分别为(x1,y1)，(x2,y2), (x3,y3)；(x3,y3), (x4,y4)，(x5,y5)；(x1,y1)，(x3,y3), (x5,y5)。再用求三角形面积的方法求解即可。
5.1.2求用户点与任意两个同一障碍区的顶点构成三角形的面积之和S1
5.1.3判断有效用户
如果S=S1，则该用户在障碍区内，为无效用户。反之为有效用户。则筛选完毕的结果如下：
在障碍区的点的序号分别为：4 23 36 99。
无效用户的信息为：(4.0000,48.5982,33.3951);(23.0000,81.3166,87.4367); (36.0000,41.8649,41.1953); (99.0000,6.4781,17.0793);
有效用户的个数是：96。
100个点是否在障碍区的情况如下图：
5.2连接有效用户
求出过任意两个有效用户点的直线m与过各障碍区中任意两个顶点的直线L的交点坐标，再运用向量法判断该交点是否在以上述两有效用户点为端点上的线段m1和以上述障碍区顶点为端点的线段L1上，然后判断过该两个有效用户点的连接是否有效。
5.2.1运用矩阵的方法求解两直线之间的交点坐标
如果任意两个有效用户点的坐标分别为A(x1,y1)、B(x2,y2)，同一障碍区任意两个顶点坐标为M(x3,y3)、N(x4,y4)。则两直线方程分别为：
（1）
（2）；
则由解线性方程组的方法有
，线性方程组的的系数矩阵为：
；
；
在运用Matlab求解该线性方程组时，不妨把
分别设为：
可以求得
=A\
。
5.2.2判断线段是否为有效线段
若求得的交点坐标为P(x,y)，则通过向量关系PM=
PN,可以求的
。若
EMBED Equation.DSMT4 0,则该线段为有效线段；若
<0,则要考虑向量关系PA=
PB,若
EMBED Equation.DSMT4 0，则该线段为有效线段，否则，该线段为无效线段。
5.3问题三的模型建立与求解
若要在N个用户之间连接自来水管道，由于每一个用户与其余N-1个用户之间都可能连接自来水管道。因此，在N个用户之间，最多可能连接N(N-1)/2条自来水管道然而，在连接N个用户之间的管道时，最少只需连接N-1条管道。也就是说只需要N-1条管道线路就可以把N个用户之间的自来水管道连通。现在要考虑在连接N个用户的自来水管道的同时要保证所有的管道长度之和最短，这就涉及了最优化的问题。利用Kruskal算法
思想
教师资格思想品德鉴定表下载浅论红楼梦的主题思想员工思想动态调查问卷论语教育思想学生思想教育讲话稿
设计Matlab程序进行最小生成树所需边的筛选,并且设计算法将筛选出来的构成最小生成树的各边连接起来，求出最短路径长度，并画出连接图形。
5.3.1利用Kruskal算法思想求解最小生成树
设计96个用户之间的带权图，并作出邻接矩阵DIS,再根据求得的有效线段与无效线段对邻接矩阵进行修改，将邻接矩阵中对应无效线段的位置的值修改为inf，可以得到一个新的邻接矩阵DIS。
接下来，用冒泡排序法对所有有效线段长度按从小到大的顺序进行排序。这时，需要借助Kruskal算法进行最小生成树的计算。然后把最小生成树对应边的线段长度、起点、终点信息记录在矩阵EE中。
生成最小生成树时，从长度最短的边开始选取。首先不妨设一个1×96的标记向量l用于记录被选取的点的序号，初始状态向量l的各元素依次为各用户序号，在选取线段为边后，将对应两点的序号m与n取最小值，并将向量l中所有与m位置元素相等的元素位置及所有与n位置的元素相等的元素位置都赋值为该最小值，如此循环知道向量l中所有元素均相等时停止；同时可以设一向量R来依次记录被选点的序号，直到所有用户点被无重复地被记录。在按线段长度从小到大的顺序选择边时，设线段端点用户的序号为m与n。这时需要考虑如下4种情况：
<1>如果在向量R中m和n均没有被记录,则该线段可以被选为最小生成树的边，将对应线段的信息记录在矩阵EE中，同时在R中添加记录m和n的值，并按照上述步骤更新向量l。
<2>如果在向量R中m被记录而n没有被记录，则该线段可以被选为最小生成树的边，将对应线段的信息记录在矩阵M中，同时在R中添加记录n的值，并按照上述步骤更新向量l。
<3>如果在向量R中n被记录而m没有被记录，则该线段可以被选为最小生成树的边，将对应线段的信息记录在矩阵EE中，同时在R中添加记录m的值，并按照上述步骤更新向量l。
<4>如果在向量R中m和n均被记录,则需要借助向量l来判断是否该线段可以被选为最小生成树的边：
a. 如果向量l中对应的m位置与n位置的元素值相等，则该线段不是最小生成树的边，直接跳过到下一步判断。
b. 如果向量l中对应的m位置与n位置的元素值不相等，则该线段是最小生成树的边，将对应线段的信息记录在矩阵M中，同时只需要更新向量l。
通过上述方法，即可产生最小生成树，其各边信息记录在矩阵M中。
5.3.2设计Matlab程序求出最小生成树长度并将各边连接起来
要计算最小生成树的长度，只需要借助for循环将M矩阵中记录长度相加即可。具体算发如下：
sum=0;
for i=1:p-1
sum=sum+M(1,i);
end
sum
可以求得最小生成树的长度为：sum= 653.0196；
最后，借助plot函数画出最小生成树的图形。算法如下：
hold on;
for i=1:100
x=A(i,2);
y=A(i,3);
plot(x,y,'o')
end
for i=1:n-1
x1=AL(M(2,i),2);
y1=AL(M(2,i),3);
x2=AL(M(3,i),2);
y2=AL(M(3,i),3);
X=[x1,x2];
Y=[y1,y2];
plot(X,Y)
end
for i=1:3
x1=B(i,2);
y1=B(i,3);
x2=B(mod(i,3)+1,2);
y2=B(mod(i,3)+1,3);
X=[x1,x2];
Y=[y1,y2];
plot(X,Y,'m')
end
for i=1:5
x1=C(i,2);
y1=C(i,3);
x2=C(mod(i,5)+1,2);
y2=C(mod(i,5)+1,3);
X=[x1,x2];
Y=[y1,y2];
plot(X,Y,'m')
end
for i=1:3
x1=D(i,2);
y1=D(i,3);
x2=D(mod(i,3)+1,2);
y2=D(mod(i,3)+1,3);
X=[x1,x2];
Y=[y1,y2];
plot(X,Y,'m')
end
for i=1:3
x1=E(i,2);
y1=E(i,3);
x2=E(mod(i,3)+1,2);
y2=E(mod(i,3)+1,3);
X=[x1,x2];
Y=[y1,y2];
plot(X,Y,'m')
end
连接形成的最小生成树的图形如下图所示：
由图可知，该最小生成数是合理的。
六．模型检验
首先可以通过对所画最小生成树图形的观察，看是否有回路，由图易知图形中无回路，则通过修改最小生成树中任意边的连接，计算修改后的最小生成树的长度sum’与sum进行比较。可得sum’>sum,则该模型所生成的最小生成树的长度最短，即运用该模型进行自来水管道的连接所需要的自来水管长度最短。
十．附录
附录：
若干个可能的用户的地址的横纵坐标
可能的用户的序号
可能的用户横坐标
可能的用户纵坐标
1.0000
95.0129
58.2792
2.0000
23.1139
42.3496
3.0000
60.6843
51.5512
4.0000
48.5982
33.3951
5.0000
89.1299
43.2907
6.0000
76.2097
22.5950
7.0000
45.6468
57.9807
8.0000
1.8504
76.0365
9.0000
82.1407
52.9823
10.0000
44.4703
64.0526
11.0000
61.5432
20.9069
12.0000
79.1937
37.9818
13.0000
92.1813
78.3329
14.0000
73.8207
68.0846
15.0000
17.6266
46.1095
16.0000
40.5706
56.7829
17.0000
93.5470
79.4211
18.0000
91.6904
5.9183
19.0000
41.0270
60.2869
20.0000
89.3650
5.0269
21.0000
5.7891
41.5375
22.0000
35.2868
30.4999
23.0000
81.3166
87.4367
24.0000
0.9861
1.5009
25.0000
13.8891
76.7950
26.0000
20.2765
97.0845
27.0000
19.8722
99.0083
28.0000
60.3792
78.8862
29.0000
27.2188
43.8659
30.0000
19.8814
49.8311
31.0000
1.5274
21.3963
32.0000
74.6786
64.3492
33.0000
44.5096
32.0036
34.0000
93.1815
96.0099
35.0000
46.5994
72.6632
36.0000
41.8649
41.1953
37.0000
84.6221
74.4566
38.0000
52.5152
26.7947
39.0000
20.2647
43.9924
40.0000
67.2137
93.3380
41.0000
83.8118
68.3332
42.0000
1.9640
21.2560
43.0000
68.1277
83.9238
44.0000
37.9481
62.8785
45.0000
83.1796
13.3773
46.0000
50.2813
20.7133
47.0000
70.9471
60.7199
48.0000
42.8892
62.9888
49.0000
30.4617
37.0477
50.0000
18.9654
57.5148
51.0000
19.3431
45.1425
52.0000
68.2223
4.3895
53.0000
30.2764
2.7185
54.0000
54.1674
31.2685
55.0000
15.0873
1.2863
56.0000
69.7898
38.3967
57.0000
37.8373
68.3116
58.0000
86.0012
9.2842
59.0000
85.3655
3.5338
60.0000
59.3563
61.2395
61.0000
49.6552
60.8540
62.0000
89.9769
1.5760
63.0000
82.1629
1.6355
64.0000
64.4910
19.0075
65.0000
81.7974
58.6918
66.0000
66.0228
5.7581
67.0000
34.1971
36.7568
68.0000
28.9726
63.1451
69.0000
34.1194
71.7634
70.0000
53.4079
69.2669
71.0000
72.7113
8.4079
72.0000
30.9290
45.4355
73.0000
83.8496
44.1828
74.0000
56.8072
35.3250
75.0000
37.0414
15.3606
76.0000
70.2740
67.5645
77.0000
54.6571
69.9213
78.0000
44.4880
72.7509
79.0000
69.4567
47.8384
80.0000
62.1310
55.4842
81.0000
79.4821
12.1047
82.0000
95.6843
45.0754
83.0000
52.2590
71.5883
84.0000
88.0142
89.2842
85.0000
17.2956
27.3102
86.0000
97.9747
25.4769
87.0000
27.1447
86.5603
88.0000
25.2329
23.2350
89.0000
87.5742
80.4872
90.0000
73.7306
90.8398
91.0000
13.6519
23.1894
92.0000
1.1757
23.9313
93.0000
89.3898
4.9754
94.0000
19.9138
7.8384
95.0000
29.8723
64.0815
96.0000
66.1443
19.0887
97.0000
28.4409
84.3869
98.0000
46.9224
17.3900
99.0000
6.4781
17.0793
100.0000
98.8335
99.4295
附录三：
解决该自来水管道连接问题的Matlab程序：
%问题一，进行有效点的筛选
A=[1.0000 95.0129 58.2792;
2.0000 23.1139 42.3496;
3.0000 60.6843 51.5512;
4.0000 48.5982 33.3951;
5.0000 89.1299 43.2907;
6.0000 76.2097 22.5950;
7.0000 45.6468 57.9807;
8.0000 1.8504 76.0365;
9.0000 82.1407 52.9823;
10.0000 44.4703 64.0526;
11.0000 61.5432 20.9069;
12.0000 79.1937 37.9818;
13.0000 92.1813 78.3329;
14.0000 73.8207 68.0846;
15.0000 17.6266 46.1095;
16.0000 40.5706 56.7829;
17.0000 93.5470 79.4211;
18.0000 91.6904 5.9183;
19.0000 41.0270 60.2869;
20.0000 89.3650 5.0269;
21.0000 5.7891 41.5375;
22.0000 35.2868 30.4999;
23.0000 81.3166 87.4367;
24.0000 0.9861 1.5009;
25.0000 13.8891 76.7950;
26.0000 20.2765 97.0845;
27.0000 19.8722 99.0083;
28.0000 60.3792 78.8862;
29.0000 27.2188 43.8659;
30.0000 19.8814 49.8311;
31.0000 1.5274 21.3963;
32.0000 74.6786 64.3492;
33.0000 44.5096 32.0036;
34.0000 93.1815 96.0099;
35.0000 46.5994 72.6632;
36.0000 41.8649 41.1953;
37.0000 84.6221 74.4566;
38.0000 52.5152 26.7947;
39.0000 20.2647 43.9924;
40.0000 67.2137 93.3380;
41.0000 83.8118 68.3332;
42.0000 1.9640 21.2560;
43.0000 68.1277 83.9238;
44.0000 37.9481 62.8785;
45.0000 83.1796 13.3773;
46.0000 50.2813 20.7133;
47.0000 70.9471 60.7199;
48.0000 42.8892 62.9888;
49.0000 30.4617 37.0477;
50.0000 18.9654 57.5148;
51.0000 19.3431 45.1425;
52.0000 68.2223 4.3895;
53.0000 30.2764 2.7185;
54.0000 54.1674 31.2685;
55.0000 15.0873 1.2863;
56.0000 69.7898 38.3967;
57.0000 37.8373 68.3116;
58.0000 86.0012 9.2842;
59.0000 85.3655 3.5338;
60.0000 59.3563 61.2395;
61.0000 49.6552 60.8540;
62.0000 89.9769 1.5760;
63.0000 82.1629 1.6355;
64.0000 64.4910 19.0075;
65.0000 81.7974 58.6918;
66.0000 66.0228 5.7581;
67.0000 34.1971 36.7568;
68.0000 28.9726 63.1451;
69.0000 34.1194 71.7634;
70.0000 53.4079 69.2669;
71.0000 72.7113 8.4079;
72.0000 30.9290 45.4355;
73.0000 83.8496 44.1828;
74.0000 56.8072 35.3250;
75.0000 37.0414 15.3606;
76.0000 70.2740 67.5645;
77.0000 54.6571 69.9213;
78.0000 44.4880 72.7509;
79.0000 69.4567 47.8384;
80.0000 62.1310 55.4842;
81.0000 79.4821 12.1047;
82.0000 95.6843 45.0754;
83.0000 52.2590 71.5883;
84.0000 88.0142 89.2842;
85.0000 17.2956 27.3102;
86.0000 97.9747 25.4769;
87.0000 27.1447 86.5603;
88.0000 25.2329 23.2350;
89.0000 87.5742 80.4872;
90.0000 73.7306 90.8398;
91.0000 13.6519 23.1894;
92.0000 1.1757 23.9313;
93.0000 89.3898 4.9754;
94.0000 19.9138 7.8384;
95.0000 29.8723 64.0815;
96.0000 66.1443 19.0887;
97.0000 28.4409 84.3869;
98.0000 46.9224 17.3900;
99.0000 6.4781 17.0793;
100.0000 98.8335 99.4295
];
B=[1 3.2060 12.9166;
2 17.4571 19.3377;
3 4.7576 20
];
C=[1 50 30;
2 53.7465 48.4490;
3 46.9222 57.1195;
5 43.1123 56.3187;
4 33.3207 39.8050
];
D=[1 54.6982 70;
2 53.7465 90;
3 46.9222 80
];
E=[1 90 75;
2 80 95;
3 70 80
];%准备用户坐标矩阵和障碍区坐标矩阵
SIGN=zeros(1,100);%生成1行100列的记录矩阵，若点不在障碍区则对应位置记为
1，否则记为0
for n=1:100
a1=[B(2,2)-B(1,2),B(2,3)-B(1,3),0];
a2=[B(3,2)-B(2,2),B(3,3)-B(2,3),0];
a3=[B(1,2)-B(3,2),B(1,3)-B(3,3),0];
S=norm(cross(a1,a2))/2;%该障碍区面积
x=A(n,2);
y=A(n,3);
z1=[x-B(1,2),y-B(1,3),0];
z2=[x-B(2,2),y-B(2,3),0];
z3=[x-B(3,2),y-B(3,3),0];
s1=norm(cross(z1, a1))/2;
s2=norm(cross(z2, a2))/2;
s3=norm(cross(z3, a3))/2;
S1=s1+s2+s3;%由用户点和任意对应两个该障碍区顶点构成的三角形面积之和
if(S1==S)m1=0 ;
else m1=1;
end
%第一个障碍区内的点判断
b1=[C(2,2)-C(1,2),C(2,3)-C(1,3),0];
b2=[C(3,2)-C(2,2),C(3,3)-C(2,3),0];
b3=[C(4,2)-C(3,2),C(4,3)-C(3,3),0];
b4=[C(5,2)-C(4,2),C(5,3)-C(4,3),0];
b5=[C(1,2)-C(5,2),C(1,3)-C(5,3),0];
s1=norm(cross(b1,b2))/2;
s2=norm(cross(b3,b4))/2;
s3=norm(cross(b1+b2,b3+b4))/2;
S=s1+s2+s3;%该障碍区面积
x=A(n,2);
y=A(n,3);
z1=[x-C(1,2),y-C(1,3),0];
z2=[x-C(2,2),y-C(2,3),0];
z3=[x-C(3,2),y-C(3,3),0];
z4=[x-C(4,2),y-C(4,3),0];
z5=[x-C(5,2),y-C(5,3),0];
s1=norm(cross(z1,b1))/2;
s2=norm(cross(z2,b2))/2;
s3=norm(cross(z3,b3))/2;
s4=norm(cross(z4,b4))/2;
s5=norm(cross(z5,b5))/2;
S1=s1+s2+s3+s4+s5;%由用户点和任意对应两个该障碍区顶点构成的三角形面积之
和
if(S1==S)m2=0;
else m2=1;
end%第二个障碍区内的点判断
c1=[D(2,2)-D(1,2),D(2,3)-D(1,3),0];
c2=[D(3,2)-D(2,2),D(3,3)-D(2,3),0];
c3=[D(1,2)-D(3,2),D(1,3)-D(3,3),0];
S=norm(cross(c1,c2))/2;%该障碍区面积
x=A(n,2);
y=A(n,3);
z1=[x-D(1,2),y-D(1,3),0];
z2=[x-D(2,2),y-D(2,3),0];
z3=[x-D(3,2),y-D(3,3),0];
s1=norm(cross(c1,z1))/2;
s2=norm(cross(c2,z2))/2;
s3=norm(cross(c3,z3))/2;
S1=s1+s2+s3;%由用户点和任意对应两个该障碍区顶点构成的三角形面积之和
if(S1==S)m3=0;
else m3=1;
end%第三个障碍区内的点判断
d1=[E(2,2)-E(1,2),E(2,3)-E(1,3),0];
d2=[E(3,2)-E(2,2),E(3,3)-E(2,3),0];
d3=[E(1,2)-E(3,2),E(1,3)-E(3,3),0];
S=norm(cross(d1,d2))/2;%该障碍区面积
x=A(n,2);
y=A(n,3);
z1=[x-E(1,2),y-E(1,3),0];
z2=[x-E(2,2),y-E(2,3),0];
z3=[x-E(3,2),y-E(3,3),0];
s1=norm(cross(d1,z1))/2;
s2=norm(cross(d2,z2))/2;
s3=norm(cross(d3,z3))/2;
S1=s1+s2+s3;%由用户点和任意对应两个该障碍区顶点构成的三角形面积之和
if(S1==S)m4=0 ;
else m4=1;
end%第四个障碍区内的点判断
if(m1&m2&m3&m4)SIGN(n)=1;
else SIGN(n)=0;
end
end
SIGN ;
%以上判断不在障碍区的点，其标号记录在SIGN矩阵中用1表示
OUTSIGN=find(SIGN==0)
%记录在障碍区的用户点
p=0;
for i=1:100
p=p+SIGN(i);
end
p
%计算保留用户点的个数p
%问题二，进行有效线段的筛选
NUM=zeros(100,100);
for i=1:100
for j=i+1:100
NUM(i,j)=1;
end
end
b1=(B(1,3)-B(2,3))/(B(1,2)-B(2,2));
bb1=(B(1,3)*B(2,2)-B(1,2)*B(2,3))/(B(1,2)-B(2,2));
b2=(B(2,3)-B(3,3))/(B(2,2)-B(3,2));
bb2=(B(2,3)*B(3,2)-B(2,2)*B(3,3))/(B(2,2)-B(3,2));
b3=(B(3,3)-B(1,3))/(B(3,2)-B(1,2));
bb3=(B(3,3)*B(1,2)-B(3,2)*B(1,3))/(B(3,2)-B(1,2));
BB=[b1 bb1;b2 bb2;b3 bb3];
c1=(C(1,3)-C(2,3))/(C(1,2)-C(2,2));
cc1=(C(1,3)*C(2,2)-C(1,2)*C(2,3))/(C(1,2)-C(2,2));
c2=(C(2,3)-C(3,3))/(C(2,2)-C(3,2));
cc2=(C(2,3)*C(3,2)-C(2,2)*C(3,3))/(C(2,2)-C(3,2));
c3=(C(3,3)-C(4,3))/(C(3,2)-C(4,2));
cc3=(C(3,3)*C(4,2)-C(3,2)*C(4,3))/(C(3,2)-C(4,2));
c4=(C(4,3)-C(5,3))/(C(4,2)-C(5,2));
cc4=(C(4,3)*C(5,2)-C(4,2)*C(5,3))/(C(4,2)-C(5,2));
c5=(C(5,3)-C(1,3))/(C(5,2)-C(1,2));
cc5=(C(5,3)*C(1,2)-C(5,2)*C(1,3))/(C(5,2)-C(1,2));
CC=[c1 cc1;c2 cc2;c3 cc3;c4 cc4;c5 cc5];
d1=(D(1,3)-D(2,3))/(D(1,2)-D(2,2));
dd1=(D(1,3)*D(2,2)-D(1,2)*D(2,3))/(D(1,2)-D(2,2));
d2=(D(2,3)-D(3,3))/(D(2,2)-D(3,2));
dd2=(D(2,3)*D(3,2)-D(2,2)*D(3,3))/(D(2,2)-D(3,2));
d3=(D(3,3)-D(1,3))/(D(3,2)-D(1,2));
dd3=(D(3,3)*D(1,2)-D(3,2)*D(1,3))/(D(3,2)-D(1,2));
DD=[d1 dd1;d2 dd2;d3 dd3];
e1=(E(1,3)-E(2,3))/(E(1,2)-E(2,2));
ee1=(E(1,3)*E(2,2)-E(1,2)*E(2,3))/(E(1,2)-E(2,2));
e2=(E(2,3)-E(3,3))/(E(2,2)-E(3,2));
ee2=(E(2,3)*E(3,2)-E(2,2)*E(3,3))/(E(2,2)-E(3,2));
e3=(E(3,3)-E(1,3))/(E(3,2)-E(1,2));
ee3=(E(3,3)*E(1,2)-E(3,2)*E(1,3))/(E(3,2)-E(1,2));
EE=[e1 ee1;e2 ee2;e3 ee3];
for i=1:100
for j=i+1:100
x1=A(i,2);
y1=A(i,3);
x2=A(j,2);
y2=A(j,3);
a=(y1-y2)/(x1-x2);
b=(y1*x2-x1*y2)/(x1-x2);
for k=1:3
M=[a -1;BB(k,1) -1];
N=[b 0;BB(k,2) 0];
if(det(M)~=0)
P=M\N;
x=P(1,1);
y=P(2,1);
M1=[x-B(k,2) y-B(k,3)];
N1=[x-B(mod(k,3)+1,2) y-B(mod(k,3)+1,3)];
m=M1/N1;
aa=[x-x1,y-y1];
bb=[x-x2,y-y2];
if(xor(aa(1),bb(1))|xor(aa(1),bb(1)))mm=0;
else mm=aa/bb;
end
if(m<0)
if(mm<0)
NUM(i,j)=NUM(i,j)*0;
else NUM(i,j)=NUM(i,j)*1;
end
else NUM(i,j)=NUM(i,j)*1;
end
end
end
for k=1:5
M=[a -1;CC(k,1) -1];
N=[b 0;CC(k,2) 0];
if(det(M)~=0)
P=M\N;
x=P(1,1);
y=P(2,1);
M1=[x-C(k,2) y-A(k,3)];
N1=[x-C(mod(k,5)+1,2) y-C(mod(k,5)+1,3)];
m=M1/N1;
aa=[x-x1,y-y1];
bb=[x-x2,y-y2];
if(xor(aa(1),bb(1))|xor(aa(1),bb(1)))mm=0;
else mm=aa/bb;
end
if(m<0)
if(mm<0)NUM(i,j)=NUM(i,j)*0;
else NUM(i,j)=NUM(i,j)*1;
end
else NUM(i,j)=NUM(i,j)*1;
end
end
end
for k=1:3
M=[a -1;DD(k,1) -1];
N=[b 0;DD(k,2) 0];
if(det(M)~=0)
P=M\N;
x=P(1,1);
y=P(2,1);
M1=[x-D(k,2) y-D(k,3)];
N1=[x-D(mod(k,3)+1,2) y-D(mod(k,3)+1,3)];
m=M1/N1;
aa=[x-x1,y-y1];
bb=[x-x2,y-y2];
if(xor(aa(1),bb(1))|xor(aa(1),bb(1)))mm=0;
else mm=aa/bb;
end
if(m<0)
if(mm<0)NUM(i,j)=NUM(i,j)*0;
else NUM(i,j)=NUM(i,j)*1;
end
else NUM(i,j)=NUM(i,j)*1;
end
end
end
for k=1:3
M=[a -1;EE(k,1) -1];
N=[b 0;EE(k,2) 0];
if(det(M)~=0)
P=M\N;
x=P(1,1);
y=P(2,1);
M1=[x-E(k,2) y-E(k,3)];
N1=[x-E(mod(k,3)+1,2) y-E(mod(k,3)+1,3)];
m=M1/N1;
aa=[x-x1,y-y1];
bb=[x-x2,y-y2];
if(xor(aa(1),bb(1))|xor(aa(1),bb(1)))mm=0;
else mm=aa/bb;
end
if(m<0)
if(mm<0)NUM(i,j)=NUM(i,j)*0;
else NUM(i,j)=NUM(i,j)*1;
end
else NUM(i,j)=NUM(i,j)*1;
end
end
end
end
end
NUM=NUM+NUM';
%以上判别出没有过障碍区的用户两点之间的线段，对应点放在矩阵NUM中满足记
为1
for i=1:100
if(SIGN(i)==0)
for j=1:100
NUM(i,j)=0;
NUM(j,i)=0;
end
end
end
NUM
%NUM用于记录任意两用户点之间可用线段连接起来且不过障碍区的线段，对应点
放在矩阵NUM中满足记为1
%问题三，最小生成树的计算
AL=[A(1:OUTSIGN(1)-1,:);A(OUTSIGN(1)+1:OUTSIGN(2)-1,:);...
A(OUTSIGN(2)+1:OUTSIGN(3)-1,:);A(OUTSIGN(3)+1:OUTSIGN(4)-1,:);...
A(OUTSIGN(4)+1:100,:)];
%AL记录不在障碍区的用户点的信息
DIS=zeros(p,p);
for i=1:p
for j=1:p
AAA=[AL(i,2)-AL(j,2),AL(i,3)-AL(j,3)];
DIS(i,j)=norm(AAA);
end
end
for i=1:p
for j=1:p
if(i~=j)
if(NUM(AL(i,1),AL(j,1))==0)DIS(i,j)=inf;
end
end
end
end
DIS
%记录不在障碍区各用户点之间可用不过障碍区线段连接的线段的长度
%以下是kruscal算法求解最短路问题
%图论最小生成树Kruskal避圈算法(使用时根据题目修改w和n)
%W为邻接矩阵
W=DIS;
n=p;%有p个点
k=1;
for i=1:n-1
for j=i+1:n
if (W(i,j)~=inf)
x(1,k)=W(i,j);%记录边
x(2,k)=i;%记录起点
x(3,k)=j;%记录终点
k=k+1;
end
end
end
k=k-1; %统计边数 k为边数
%步骤一
%冒泡法给边的大小排序
for i=1:k
for j=i+1:k
if x(1,i)>x(1,j)
a=x(1,i);x(1,i)=x(1,j);x(1,j)=a;
a=x(2,i);x(2,i)=x(2,j);x(2,j)=a;
a=x(3,i);x(3,i)=x(3,j);x(3,j)=a;
end
end
end
R=zeros(1,n); %R用于记录已选的点的标号
for i=1:n
l(i)=i;
end
%l 用于对点的筛选，防止形成回路
%初始时选e1加入集合EE
EE(1,1)=x(1,1); %EE矩阵的第一行记录最小生成树的边长
EE(2,1)=x(2,1); %EE矩阵的第二行记录边的起点
EE(3,1)=x(3,1); %EE矩阵的第三行记录边的终点
a=min(l(x(2,1)),l(x(3,1)));
l(x(2,1))=a;l(x(3,1))=a;%用于筛选点，防止形成回路
b=1;%记录EE中边数
R(1)=x(2,1);
R(2)=x(3,1);
c=2;
for i=2:k
%步骤四
if b==n-1 %如果树中边数达到n-1
break %算法终止
end
%步骤二
O1=find(R==x(2,i));
O2=find(R==x(3,i));
size1=size(O1,2);
size2=size(O2,2);
if(size1~=0&size2~=0)
if l(x(2,i))==l(x(3,i));
else %如果两顶点标号不同
b=b+1; %将这条边加入EE
EE(1,b)=x(1,i);
EE(2,b)=x(2,i);
EE(3,b)=x(3,i);
a=min(l(x(2,i)),l(x(3,i)));
b1=max(l(x(2,i)),l(x(3,i)));
S1=find(l==b1);
len=size(S1,2);
for j=1:len
l(S1(j))=a;
end
end
else
if(size1==0&size2~=0)
R(c+1)=x(2,i);
c=c+1;
end
if(size2==0&size1~=0)
R(c+1)=x(3,i);
c=c+1;
end
if(size2==0&size1==0)
R(c+1)=x(2,i);
R(c+2)=x(3,i);
c=c+2;
end
b=b+1; %将这条边加入EE
EE(1,b)=x(1,i);
EE(2,b)=x(2,i);
EE(3,b)=x(3,i);
a=min(l(x(2,i)),l(x(3,i)));
b1=max(l(x(2,i)),l(x(3,i)));
S1=find(l==b1);
len=size(S1,2);
for j=1:len
l(S1(j))=a;
end
end
end
EE;
sum=0;
for i=1:p-1
sum=sum+EE(1,i);
end
sum
hold on;
for i=1:100
x=A(i,2);
y=A(i,3);
plot(x,y,'o')
end
for i=1:n-1
x1=AL(EE(2,i),2);
y1=AL(EE(2,i),3);
x2=AL(EE(3,i),2);
y2=AL(EE(3,i),3);
X=[x1,x2];
Y=[y1,y2];
plot(X,Y)
end
for i=1:3
x1=B(i,2);
y1=B(i,3);
x2=B(mod(i,3)+1,2);
y2=B(mod(i,3)+1,3);
X=[x1,x2];
Y=[y1,y2];
plot(X,Y,'m')
end
for i=1:5
x1=C(i,2);
y1=C(i,3);
x2=C(mod(i,5)+1,2);
y2=C(mod(i,5)+1,3);
X=[x1,x2];
Y=[y1,y2];
plot(X,Y,'m')
end
for i=1:3
x1=D(i,2);
y1=D(i,3);
x2=D(mod(i,3)+1,2);
y2=D(mod(i,3)+1,3);
X=[x1,x2];
Y=[y1,y2];
plot(X,Y,'m')
end
for i=1:3
x1=E(i,2);
y1=E(i,3);
x2=E(mod(i,3)+1,2);
y2=E(mod(i,3)+1,3);
X=[x1,x2];
Y=[y1,y2];
plot(X,Y,'m')
end
30
_1234567897.unknown
_1234567901.unknown
_1234567903.unknown
_1234567905.unknown
_1234567906.unknown
_1234567904.unknown
_1234567902.unknown
_1234567899.unknown
_1234567900.unknown
_1234567898.unknown
_1234567893.unknown
_1234567895.unknown
_1234567896.unknown
_1234567894.unknown
_1234567891.unknown
_1234567892.unknown
_1234567890.unknown
浙公网安备 33021202002483