离散点凹包多边形生成研究开题报告

1. 研究目的与意义（文献综述包含参考文献）

1.1课题的背景和意义平面多边形是由二维空间中一组有序排列的不共线点连接成的封闭区域，它是许多真实物体外形的一种方便而又准确的描述工具，并且在计算机上容易实现。很多图形学的算法如裁剪、着色、消隐及轮廓填充等都是建立在多边形研究的基础上。平面多边形又可分为简单多边形和非简单多边形。简单多边形^[1]指的是非相邻边互不相交的多边形即⑴相邻两条边只有一个公共点；⑵任意不相邻的两条边彼此不相交；⑶封闭几何内部不存在环路（以下简称简单多边形为多边形）。凹包为简单多边形的一种。构造简单多边形在图形处理、模式识别、实体造型等领域有着广泛的应用，如自动符号识别，机器人运动中绕过障碍物，屏幕显示固体对象的形状，地理信息系统^[2-6]，地理信息传感器网络^[3-6]等，同时也在实际工程应用中也有着重要价值，例如在铺设石油管道时，如何将各个副井有序的连线构成一个简单多边形，并使工程造价最低；规划小区内天然气管道铺设，确保各管道之间不相交或者不重叠，整个管道网的入口和出口是否在同一处；选择一条最优路径遍历每个社区站点，使得每个站点只经过一次且路程最短。针对简单多边形自身的特点，设计具有算法性能较优、稳定性好，能够满足实际应用需要的构造算法是十分必要的，对于理论研究和工程应用都有重要的意义。 1.2国内外研究现状 根据构造简单多边形的原始数据对象的不同，可将多边形构造算法分为两类：离散点集构造法、线段集构造法。下面分别对已有算法进行介绍： 1.2.1离散点集构造法离散点集构造法的基本思想为对于平面上有限离散点集S={Si|i=0,1,2, ,n}，其排列顺序S0,S1,S2,S3,,Sn ,通过随机点序列相互连接构成的多边形可能存在自相交现象，不能满足简单多边形的特性。为此，需要按照某种规则对点集S进行排序，生成新的有序点集合,顺次连接各点来,构造简单多边形,目前已有的算法包括二分排序法、坐标平移判断角法^[7]、极坐标排序法、凸壳划分法等。 ⑴二分排序法^[8] 二分排序法在给定的顶点集S中选出X坐标（或Y坐标）方向上的最大值点和最小值点，则点集中其余点分布于这两点间连线L的两侧。对于一侧的点，按X值非递减次序排列；对另一侧的点，按X值非递增次序排列，最后得到新的有序点集S '，顺次连接S '中各点，构造简单多边形。若所有点均位于直线L的同一侧，则找Y方向的最大值和最小值，得直线L，再按二分排序算法，作同样的处理。若y 最大值点不止一个，则将这些点按x值由大到小排列，再令其属于点集S1内；若 y 最小值点不止一个，则将这些点按x值由小到大排列，再令其属于点集S2内；之后将S1按 y 值非递减次序排列，将S2 按 y 值非递增次序排列，其余作同样的处理。 ⑵极坐标排序法^[9-11] 文献^[10]在极坐标平面内，选取点集S 中任一点S0作为核心点(原点)，将其余点Si(i=1,2,,n) 分别和S0相连构成向量，计算向量的模和辐角，然后按辐角的大小来确定的次序，辐角小的点优先排序。如果两个点的辐角相同，则按照模小的优先排序， 最后生成有序点集，并将各点顺序连接构造简单多边形。但其不足之处在于若存在几个顶点与原点构成向量的极角相等的情况时，则可能会导致多边形的边重合的现象。文献^[10]则对角度排序法作出了进一步的改进，引入种子点的定义，种子点为点集所构成的点封闭区域内某点，将其设置为坐标原点，计算点集中的点与种子点的连线与Y轴正半轴的夹角α，规定逆时针方向为正向，α值的范围为[0,2]，通过角度α的大小来确定其对应顶点的顺序，然后顺次连接排序后的点构造简单多边形。一般选取多边形的几何中心、重心等来作为种子点。但是该算法仍然存在一定的缺陷，算法中种子节点的选取至关重要，不同的种子点造成连接顺序不同，还会出现错误的排序，需要先验知识，文中介绍了一种通过扰动产生新的种子点，重新计算直到获取满意的结果，但是这样降低了程序的效率，且当两个点的角度相同时也可能会导致边重合或者相交的现象出现。文献^[11]提出了一种基于方位角的多边形造算法，通过选取点集S 内部某一位置点作为主井（其中主井位置点不属于点集S）向周围副井(即点集S 中的点)作射线，计算所有射线的方位角并按照大小顺序排序，再依次连接起来构造简单多边形。与文献^[10]相同，该算法同样未考虑方位角大小相同的情况。 ⑶凸壳构造法^[12-13] 文献^[12]提出了一种基于凸壳划分点集的构造算法，首先计算点集的凸壳及凸壳中轴，将点集划分为m(1≤m≤n)个子点集，然后逐层求取各个子点集的凸壳，计算最内层凸壳与相邻的次内层凸壳顶点的距离^[14]，根据距离大小来重新划分最内层凸壳的顶点集，最后采用同样的划分方法对各层子集进行处理，获得一条子路径，在最外层凸壳顶点处连接所有子路形成一条回路即简单多边形。算法的时间复杂度为O(n2logn)。文献^[13]提出一种基于凸壳划分的最大面积简单多边构造形算法。该算法通过计算离散点集的凸包确定初始多边形，然后搜索剩余点集中与多边形上每条边构成面积最大且不包含内点的顶点，将面积取值最大的顶点插入到相应边的两个端点之间，重复这一过程直至所有点都被测试完为止。该算法复杂度为O(n3)。 ⑷可视区法^[15] 文献^[15]首先通过随机选点的方式构造初始三角形，然后按照各边的可视性逐步把点集中剩余的点插入到多边形中，最后直至所有点全部插入，简单多边形构造完毕。算法时间复杂度为O(n2logn)。

