自来水管道的连接优化问题

1、自来水管道的连接优化问题摘要为了使自来水管道总长度最小，现我们考虑通过分两步来解决。首先，先确定点是否属于不可连接区域。我们分别通过点坐标转换为极坐标后扩大区域再二维比大小、离散法分割区域后点坐标带入比对、以及边界限定后整体线性规划的方法确定点是否处于区域中。最终考虑线性规划法的精确度最高，得出第4、23、36、99点在不可连接区域内。再参考网上资料考虑最小连接问题，剔除无效点后，对剩余点间距离以欧式距离赋值，通过不可连接区域的距离赋值为无穷，生成带权邻接矩阵，再使用kruskal算法解出最小生成树，结果为653.0196。最后，对此最小生成树结果进行优化，考虑加入一点使得此值更小，于是利用循

2、环语句，将x=1100 ；y=1100共10000个整数点分别带入，使之成为第97个点，利用上述算法重新生成新的带权邻接矩阵，再使用kruskal算法求得结果为642.1555。同理再从优化矩阵中返回点，依次加入，作为第98个点，再求的结果为。，依次类推，可以找到最理想值。关键词：长度最段；线性规划；最小生成树；极坐标；离散一、 问题的重述及分析1.1问题的重述：自来水是人们日常生活中不可缺少的生活要素，然而自来水管网的组建却有很多问题需要解决。一般来说，我们假设管网中任意两个用户之间存在直线段相连，但是在连接过程中，有些区域是必须绕开的，这些必须绕开的区域我们称为障碍区域。表1给出了若干个可

3、能的用户的地址的横纵坐标，可能的用户的含义是：如果用户的地址不在障碍区域内，那么该用户就是需要使用自来水的用户（即有效用户），否则如果用户的地址在障碍区域内，那么该用户就是无效用户（即不要将该用户连接在网络中）。表2-表5是分别是4个障碍区域必须要覆盖的点的坐标，而对应障碍区域就是覆盖这些要覆盖的点的最小凸集。(1)请您判定表1中那些用户为有效用户。(2)请设计一个算法将有效用户连接起来，并且连接的距离总和最小。1.2问题的分析：问题（1）：根据题目要求，我们需要对用户的100个点位置进行评判，判断其是否属于可连接区域内。我们考虑到区域具有不规则性，无法利用简单的二维数值直接比较，于是考虑把区

4、域做适当放大，化为极坐标区域进行二维判断。由于实际情况中，区域放大会有误差，为提高精度，考虑将不可连接区域分割离散化，将离散出的小格视为点，判断用户情况。进而综合上述两种方案，进一步优化，可利用线性规划的方法，将边界利用方程表示，以此更精确的限定区域。问题（2）：由题目，此题需同时考虑管道的经济成本（即连线的长度最短）和躲避不可连接区域这两个问题，由于躲避不可连接区域为必须条件，所以我们考虑将整个区域自行分块（按照处理的便利程度躲避不可连接区域），再利用最小生成树来将各区域内的点连上，再取相邻两区域的最小距离相连。由于此方案不够自动化，需要人为分区，故我们考虑对全体点运用最小生成树的方案，对不

5、可连接区域内的距离设定为正无穷大，以此解决问题。二、 模型的前提假设1、假设任意两个用户之间可以用直线连接。2、假设用户的面积可近似为点。3、假设障碍区域的边界是标准的直线。4、文中给出所有点的坐标值准确无误。5、以所有管道总距离最小为目的。6、假设所有有效用户的自来水都得通过这个自来水管网供应。三、 符号说明变量定义x用户点的横坐标y用户点的纵坐标用户点极坐标的角度值r用户点极坐标的半径值temp一乘一百的赋值矩阵四、 模型的建立与求解4.1问题一：4.1.1极坐标法模糊简化区域由于区域大多不规则，利用2维坐标做简单的直接限定（如x<5等）使之成为方形区域的精确度过低，于是我们考虑利用

