【基于最短路径的三维网格模型分割算法分析7500字】

基于最短路径的三维网格模型分割算法分析目录TOC\o"1-3"\h\u11021基于最短路径的三维网格模型分割算法分析 .3.3所述，对于图2-1所示的兔子网格模型，以邻接矩阵的方式存储需消耗8.5MB的空间。以本文的方式，则V-V所占用空间为179KB，V-W所占用空间为619KB，共798KB。可见，经如上的操作，所需要的存储空间大大减少。同时，对于图2-7中的兔子模型上的最短路径的计算，标准的Dijkstra算法共消耗时间为18.88秒，共进行了18578次松弛操作，本文所改进的Dijkstra算法仅需0.74秒，进行了17403次松弛操作。可见，本文所述的改进方法对于Dijkstra算法的速度提升非常明显。其中，松弛次数的相差并不大的原因在于，起点和终点的距离较远，改进的Dijkstra算法搜索到终点时已遍历了大多数网格点，若起点终点较近，则在松弛操作的次数上的提升将会更加明显。对此，本文增加了在另一个球形网格模型上搜索最短路径的测试，相应的比较如图2-9和表2-13所示。可见，经过改进的Dijkstra算法在运行速度和存储空间方面有着极大的提升，并且保持了路径计算结果的正确性。表2-13改进Dijkstra算法测试模型数据比较模型名称兔子模型（27778个三角面片）球形模型（24630个三角面片）项目路径总长（边数目）占用存储空间运行时间（s）松弛操作次数路径总长（边数目）占用存储空间运行时间（s）松弛操作次数标准Dijkstra808.5MB18.8818578216.77MB10.1613903改进Dijkstra80798KB0.741740321698KB0.0371931（a）（b）（c）（d）图2-9最短路径计算比较（a）标准Dijkstra算法在兔子模型上的计算结果；（b）改进Dijkstra算法在兔子模型上的计算结果；（c）标准Dijkstra算法在球形模型上的计算结果；（d）改进Dijkstra算法在兔子模型上的计算结果网格模型的分割在经过了优化Dijkstra算法后，可以迅速计算出网格模型上任意两点间的最短路径，可以将该路径作为分开网格模型的新边界，以该边界将网格模型分片，即可得到分开的独立的两个网格模型。此时，需要基于新的边界计算出分别属于不同分片的网格模型上的三角面片。对此，本文通过在不同分片布置种子点，采用区域生长的方法计算出分属于不同分片的三角面片。具体的做法如下。step1.准备数据。导入路径path、点对面拓扑数据V-F、点对点拓扑数据V-V，选取不同分片上的种子点集合seed。准备空的cell数组F-part。step2.区域增长。从seed中依次取出种子点Vi，对于每个种子点，从Vi开始，不断寻找其邻接的顶点V_adjacency，直到生长到边界停止。将这些顶点所对应的面标号集合记录下来，由于不同点所对应的面片由重合部分，调用unique函数去除其中的重复面片，存储在以上所述的步骤在MATLAB平台实现，伪代码如表2-14所示。表2-14区域生长分割网格模型的伪代码Algorithm5:SegmentationbyRegionGgrow输入：点对点拓扑数据V-V,点对面的拓扑数据V-F,种子点集合seed,路径path输出：不同分片的三角面片F-partNseedF-part=大小为Nseedfori=1toNVi=Nseed(vertex-part=空数组;vertex-part=将Viwhen仍有V_adjacency可加入vertexV_adjacency=在V-V中取出vertex-part中的顶点的邻接点；ifV_adjacency还未被加入vertex-part且V_adjacency不属于seedvertex=将V_adja