IGSNRR OpenIR
求解简单多边形间最小距离的一个线性时间算法
毛定山1; 崔先国2; 李行3; 吴哲辉2
2008
Source Publication中国图象图形学报
ISSN1006-8961
Volume013Issue:012Pages:2400
Abstract计算简单多边形间的最小距离,在所有与几何图形计算有关的领域中,一直以来都是一个基本问题。为了更快地求解简单多边形的最小距离,提出了一个基于关联多边形三角化分割的简单多边形间最小距离的求解算法。该算法的主要思想是:首先构造一个关联多边形把两个多边形联系起来,其目的是把最小距离限制在这个关联多边形内;然后根据两个多边形的最小边界矩形包围框间的不同位置关系,详细阐述了关联多边形的构造过程,同时论述了关联多边形是一个简单多边形。为了计算最小距离,首先要对关联多边形进行三角化分割,并使最小距离位于三角化分割结果中某一个三角形区域内,或者至多位于两个相邻三角形区域内;之后通过对所有三角形进行遍历来找出最小距离及其所在的位置。该算法的时间复杂度是线性的。
Language英语
Document Type期刊论文
Identifierhttp://ir.igsnrr.ac.cn/handle/311030/76606
Collection中国科学院地理科学与资源研究所
Affiliation1.中国科学院地理科学与资源研究所
2.山东科技大学
3.华东师范大学
First Author Affilication中国科学院地理科学与资源研究所
Recommended Citation
GB/T 7714
毛定山,崔先国,李行,等. 求解简单多边形间最小距离的一个线性时间算法[J]. 中国图象图形学报,2008,013(012):2400.
APA 毛定山,崔先国,李行,&吴哲辉.(2008).求解简单多边形间最小距离的一个线性时间算法.中国图象图形学报,013(012),2400.
MLA 毛定山,et al."求解简单多边形间最小距离的一个线性时间算法".中国图象图形学报 013.012(2008):2400.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[毛定山]'s Articles
[崔先国]'s Articles
[李行]'s Articles
Baidu academic
Similar articles in Baidu academic
[毛定山]'s Articles
[崔先国]'s Articles
[李行]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[毛定山]'s Articles
[崔先国]'s Articles
[李行]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.