6、极坐标法表示现有坐标，并用形如扇面的区域来代替原区域，以求用直接限定的方法，确定点是否处于危险区域内。首先绘出四个限定区域：（编程过程见附1） 分别讨论每一个区域以区域一为例，将其边界点坐标转化为极坐标附2，转化出的极坐标为=1.3275 0.8365 1.3373r =13.3085 26.0518 20.5581由图像可知，此扇面区域的r坐标的区间为13.3085，26.0518，坐标区间为0.8365，1.3373，故此扇形区域可以覆盖整个区域一，同理可找出其他三个区域的r坐标区间，和坐标区间区域24的r、坐标区间分别为：r251.9106，73.9211；20.5404，0.9174r

7、388.8363，104.8269；30.9075，1.0403r4106.3015，124.1974；40.6947，0.8709 用极坐标模糊障碍区域后，障碍区域变大，如图所示：利用算法语句将100个标记点转化为极坐标，并判断其是否属于此极坐标区域中附3。执行结果如下:QW = 4 7 13 17 23 28 33 36 37 74 89 99将这12个点进行验证，可知其中一部分点并不在区域内，所以该方法误差较大。离散法分解区域：由于将原区域转化成扇面区域产生了一定的误差（由于扇面面积大于实际面积所致），故我们考虑将连续的整体面积离散化，通过分割来提高精度。 通过matlab的grid o

8、n功能，我们得出了离散后的障碍区域图形，图中每个网格我们都可以用坐标表示出来，于是我们可以利用题设点坐标直接对应到区域图内，利用直接观察的办法判断其是否属于障碍区域。显然，网格划分的越密，对于区域的限定就越准确，判断结果也就越准确。但此方法，需要的精度太高，并非matlab可以达到，而且也不够智能（需要人为界定），故我们提出对它的改进办法。4.1.3线性规划圈定区域：根据两点式求直线的方法可求出每个障碍区域的边界的直线方程，根据线性规划的方法可知道障碍区域内的点应满足的条件。然后用matlab软件编程，首先产生一个一行一百列的零矩阵temp，然后采用for循环使得程序自动输入每个点的坐标x,y

9、,接着判断是否满足在障碍区域二内的条件，若满足则不改变矩阵temp相应位置的值，若不满足则接着判断是否在障碍区域一内的条件，若满足则不改变矩阵temp相应位置的值，若不满足则接着判断是否在障碍区域三内的条件，若满足则不改变矩阵temp相应位置的值，若仍不满足则接着判断是否在障碍区域四内的条件，若满足则不改变矩阵temp相应位置的值，若还不满足则将矩阵temp相应位置的值改为1.最后寻找矩阵temp中为一的元素，将其列下标赋值给temp。执行程序，最后所得到的temp的值就是无效用户。区域内的点应满足的条件 利用两点式求直线方程，公示如下：y=b2-b1 a2-a1x+a1b2-a2b1a2-b

10、1障碍区域一为一三角形，区域内的点应满足以下三个方程：0.4506*x+11.4720-y<04.5652*x-1.7194-y>0-0.0522*x+20.2483-y>0障碍区域二为一五边形，区域内的点应满足以下五个方程：0.2123*x+47.1579-y>01.6865*x-16.3903-y>0-0.5879*x+59.395-y<04.9243*x-216.2150-y<0-1.2705*x+116.7341-y>0障碍区域三为一三角形，区域内的点应满足以下三个方程：1.4654*x+11.2402-y>0-1.2860*x+1

11、40.3423-y<0-21.0150*x+1219.4200-y>0障碍区域四为一三角形，区域内的点应满足以下三个方程：-2*x+255-y>0-0.25*x+97.5-y<01.5*x-25-y>0利用matlab语言编程，带入所有点求解附4判断点是否在障碍区域内：可判断出编号为4,23,36,99的点在障碍区域内，无效点的坐标为编号 横坐标 纵坐标4.0000 48.5982 33.395123.0000 81.3166 87.436736.0000 41.8649 41.195399.0000 6.4781 17.0793 用matlab软件根据点的坐标及

