Please wait a minute...
ZJUS-A
Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering)  2006, Vol. 7 Issue (9): 1522-1529    DOI: 10.1631/jzus.2006.A1522
Geometric Modeling & Computing     
A new fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram
YANG Cheng-lei, QI Meng, MENG Xiang-xu, LI Xue-qing, WANG Jia-ye
School of Computer Science and Technology, Shandong University, Jinan 250100, China
Download:     PDF (0 KB)     
Export: BibTeX | EndNote (RIS)      

Abstract  Computing the distance between two convex polygons is often a basic step to the algorithms of collision detection and path planning. Now, the lowest time complexity algorithm takes O(logm+logn) time to compute the minimum distance between two disjoint convex polygons P and Q, where n and m are the number of the polygons’ edges respectively. This paper discusses the location relations of outer Voronoi diagrams of two disjoint convex polygons P and Q, and presents a new O(logm+logn) algorithm to compute the minimum distance between P and Q. The algorithm is simple and easy to implement, and does not need any preprocessing and extra data structures.

Key words： Computational geometry      Polygon      Voronoi diagram      Distance computation     
Received: 20 May 2006     
CLC:  TP202  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
YANG Cheng-lei
QI Meng
MENG Xiang-xu
LI Xue-qing
WANG Jia-ye
Cite this article:

YANG Cheng-lei, QI Meng, MENG Xiang-xu, LI Xue-qing, WANG Jia-ye. A new fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2006, 7(9): 1522-1529.

URL:

http://www.zjujournals.com/xueshu/zjus-a/10.1631/jzus.2006.A1522     OR     http://www.zjujournals.com/xueshu/zjus-a/Y2006/V7/I9/1522

[1] Jie Zhang, Guang-xu Han, Xin-biao Xiao, Rui-qian Wang, Yue Zhao, Xue-song Jin. Influence of wheel polygonal wear on interior noise of high-speed trains[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2014, 15(12): 1002-1018.
[2] LIU Guang-hui, CHEN Chuan-bo. A new algorithm for computing the convex hull of a planar point set[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2007, 8(8): 1210-1217.
[3] Liu Hu-yao, He Yuan-jun. Algorithm for 2D irregular-shaped nesting problem based on the NFP algorithm and lowest-gravity-center principle[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2006, 7(4): 570-576.
[4] KIM Chong-Min, WON Chung-In, RYU Joonghyun, CHO Cheol-Hyung, BHAK Jonghwa, KIM Deok-Soo. Parameter selection of pocket extraction algorithm using interaction interface[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2006, 7( 9): 5-.
[5] WANG Jin, LU Guo-dong, PENG Qun-sheng, WU Xuan-hui. Line clipping against polygonal window algorithm based on the multiple virtual boxes rejecting[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2005, 6(Supplement 1): 100-107.