自来水管道连接规划模型

1、数学建模作业：自来水管道连接规划模型自来水管道连接规划模型【摘要】：生活中需要通过自来水管道将自来水运输至各个用户处，本文分析讨论自来水管道连接规划问题，即在自来水管道铺设过程中在绕开障碍物的前提下的最优路径问题，使自来水管道将各个供水点用最短路径链接。根据对100个目标点的数据进行筛选与分析，得出在用面积法排除障碍区域的前提下，对剩余点采用Kruskal算法生成最优路的方案。初始给定的100个供水点中存在位于障碍区域中的点，采用合理的方法排除障碍区域中的点，将对管道链接的效率、能耗、可行性起到决定性作用，是一个非常实际的问题。本文将采用面积分析的方法，提供一种解决障碍区域判定的切实可行的方法

2、，在二维坐标系上标定各点，障碍区域用由阴影覆盖的凸多边形表出，通过对点坐标之间的向量运算判定各点是否位于阴影区域，最终通过MatlabR2010a编程实现。在确定并剔除障碍区中的点位后，采用Kruskal闭圈算法生成最优路径，对于通过阴影区域的线段，采用将其权值设定为（无穷大）的处理方法，最终通过MatlabR2010a编程、绘图，给出管道最优连接方案，解决本问题。最后我们对模型的可行性，合理性，科学性进行了阐述，得到对模型的整体评价以及需改进之处。【关键词】：管道连接 面积法 障碍点筛选Kruskal算法 权值 最小生成树一. 问题重述自来水是人们日常生活中不可缺少的生活要素，然而自来水管网

3、的组建却有很多问题需要解决。一般来说，我们假设管网中任意两个用户之间存在直线段相连，但是在连接过程中，有些区域是必须绕开的，这些必须绕开的区域我们称为障碍区域。表1给出了若干个可能的用户的地址的横纵坐标，可能的用户的含义是：如果用户的地址不在障碍区域内，那么该用户就是需要使用自来水的用户（即有效用户），否则如果用户的地址在障碍区域内，那么该用户就是无效用户（即不要将该用户连接在网络中）。表2-表5是分别是4个障碍区域必须要覆盖的点的坐标，而对应障碍区域就是覆盖这些要覆盖的点的最小凸集。(1) 请您判定表1中那些用户为有效用户。(2) 请设计算法筛选有效用户之间的有效线段。(3)请设计一个算法将

4、有效用户用有效线段连接起来，并且连接的距离总和最小。表1（见附录一）表2障碍区域1必须要覆盖的点的坐标顶点序号顶点的横坐标顶点的纵坐标13.2060 12.9166217.457119.337734.7576 20表3障碍区域2必须要覆盖的点的坐标顶点序号顶点的横坐标顶点的纵坐标150 30253.746548.4490346.922257.1195433.320739.8050543.112356.3187表4障碍区域3必须要覆盖的点的坐标顶点序号顶点的横坐标顶点的纵坐标154.698270253.746590346.922280表5障碍区域4必须要覆盖的点的坐标顶点序号顶点的横坐标顶点的纵

5、坐标190752809537080二模型假设1， 假设任意两个用户之间以直线连接；2， 不在障碍区中的用户都通过自来水管道获得自来水供应；3， 以所有管道总距离最小为目的；4， 障碍区域就是障碍顶点围成的凸多边形区域；5， 文中给出所有点的坐标值准确无误；6， 在非障碍区用户之间可确保用直线连接；7， 要保证在任意两点间线段不过障碍区的情况下，求解连接形成的最短路径；三符号说明表6 论文符号说明符号含义A记录100个用户点的坐标信息B障碍区1的各顶点坐标信息C障碍区2的各顶点坐标信息D障碍区3的各顶点坐标信息E障碍区4的各顶点坐标信息SIGN记录各用户点是否在障碍区，若在对应位置记为1；若不在

6、，则对应位置记为0OUTSIGN记录在障碍区的用户点的序号p记录保留用户点的个数NUM记录任意两用户点之间可用线段连接起来且不过障碍区的线段DIS记录不在障碍区各用户点之间可用不过障碍区线段连接的线段的长度EE记录生成的最小生成树的各点及各线段信息sum表示产生的最小生成树中所有管道的总长四问题分析解决问题的第一步是排除障碍区域的影响。如果用户点位于障碍区域之外，则为有效用户，否则，为无效线段。解决问题第二步，将任意两个有效用户用线段连接，如果任意两个用户点之间的线段通过障碍区域之内，则为无效线段，作剔除处理，筛选出有效线段。解决问题第三步，根据筛选出来的有效用户点和有效线段生成最小生成树连接

