|Table of Contents|

 New Algorithm of Joining a Set of Segments into a Simple Polygon(PDF)

《哈尔滨理工大学学报》[ISSN:1007-2683/CN:23-1404/N]

Issue:
2018年06期
Page:
138-145
Research Field:
计算机与控制工程
Publishing date:

Info

Title:
 New Algorithm of Joining a Set of Segments into a Simple Polygon
Author(s):
 JIN Hui1LIU Runtao2
 1School of Sciences, Harbin University of Science and Technology, Harbin 150080,China;
2Institute of Information and Scientific Computing Technology, Harbin University of Science and Technology, Harbin 150080,China
Keywords:
Keywords:set of segments simple polygon Delaunay triangulation the enlargement of quadrilateral length
PACS:
TP39141
DOI:
10.15938/j.jhust.2018.06.025
Abstract:
 Abstract:For the problem of how to link a set of segments to a simple polygon with the shortest whole length, a sufficient condition that a given set of segments can be joined into a simple polygon is given It is proved that the nearest point or second nearest point of the end point can be obtained in Delaunay triangulation for the end points of a set of segments S Based on this result, the method of joining a segment into a polygon is given for getting the polygon with the shortest length Then, a new algorithm for joining a set of segments into a simple polygon with shorter whole length is presented The analysis is done on the time complexity for new algorithm The correctness of new algorithm is proved The comparison and analysis are done for the new algorithm to show that better result can be obtained with the new algorithm

References:

 
[1]周培德, 王树武, 李斌 连接不相交线段成简单多边形(链)的算法及其实现[J] 计算机辅助设计与图形学学报, 2002, 14(6): 522-525
[2]周培德 平面线段集三角剖分的算法[J] 计算机工程与科学, 2003, 25(1): 20-22
[3]袁小翠, 吴禄慎, 陈华伟 Delaunay三角剖分算法改进与对比分析[J] 计算机应用与软件, 2016, 33(9):163-166
[4]高莉 改进的Delaunay三角剖分算法研究[D] 兰州:兰州交通大学, 2015:126-188
[5]周培德 连接两个多边形成一条回路的算法[J] 计算机研究与发展, 1996(11): 865-868
[6]周培德计算几何——算法设计与分析(第2版)[M] 北京: 清华大学出版社, 20054: 166-176
[7]杨洋, 刘学军, 肖斐 复杂多边形快速融合算法与实现[J] 地理空间信息, 2016, 14(3):52-55
[8]SHEWCHUK J R Delaunay Refinement Algorithms for Triangular Mesh Generation[J] Computational Geometry Theory & Applications, 2014, 47(7):741-778
[9]余代俊, 蒲朝旭, 朱逍贤 一种Delaunay三角剖分的改进算法[J] 测绘通报, 2014(6):51-54
[10]范俊甫, 马廷, 周成虎,等 分治法在GIS多边形快速合并算法中的应用及效率提升评价模型[J] 地球信息科学学报, 2014, 16(2):158-164
[11]袁翰, 李伟波, 陈婷婷 对构建Delaunay三角网中凸壳算法的研究与改进[J] 计算机工程, 2007, 33(7):70-72
[12]FERNANDO de GOES, MEMARI Pooran, MULLEN Patrick Weighted Triangulations for Geometry Processing[J] ACM Transactions on Graphics, 2014, 33(3):1-13
[13]李源, 李永钢 基于扫描线的线段求交算法[J] 计算机光盘软件与应用, 2013(17):311-312
[14]王中辉, 闫浩文 带约束折线的平面散点集Delaunay三角剖分[J] 测绘与空间地理信息, 2011, 34(1):46-47
[15]许文帅, 龙毅, 周侗,等 面向复杂多边形合并的视觉邻近探测与缝合算法[J] 地理与地理信息科学, 2014, 30(1):125-126
[16]刘润涛, 王三, 安晓华 求平面点集凸壳的一种新算法[J] 计算机工程与应用, 2009, 45(3):58-59
[17]陈正鸣, 李春雷 多边形链求交的改进算法[J] 计算机辅助设计与图形学学报, 2004, 16(12): 1713-1718

Memo

Memo:
-
Last Update: 2019-03-26