12、障碍区域的边长的直线方程可将所有用户的情况表示出来，结果如下：4.2问题二：4.2.1限定区域的用户最小连接：注：此部分参考学长论文，相同内容不再赘述。为了求解最短路径直接在平面内通过求解障碍区域顶点与用户点的直线方程筛选有效用户之间的有效线段。构造有效线段的带权临接矩阵，将无效线段的距离赋值为无穷大。 利用带权临接矩阵，使用 Kruskal 算法解得最小连通图，并解得最小连通距离设计程序执行（建立两个M文件附5）如下：距离为653.0196.附6 4.2.2对最小连接结果的优化（加入一个点）：从图中可看出为了躲避障碍区域程序所得路径是不“自由”的所以不是最短的，容易想到沿着障碍区域走折线反而

13、路径更短。由此，考虑依次带入平面内的点。利用循环语句，我们考虑x=1100 ；y=1100共计一万个整数点分别代入（由于计算机计算速度的限制，10000次带入计算已经很庞大了，故我们将精度定在整数位上），再次应用最小生成树的算法找出最短的路径是：642.1555 此点坐标为90 75 附7此图为分别代入所有整数点作为第97个点后的最小生成树距离（10000个点的最小值详细结果矩阵见运行结果.txt）。局部放大后的引入一点后的最优解用红叉表示：4.2.2对最小连接结果的优化（加入多个点）：在加入点90 75后，我们考虑再加入一点，使得结果进一步优化，由上图所示，纵坐标在653.0196以下的点共

14、有659个附8，利用循环语句，分别在加入这659个点作为第98个点，所得最小生成树结果为五、 优缺点分析关于极坐标法模糊简化区域优点：将横纵坐标x,y转化为极坐标，转变思考问题的角度，若障碍区域为圆形或椭圆形，能够使问题得到很好的简化。缺点：极坐标法模糊简化区域增大了障碍区域的范围，不能够准确的判断出有效用户，结果使得无效用户由4个增加到12个，误差较大。5.1.2 关于离散法分解区域优点：可以通过控制不同的精度精确地判断点是否属于区域内。缺点：不够自动化，需要人为的确定精度，和比较大小。 5.1.3线性规划圈定区域：优点：此方法简单易懂，容易想到，用最基本的方法解决了问题。且用C语言编写程序

15、较为简单，方便。缺点：当障碍区域较多或障碍区域的边长较多时，需要求很多个障碍区域的边界的直线方程，过程过于繁琐，且所编写的程序需要根据直线方程的变动而变动，不具有普遍性。未加入额外点的最小生成树的优缺点：优点：用最小生成树解决最短路问题，较为方便缺点：某两个有效用户之间用通过障碍物的顶点的折线连接，而这 样得到的水道管总长度更短。如图所示： 很显然，红色连线短于黑色连线。六、 参考文献 1谭浩强.C程序设计（第四版）.清华大学出版社，20102许丽佳，穆炯.MATLAB程序设计及应用.清华大学出版社，20113薛定宇，陈阳泉.高等应用数学问题的MATLAB求解. 清华大学出版社，2008七、

16、附表 附1：（1）区域一x = 3.2060 17.4571 4.7576 3.2060>> y=12.9166 19.3377 20 12.9166y = 12.9166 19.3377 20.0000 12.9166>> plot(x,y,'k-')x = 3.2060 17.4571 4.7576 3.2060>> y=12.9166 19.3377 20 12.9166y = 12.9166 19.3377 20.0000 12.9166>> plot(x,y,'k-')（2）区域二>> x=5

17、0 53.7465 46.9222 43.1123 33.3207 50x = 50.0000 53.7465 46.9222 43.1123 33.3207 50.0000>> y=30 48.4490 57.1195 56.3187 39.8050 30y = 30.0000 48.4490 57.1195 56.3187 39.8050 30.0000>> plot(x,y,'k-')（3）区域三：>> x=54.6982 53.7465 46.9222 54.6982x = 54.6982 53.7465 46.9222 54.698

18、2>> y=70 90 80 70y = 70 90 80 70>> plot(x,y,'k-')（4）区域四>> x=90 80 70 90x = 90 80 70 90>> y=75 95 80 75y = 75 95 80 75>> plot(x,y,'k-')附2：区域一>> y=12.9166 19.3377 20.0000;>> x=3.2060 17.4571 4.7576;>> theta,r = cart2pol(x,y)theta = 1.3275

