【作者】 弓晨；

【导师】 戴光明；

【作者基本信息】 中国地质大学 ， 计算机应用技术， 2006， 硕士

【摘要】 在给定曲面上的两点间求沿曲面的最短路径，是理论与实际领域都十分关注的问题。由于自由曲面自身的复杂性，需要找到一种既准确又可靠，并能广泛适用于自由曲面的求取方法。三维曲面最短路径的求解方法可以有效地解决形式各异的曲面路径优化问题。如果将其用于战场、公路、铁路建设，电力、通信线路，输水、输油管道的假设等实际问题中，可以起到立竿见影的效果，将节省大笔开支。 三维图形对象表示方法大致可以分为两类，即边界(Boundary)表示和实体表示(Solid)。边界表示包括多边形网格、隐式曲面、参数曲面模型，其中隐式曲面、参数曲面一般通过转换为多边形网格模型进行绘制。实体表示包括结构实体模型(CSG)和分解模型，其中结构实体模型最终需要转换为实体的边界表示进行绘制，而分解模型的最基本元素是体素。所以从绘制的角度看，也可以把三维图形对象的表示分为曲面模型(本文的研究重点)和体素模型(简称体模型)，曲面模型中可以用栅格作为典型。 栅格数据结构和矢量数据结构都是表示空间数据的有效方法，但是都有一定的优点和局限性。矢量数据能输出精美的地图，但结构复杂，用于空间分析存在不少的困难，尤其是在多边形的叠置、空间均值处理上。相比之下，栅格数据数据结构简单，叠加操作易于实现，更有效，如多边形周长、面积总和、平均值的计算等，在栅格结构中都简化为简单的计数操作，栅格坐标规则，删除和提取数据都可以按位置确定窗口来实现。 规则格网是比较普遍采用的表示方法。用Grid表示的DEM是一种XY平面等间距排列地面点XYZ三维坐标的数据形式。它的数据格式比较的简单，便于存储，建模方法也比较直接，所描述的高程细节信息也比较的丰富；采用不规则三角网表示的DEM称为三角网DEM或Tin(Triangulated irregular network)，它直接利用原始的离散采样点表示地形表面，因此Tin不仅有地面点XYZ的三维坐标，保持了原始采样数据的精度，还包含了三角网构网的拓扑信息，比较适合描述复杂的地形数据。但是三角形面元，以及三角形点、边之间的拓扑关系比较复杂，要对其进行处理也比较复杂。基于TIN模型的DEM简化计算在预处理和可视化的实时计算量比较大，难以处理跨区域DEM实时漫游，而且时显示时很难具有自适应能力；相比之下，规则格网结构简单，算法容易，可视化实时计算量小。 路径规划问题是人工智能研究的一个经典问题，它实际是一类求最优解的问题。其实现过程就是从问题的初始状态出发，不断地选择合适的操作来不断的改变问题的状态，直到满足目标状态为止，实现过程中所运用的操作序列就构成了问题的解。搜索的过程可以分为三个部分：一是选择合适的操作，二是记住已施行的操作序列，三是描述操作所产生的状态。求最优解或近似最优解方法可以分为枚举法、Dijkstra算法、传统的启发式算法和新兴的启发式算法——遗传算法等几种类型。利用启发式方法对三维曲面路径问题进行求解有比较重要的意义，能够求出比直接连线法更好的路径。且在计算过程中启发式算法的微调能力是更多还原

【Abstract】 Finding an algorithm for solving the minimal way on surface is concerned by theoretical and practical areas.The algorithm can be used for practical applications such as battlefield, the constructions of railway and highway, and so on.There are two ways to represent the 3D graphic objects: Boundary and Solid. Boundary includes polygon grid and parametric surface. Solid includes CSG and decompose model.So from the view of draw, 3D graphic objects can be represented to surface model and tissue model ,and grid can be the example for surface model.As two available approaches to represent 3D data, grid data structure and vector data structure both have advantages and limitations. Vector data structure can export fancy maps, but the constructor is too complex.In contract, grid data structure has a compact constructor and efficiency for use.Order grid is an offen adopted represent for 3D data. It use grid to represent DEM. The data format is simple, and easy to store. Triangulated irregular network is another way to represent DEM.It is very suitable for complex landform, but it has a complex topological relation to deal with.In contrast, order grid can be use easily.Path planning is a classical problem of AI. It starts from an initial state, and constantly chooses appropriate operate to change the state until reaches the goal state.There are many type of algorithm for solving the minimal way such as enumeration method, Dijkstra algorithm,traditional heuristic algorithm and genetic algorithm. Heuristic algorithm has the great significance for solving the minimal way on surface.After analysed the way to represent the 3D graphic objects and path planning finding, a new algorithm based on genetic algorithm and surface thinning for path planning on 3D surface is brought on.For the expression method of the environmental model, order grids are used to represent the 3D graphic objects in this paper. This can make solving simplify.An algorithm called Guotao Algorithm (GT) owned to Evolutionary Algorithm and surface thinning are used to find the minimal way on surface in this paper.GT is from TSP and plan on the minimal way on surface the differences of issues route in issueses, effective range in chromosomes(from the starting point to terminal point in the genes) and the range of choosings of genes (select gene C from the starting point to terminal point in the genes, select gene C from the Gene Database of C), wait for place revise to the algorithm, Introduce gene pool come and optimize some algorithms.Most way for surface thinning are fractionizing the whole surface. But this paper only fractionize the areas near the minimal way. The scale of problem is reduced in this way.Related algorithms are verified by the results of programs, attaining to the requirement.更多还原