7、有效用户点，画出连接路线图形，并计算生成树长度。根据对模型的合理假设，障碍区域即为已知若干障碍区顶点围成的凸多边形，故解决此问题的关键在于在已建立的二维坐标系中，寻找到一种合理的算法能够判定出点是否位于障碍区域中。通过直观判断，阴影区域的构成由表7给出：表7 障碍区域构成障碍区域编号构成1由3个无效用户坐标点围成的三角形2由5个无效用户坐标点围成的凸五边形3由3个无效用户坐标点围成的三角形4由3个无效用户坐标点围成的三角形通过设计运用面积法进行筛选点的程序，对所有点进行筛选，找到并排除障碍区域中的无效用户，完成解决问题的第一步。接下来我们要做的是把任意两个有效用户点之间用线段连接，运用向量法设

8、计筛选线段的程序，筛选出所有不过障碍区的线段，完成解决问题的第二步。解决自来水管道连接问题的第三步需要我们设计一个程序，将所有有效用户点连接起来，并使管道总距离最小。这是一个典型的最小生成树问题，但相较以往最小生成树问题又有着其特别之处，就是障碍区域的干扰，即管道无法穿过障碍区，这使得坐标系并非是一个连通区域，众多算法无法直接使用。这就需要我们在对问题进行合理假设的前提下，对已有算法进行改良。我们通过对穿过障碍区的线段赋权值为无穷大的方法，利用Kruskal算法，生成最优路径。五模型的建立与求解： 5.1.问题一的模型建立和求解由问题分析可知，本问题的关键有二个：一是求确定各障碍区的面积以及用