19、 0.8365 1.3373r = 13.3085 26.0518 20.5581区域二y=30 48.4490 57.1195 56.3187 39.8050; x=50 53.7465 46.9222 43.1123 33.3207; theta,r = cart2pol(x,y)theta = 0.5404 0.7336 0.8831 0.9174 0.8738r = 58.3095 72.3602 73.9211 70.9258 51.9106区域三y=70 90 80; x=54.6982 53.7465 46.9222; theta,r = cart2pol(x,y)theta =

20、 0.9075 1.0325 1.0403r = 88.8363 104.8269 92.7453区域四y=75 95 80; x=90 80 70; theta,r = cart2pol(x,y)theta = 0.6947 0.8709 0.8520r = 117.1537 124.1974 106.3015附3：Q=zeros(1,100);for i=1:100 thera=JI(i,1);r=JI(i,2);if(thera>0.8365&thera<1.3373&r>13.3085&r<26.0518)Q(i)=0;else if(t

21、hera>0.5404&thera<0.9174&r>51.9106&r<73.9211)Q(i)=0;else if(thera>0.9075&thera<1.0403&r>88.8363&r<104.8269)Q(i)=0;else if(thera>0.6947&thera<0.8709&r>106.3015&r<124.1974)Q(i)=0;elseQ(i)=1;endendendendendQW=find(Q=0)QW = 4 7 13 1

22、7 23 28 33 36 37 74 89 99附4：temp=zeros(1,100);for i=1:100 x=data(i,2);y=data(i,3);if(0.2102*x+47.2565-y>0&1.6865*x-16.3903-y>0&(-0.5879)*x+59.395-y<0&4.9243*x-216.2150-y<0&(-1.2705)*x+116.7341-y>0)temp(i)=0;else if(0.4506*x+11.4720-y<0&4.5652*x-1.7194-y>0&

23、;(-0.0522)*x+20.2483-y>0)temp(i)=0;else if(1.4654*x+11.2402-y>0&(-1.2860)*x+140.3423-y<0&(-21.0150)*x+1219.4200-y>0)temp(i)=0;else if(-2)*x+255-y>0&(-0.25)*x+97.5-y<0&1.5*x-25-y>0)temp(i)=0;elsetemp(i)=1;endendendend附5：建立两个M文件M文件一、questiondata=1.0000 95.0129 58.2

24、7922.0000 23.1139 42.34963.0000 60.6843 51.55124.0000 48.5982 33.39515.0000 89.1299 43.29076.0000 76.2097 22.59507.0000 45.6468 57.98078.0000 1.8504 76.03659.0000 82.1407 52.982310.0000 44.4703 64.052611.0000 61.5432 20.906912.0000 79.1937 37.981813.0000 92.1813 78.332914.0000 73.8207 68.084615.0000

25、 17.6266 46.109516.0000 40.5706 56.782917.0000 93.5470 79.421118.0000 91.6904 5.918319.0000 41.0270 60.286920.0000 89.3650 5.026921.0000 5.7891 41.537522.0000 35.2868 30.499923.0000 81.3166 87.436724.0000 0.9861 1.500925.0000 13.8891 76.795026.0000 20.2765 97.084527.0000 19.8722 99.008328.0000 60.37

26、92 78.886229.0000 27.2188 43.865930.0000 19.8814 49.831131.0000 1.5274 21.396332.0000 74.6786 64.349233.0000 44.5096 32.003634.0000 93.1815 96.009935.0000 46.5994 72.663236.0000 41.8649 41.195337.0000 84.6221 74.456638.0000 52.5152 26.794739.0000 20.2647 43.992440.0000 67.2137 93.338041.0000 83.8118

27、 68.333242.0000 1.9640 21.256043.0000 68.1277 83.923844.0000 37.9481 62.878545.0000 83.1796 13.377346.0000 50.2813 20.713347.0000 70.9471 60.719948.0000 42.8892 62.988849.0000 30.4617 37.047750.0000 18.9654 57.514851.0000 19.3431 45.142552.0000 68.2223 4.389553.0000 30.2764 2.718554.0000 54.1674 31.

28、268555.0000 15.0873 1.286356.0000 69.7898 38.396757.0000 37.8373 68.311658.0000 86.0012 9.284259.0000 85.3655 3.533860.0000 59.3563 61.239561.0000 49.6552 60.854062.0000 89.9769 1.576063.0000 82.1629 1.635564.0000 64.4910 19.007565.0000 81.7974 58.691866.0000 66.0228 5.758167.0000 34.1971 36.756868.