[1] 周培德.计算几何算法设计与分析(第四版)[M].北京:清华大学出版社,2012:134-150. [2] 刀学龙,徐鹏.一种平面二维坐标点排序新方法[J].玉溪师范学院学报,2006,22 (6): 73 －75. [3] 王威信,郝永平.离散点集二分排序构造多边形的算法[J].沈阳工业学院学报,1997, 16(4):11-14. [4] Michael, Laszlo. Computational Geometry and Computer Graphics in C .Prentice Hall, Inc. United Stated.1996, 109-112. [5] 何国祥.解析法计算多边形面积的一点小建议[J].城市勘测,1997,(2): 31-32. [6] 刘吉余,魏华彬,李丽丽等.基于方位角的多边形构建法在储量计算中的应用[J].物探化探计算技 术,2008,30(2):117-119. [7] 周培德,周忠平,张欢.寻求中国货郎担问题最短回路的多项式时间算法[J].北京理工大学学 报,2000,20(2):201-204. [8] Tereshchenko, Muravitskiy. Constructing a Simple Poly gonalizations.World Academy of Science Engineering and Technology. 2011:668-671. [9] 周培德.计算几何[M].北京:清华大学出版社,南宁:广西科学技术出版社,2000. [10] David Dailey, Deborah Whitfield.Constructing Random Polygons[C].New York,NY,USA. 2008: 119-124. [11] H.J.Miller, J.Han, Eds. Geographic Data Mining and Knowledge Discovery. CRC Press, 2001. [12] 乌仔伦,刘瑜,张晶.地理信息系统原理、方法和应用[M].北京:科学出版社,2001. [13] Galton, M.Duckham.What is the region occupied by a set of points. GIScience, ser. Lecture Notes in Computer Science. 2006,4197(4):8198. [14] A.Galton.Dynamic collectives and their collective dynamics.Lecture Notes in Computer Science.2005, 3693(4):300315. [15] M.F.Worboys, M.Duckham.Monitoring qualitative spatiotemporal change for geosensor networks. networks.International Journal of Geographic Information Science.2006,20(10):1087110.

2. 研究的基本内容、问题解决措施及方案

平面多边形是由二维空间中一组有序排列的不共线点连接成的封闭区域，它是许多真实物体外形的一种方便而又准确的描述工具，并且在计算机上容易实现。

多边形可分为简单多边形和非简单多边形，简单多边形指的是非相邻边不相交且封闭几何内部不存在环路的多边形，其在计算机图形学、图形图像处理、实体造型等领域有着广泛应用，如符号识别、地理信息系统、地理信息传感器网络等。

因此，本课题要研究或者解决的问题是：设计一种效率较高且满足实际需要的简单多边形构造算法。