9、户点与各障碍区任意两个定点构成的三角形的面积之和；二是比较上面两个面积，若相等，则该用户点在障碍区内为无效用户，否则，用户点不在障碍区内为有效用户。5.1.1运用向量的方法求解障碍区面积S若障碍区是三角形，对应各顶点坐标分别为(x1,y1)，(x2,y2), (x3,y3)。则a=(x2-x1,y2-y1),b=(x3-x1,y3-y1)。由于三角形面积S=|a|*|b|*sin<a,b>/2,向量a,b外积的模长|a×b|=|a|*|b|*sin<a,b>则有S=|a×b|/2;若障碍区为五边形，对应点为(x1,y1)，(x2,y2), (x3,y

10、3), (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.1中求解三角形面积的方法相同。5.1.3判断有效用户 如果S=S1，则该用户在障碍区内，为无效用户。反之，为有效用户。则筛选完毕的结果如下： 在障碍区的点的序号分别为：4 23 36 99。 无效用户的信息为：(4.000

11、0,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.

12、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,可以求的。若0,则该线段为有效线段；若<0,则要考虑向量关系PA=PB,若0，则该线段为有效线段，否则，该线段为无效线段。5.3问题三的模型建立与求解若

13、要在N个用户之间连接自来水管道，由于每一个用户与其余N-1个用户之间都可能连接自来水管道。因此，在N个用户之间，最多可能连接N(N-1)/2条自来水管道然而，在连接N个用户之间的管道时，最少只需连接N-1条管道。也就是说只需要N-1条管道线路就可以把N个用户之间的自来水管道连通。现在要考虑在连接N个用户的自来水管道的同时要保证所有的管道长度之和最短，这就涉及了最优化的问题。则显然，要解决问题三需要两个步骤：一是利用Kruskal算法思想设计Matlab程序进行最小生成树所需边的筛选；二是设计算法将筛选出来的构成最小生成树的各边连接起来，求出最短路径长度，并画出连接图形。5.3.1利用Krusk

14、al算法思想求解最小生成树把用户看作图的顶点，把用户之间的自来水管道看做边，把连接各条线路的长度当作权值赋给相应的边，这样便构成一个带权的图，即网。为了解决上述问题的数学模型就是求上述图中的网状图的最小生成树的问题。由问题一可知，有效用户的个数为96，因此我们只需要考虑这96个点之间的连接，这96个点中任意两点之间的的关系只有两种，连接或不连接。我们可以先求出由96个用户点中任意两个用户点之间的距离构成的邻接矩阵DIS,再根据问题二中求得的有效线段与无效线段对邻接矩阵进行修改，将邻接矩阵中对应无效线段的位置的值修改为inf，可以得到一个新的邻接矩阵DIS。接下来，用冒泡排序法对所有有效线段长度

15、按从小到大的顺序进行排序。这时，需要借助Kruskal算法进行最小生成树的计算。然后把最小生成树对应边的线段长度、起点、终点信息记录在矩阵EE中。生成最小生成树时，从长度最短的边开始选取，这就涉及如何防止在选择过程中形成回路的问题。为了解决这个问题，首先不妨设一个1×96的标记向量l用于记录被选取的点的序号，初始状态向量l的各元素依次为各用户序号，在选取线段为边后，将对应两点的序号m与n取最小值，并将向量l中所有与m位置元素相等的元素位置及所有与n位置的元素相等的元素位置都赋值为该最小值，如此循环知道向量l中所有元素均相等时停止；同时可以设一向量R来依次记录被选点的序号，直到所有用户

16、点被无重复地被记录。在按线段长度从小到大的顺序选择边时，设线段端点用户的序号为m与n。这时需要考虑如下4种情况：<1>如果在向量R中m和n均没有被记录,则该线段可以被选为最小生成树的边，将对应线段的信息记录在矩阵EE中，同时在R中添加记录m和n的值，并按照上述步骤更新向量l。<2>如果在向量R中m被记录而n没有被记录，则该线段可以被选为最小生成树的边，将对应线段的信息记录在矩阵EE中，同时在R中添加记录n的值，并按照上述步骤更新向量l。<3>如果在向量R中n被记录而m没有被记录，则该线段可以被选为最小生成树的边，将对应线段的信息记录在矩阵EE中，同时在R中添

17、加记录m的值，并按照上述步骤更新向量l。<4>如果在向量R中m和n均被记录,则需要借助向量l来判断是否该线段可以被选为最小生成树的边：a. 如果向量l中对应的m位置与n位置的元素值相等，则该线段不是最小生成树的边，直接跳过到下一步判断。b. 如果向量l中对应的m位置与n位置的元素值不相等，则该线段是最小生成树的边，将对应线段的信息记录在矩阵EE中，同时只需要更新向量l。通过上述方法，即可产生最小生成树，其各边信息记录在矩阵EE中。 5.3.2设计Matlab程序求出最小生成树长度并将各边连接起来要计算最小生成树的长度，只需要借助for循环将EE矩阵中记录长度相加即可。具体算发如下：

18、 sum=0;for i=1:p-1 sum=sum+EE(1,i);endsum可以求得最小生成树的长度为：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(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)endfor i=1:3 x1=B(i,2); y1

19、=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')endfor 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')endfor 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(

20、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,则该模型所生成的最小生成树的长度最短，即运用该模型进行自来

21、水管道的连接所需要的自来水管长度最短。七模型的评价运用该模型进行最小生成树的生成可以一步到位，不需要进行人工的修改。因为该模型在生成最小生成树之前就已经就进行了有效用户与有效线段的筛选，所以，最小生成树中所选择的所有线段都是有效的不经过障碍区的。但是由于模型的需要计算的信息量比较的，在设计程序的时候变量的运用比较混乱，不方便阅读与修改，同时，由于算法设计繁琐且反复运用for循环，计算所需次数较多。如果在上述问题中多注意，则该模型将会更加完美。 八模型的推广 可以在保证障碍区不变的情况下，任意改变用户点的信息，运用该模型同样可以求得连接自来水管道的最短长度。且不需要过多改动，不需要人工进行修改计

22、算的结果。但是在障碍区变化的情况下，则需要较大改动。同时该模型可以应用到修建连接若干个地点之间的公路长度和最短的问题中。九参考书目1 姜启源等，数学模型（第三版），北京：高等教育出版社，20032 薛定宇，陈阳泉，高等应用数学问题的Matlab求解，清华大学出版社，20083 赵静，但琦等，数学建模与数学实验，高等教育出版社，2008十附录附录一：小组成员分工及数学建模过程感想分工：罗圣：负责符号说明、模型建立及求解、模型检验、算法设计及Matlab程序等部分的编写。乔世俊：负责组织论文总体结构，及编写摘要、问题重述、模型假设等部分。王博：负责构思解决各问题的算法及编写问题分析、模型推广、参考

23、书目及附录等部分。感想：罗圣：通过此次数学建模作业的完成过程，考验了我分析问题、解决问题的能力，同时也考验了我在不懂如何入手解决问题时是否具有坚持的耐心。我认为能完成这次数学建模作业对我是一个极大鼓励，让我可以相信自己能在面临一个陌生问题时可以独立解决它。在编写Matlab程序时遇到过很多问题，有很多问题需要自己的千方百计地思考才能解决，通过这次锻炼，学会了很多函数的使用，提升了自己编写程序解决实际问题的能力。从刚开始不知从何下手的煎熬到最后完成之后的满足，享受了团队合作的愉快，在这个过程中收获了很多。乔世俊：这次数学建模，是对我分析解决问题方面能力的一个考验，包括如何分析问题、如何查阅资料、

24、如何掌握模型结构等。能完成这次数学建模，让我信心倍增，我相信在以后遇到问题时，我可以更快得寻求到解决问题的方法。虽然这是第一次完成数学建模，但我相信它会是我的一次蜕变。王博：在刚接触这个数学建模作业的时候，我不知道如何进行问题的分析，不知道从什么方面进行入手，为此我十分苦恼。为了摆脱这中困境，我积极查找资料，希望能寻求到一些帮助。在这个过程中，我慢慢地找到了解决问题的思路。直到最后能完整解决这个问题，我学到了很多东西，同时，体会到了团队合作的重要性，整个过程我获益匪浅。附录二：若干个可能的用户的地址的横纵坐标可能的用户的序号可能的用户横坐标可能的用户纵坐标1.000095.012958.279

25、22.000023.113942.34963.000060.684351.55124.000048.598233.39515.000089.129943.29076.000076.209722.59507.000045.646857.98078.00001.850476.03659.000082.140752.982310.000044.470364.052611.000061.543220.906912.000079.193737.981813.000092.181378.332914.000073.820768.084615.000017.626646.109516.000040.5706

26、56.782917.000093.547079.421118.000091.69045.918319.000041.027060.286920.000089.36505.026921.00005.789141.537522.000035.286830.499923.000081.316687.436724.00000.98611.500925.000013.889176.795026.000020.276597.084527.000019.872299.008328.000060.379278.886229.000027.218843.865930.000019.881449.831131.0

27、0001.527421.396332.000074.678664.349233.000044.509632.003634.000093.181596.009935.000046.599472.663236.000041.864941.195337.000084.622174.456638.000052.515226.794739.000020.264743.992440.000067.213793.338041.000083.811868.333242.00001.964021.256043.000068.127783.923844.000037.948162.878545.000083.17

28、9613.377346.000050.281320.713347.000070.947160.719948.000042.889262.988849.000030.461737.047750.000018.965457.514851.000019.343145.142552.000068.22234.389553.000030.27642.718554.000054.167431.268555.000015.08731.286356.000069.789838.396757.000037.837368.311658.000086.00129.284259.000085.36553.533860

29、.000059.356361.239561.000049.655260.854062.000089.97691.576063.000082.16291.635564.000064.491019.007565.000081.797458.691866.000066.02285.758167.000034.197136.756868.000028.972663.145169.000034.119471.763470.000053.407969.266971.000072.71138.407972.000030.929045.435573.000083.849644.182874.000056.80

30、7235.325075.000037.041415.360676.000070.274067.564577.000054.657169.921378.000044.488072.750979.000069.456747.838480.000062.131055.484281.000079.482112.104782.000095.684345.075483.000052.259071.588384.000088.014289.284285.000017.295627.310286.000097.974725.476987.000027.144786.560388.000025.232923.2

31、35089.000087.574280.487290.000073.730690.839891.000013.651923.189492.00001.175723.931393.000089.38984.975494.000019.91387.838495.000029.872364.081596.000066.144319.088797.000028.440984.386998.000046.922417.390099.00006.478117.0793100.000098.833599.4295附录三：解决该自来水管道连接问题的Matlab程序：%问题一，进行有效点的筛选A=1.0000

32、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.00

33、00 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.084

34、5;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.

35、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;

36、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.

37、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 5

38、4.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.48

39、72;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

40、;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，否则记为0for n=1:100a1=B(2,2)-B(1,2),B(2,3)-B(1,3),0;a2=B(3,2)-B(2,2),B(3,

41、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

42、%第一个障碍区内的点判断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),

43、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%第二个障碍区内的点

44、判断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;%由

45、用户点和任意对应两个该障碍区顶点构成的三角形面积之和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)/

46、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;endendSIGN ;%以上判断不在障碍区的点，其标号记录在SIGN矩阵中用1表示OUTSIGN=find(SIGN=0)%记录在障碍区的用户点p=0;for i=1:100 p=p+SIGN(i);endp%计算保留用户点的个数p%问题二

47、，进行有效线段的筛选NUM=zeros(100,100);for i=1:100 for j=i+1:100 NUM(i,j)=1; endendb1=(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(