29、0000 28.9726 63.145169.0000 34.1194 71.763470.0000 53.4079 69.266971.0000 72.7113 8.407972.0000 30.9290 45.435573.0000 83.8496 44.182874.0000 56.8072 35.325075.0000 37.0414 15.360676.0000 70.2740 67.564577.0000 54.6571 69.921378.0000 44.4880 72.750979.0000 69.4567 47.838480.0000 62.1310 55.484281.00

30、00 79.4821 12.104782.0000 95.6843 45.075483.0000 52.2590 71.588384.0000 88.0142 89.284285.0000 17.2956 27.310286.0000 97.9747 25.476987.0000 27.1447 86.560388.0000 25.2329 23.235089.0000 87.5742 80.487290.0000 73.7306 90.839891.0000 13.6519 23.189492.0000 1.1757 23.931393.0000 89.3898 4.975494.0000

31、19.9138 7.838495.0000 29.8723 64.081596.0000 66.1443 19.088797.0000 28.4409 84.386998.0000 46.9224 17.390099.0000 6.4781 17.0793100.0000 98.8335 99.4295data2=1 3.2060 12.91662 17.4571 19.33773 4.7576 20data3=1 50 302 53.7465 48.44903 46.9222 57.11954 33.3207 39.80505 43.1123 56.3187data4=1 54.6982 7

