Link-k LR可视多边形的判别算法研究

发布时间：2018-03-28 11:00

本文选题：计算几何　切入点：简单多边形　出处：《大连海事大学》2017年硕士论文

【摘要】：本文针对简单多边形中link-kLR可视多边形的判别问题进行研究。由于LR可视多边形的判别是求解巡视员最短路径等问题的基础问题,因此本课题的研究不仅具有理论意义,而且具有很大的实际应用价值。本文在论述简单多边形的可视性等概念的基础上,分析了link-k LR可视多边形的几何特征,给出了link-k反射点、link-k射点、link-k组件以及非冗余link-k组件的求解方法,详细论述了非冗余link-k组件的求解过程。分析了非冗余link-k组件影响简单多边形的link-kLR可视性的相关因素,依据计算出的非冗余link-k组件,提出了判别简单多边形是否为link-k LR可视多边形的充分必要条件,并采用将非冗余组件映射为圆上的有向弦,对所提出的判别条件进行了严格的证明。根据所提出的判别条件,以k2为例,设计出了时间复杂度为O(nlogn)的判别给定简单多边形是否为link-2LR可视多边形的求解算法,并指出该算法可拓展应用于求解一般link-kLR可视多边形的判别问题,同时对link-k LR可视多边形判别算法的时间性能做较为详细的分析。本文利用非冗余组件的相关特性,首次给出了时间复杂度为O(nlogn),对于给定简单多边形是否为link-kLR可视多边形的判别算法。
[Abstract]:Aiming at the problem of link-kLR in visual discrimination of simple polygon polygon are studied. The discriminant LR visibility polygons is a basic problem solving inspector shortest path problem, so this research has not only theoretical significance, but also has great practical value. This paper discussed the visibility on the concept of simple polygon analysis of the geometric features of link-k, the LR visibility polygons, given the link-k reflex point, link-k radio, link-k components and the method of solving non redundant link-k components, discusses in detail the process of solving non redundant link-k components. Analysis of the non redundant link-k component factors affecting link-kLR visibility of a simple polygon, based on the non redundant link-k the calculated component, proposed the necessary and sufficient conditions for simple polygon is link-k LR visibility polygons, and the non redundant The components are mapped to the circle to the string, the criteria proposed are proved strictly. According to the criteria proposed by K2, for example, designed the time complexity of O (nlogn) criterion is given a simple polygon algorithm for solving the link-2LR visibility polygons, and points out that the algorithm can discrimination is extended to solve general link-kLR visibility polygons, and do a more detailed analysis on the link-k LR visual discrimination polygon and the time performance of the algorithm. This paper uses the related characteristics of non redundant components are given for the first time, the time complexity is O (nlogn), for a given simple polygon is a polygon. Visual discrimination algorithm link-kLR

【学位授予单位】：大连海事大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O18

【相似文献】