32、02 53.7465 903 46.9222 80data5=1 90 752 80 953 70 80M文件二、function r=line_cross(x1,y1,x2,y2,x3,y3,x4,y4)LD1x=min(x1,x2);LD1y=min(y1,y2); LD2x=min(x3,x4);LD2y=min(y3,y4); RU1x=max(x2,x1);RU1y=max(y2,y1); RU2x=max(x3,x4);RU2y=max(y3,y4); X=(RU1x>LD2x)&(RU2x>LD1x); Y=(RU1y>LD2y)&(RU2y&g

33、t;LD1y); if X&Y M1=x3-x1,y3-y1;x2-x1,y2-y1; M2=x4-x1,y4-y1;x2-x1,y2-y1; M3=x1-x3,y1-y3;x3-x4,y3-y4; M4=x2-x3,y2-y3;x3-x4,y3-y4; P1=det(M1); P2=det(M2); P3=det(M3); P4=det(M4); Q1=P1*P2;Q2=P3*P4; if Q1<0&&Q2<0 r=2; elseif Q1=0|Q2=0 r=1; else r=0; end else r=0; end附6：data(99,36,23,4,

34、:)=; datastill=data; ad_matrix=;sumall=; h,l=size(data); fori=1:hfor j=1:h ad_matrix(i,j)=(data(i,2)-data(j,2)2+(data(i,3)-data(j,3)2)(1/2); end end fori=1:hfor k=i+1:h x1=data(i,2);y1=data(i,3); x2=data(k,2);y2=data(k,3); r=line_cross(x1,y1,x2,y2,3.2060 ,12.9166,17.4571,19.3377); if(r=0) ad_matrix(

35、i,k)=inf;ad_matrix(k,i)=inf;continue end r=line_cross(x1,y1,x2,y2,17.4571 ,19.3377,4.7576 ,20); if(r=0) ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continue end r=line_cross(x1,y1,x2,y2,4.7576 ,20,3.2060 ,12.9166); if(r=0) ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continue end r=line_cross(x1,y1,x2,y2,50,30,5

36、3.7465,48.4490); if(r=0) ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continue end r=line_cross(x1,y1,x2,y2,53.7465,48.4490,46.9222,57.1195); if(r=0) ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continue end r=line_cross(x1,y1,x2,y2,46.9222,57.1195,43.1123,56.3187); if(r=0) ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;c

37、ontinueendr=line_cross(x1,y1,x2,y2,43.1123,56.3187,33.3207,39.8050);if(r=0)ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continueendr=line_cross(x1,y1,x2,y2,33.3207,39.8050,50,30); if(r=0) ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continue end r=line_cross(x1,y1,x2,y2,54.6982 ,70,53.7465 ,90); if(r=0) ad_matrix

38、(i,k)=inf;ad_matrix(k,i)=inf;continueendr=line_cross(x1,y1,x2,y2,53.7465 ,90,46.9222 ,80);if(r=0)ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continueendr=line_cross(x1,y1,x2,y2,46.9222 ,80,54.6982 ,70);if(r=0)ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continueendr=line_cross(x1,y1,x2,y2,90 ,75,80 ,95);if(r=0)a

39、d_matrix(i,k)=inf;ad_matrix(k,i)=inf;continueendr=line_cross(x1,y1,x2,y2,80 ,95,70,80);if(r=0)ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continueendr=line_cross(x1,y1,x2,y2,70 ,80,90,75);if(r=0)ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continueendendendW=ad_matrix; n=h; k=1; for i=1:n-1 for j=i+1:n if (W(i,j

40、)=inf) x(1,k)=W(i,j); x(2,k)=i; x(3,k)=j; k=k+1; end end end k=k-1; 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); for i=1:n l(i)=i; end EE(1,1)=x(1,1); EE(2,1)=x(2,1); EE(3,1)=x(3

41、,1); a=min(l(x(2,1),l(x(3,1); l(x(2,1)=a;l(x(3,1)=a; b=1; R(1)=x(2,1); R(2)=x(3,1); c=2; for i=2:k if b=n-1 breakend 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); elseb=b+1;EE(1,b)=x(1,i); EE(2,b)=x(2,i); EE(3,b)=x(3,i); a=min(l

42、(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(1,b)=x(1,i); EE

43、(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:n-1 sum=sum+EE(1,i); end sumall=sumall,sum 附7data(99,36,23,4,:)=;sumall1=1000;A=;for m=1:100for w=1:100a=97,m,w;data=data;a; datastill

44、=data; ad_matrix=;sumall=; h,l=size(data); fori=1:hfor j=1:h ad_matrix(i,j)=(data(i,2)-data(j,2)2+(data(i,3)-data(j,3)2)(1/2); end end fori=1:hfor k=i+1:h x1=data(i,2);y1=data(i,3); x2=data(k,2);y2=data(k,3); r=line_cross(x1,y1,x2,y2,3.2060 ,12.9166,17.4571,19.3377); if(r=0) ad_matrix(i,k)=inf;ad_ma

45、trix(k,i)=inf;continue end r=line_cross(x1,y1,x2,y2,17.4571 ,19.3377,4.7576 ,20); if(r=0) ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continue end r=line_cross(x1,y1,x2,y2,4.7576 ,20,3.2060 ,12.9166); if(r=0) ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continue end r=line_cross(x1,y1,x2,y2,50,30,53.7465,48.4490

46、); if(r=0) ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continue end r=line_cross(x1,y1,x2,y2,53.7465,48.4490,46.9222,57.1195); if(r=0) ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continue end r=line_cross(x1,y1,x2,y2,46.9222,57.1195,43.1123,56.3187); if(r=0) ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continueendr=li

47、ne_cross(x1,y1,x2,y2,43.1123,56.3187,33.3207,39.8050);if(r=0)ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continueendr=line_cross(x1,y1,x2,y2,33.3207,39.8050,50,30); if(r=0) ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continue end r=line_cross(x1,y1,x2,y2,54.6982 ,70,53.7465 ,90); if(r=0) ad_matrix(i,k)=inf;ad_m

48、atrix(k,i)=inf;continueendr=line_cross(x1,y1,x2,y2,53.7465 ,90,46.9222 ,80);if(r=0)ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continueendr=line_cross(x1,y1,x2,y2,46.9222 ,80,54.6982 ,70);if(r=0)ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continueendr=line_cross(x1,y1,x2,y2,90 ,75,80 ,95);if(r=0)ad_matrix(i,k)=

49、inf;ad_matrix(k,i)=inf;continueendr=line_cross(x1,y1,x2,y2,80 ,95,70,80);if(r=0)ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continueendr=line_cross(x1,y1,x2,y2,70 ,80,90,75);if(r=0)ad_matrix(i,k)=inf;ad_matrix(k,i)=inf;continueendendendW=ad_matrix; n=h; 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)