Full Text:   <1629>

CLC number: TP202

On-line Access: 

Received: 2006-05-20

Revision Accepted: 2006-06-21

Crosschecked: 0000-00-00

Cited: 1

Clicked: 3236

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2006 Vol.7 No.9 P.1522~1529

http://doi.org/10.1631/jzus.2006.A1522


A new fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram


Author(s):  YANG Cheng-lei, QI Meng, MENG Xiang-xu, LI Xue-qing, WANG Jia-ye

Affiliation(s):  School of Computer Science and Technology, Shandong University, Jinan 250100, China

Corresponding email(s):   chl_yang@sdu.edu.cn

Key Words:  Computational geometry, Polygon, Voronoi diagram, Distance computation


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[J]. Journal of Zhejiang University Science A, 2006, 7(9): 1522~1529.

@article{title="A new fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram",
author="YANG Cheng-lei, QI Meng, MENG Xiang-xu, LI Xue-qing, WANG Jia-ye",
journal="Journal of Zhejiang University Science A",
volume="7",
number="9",
pages="1522~1529",
year="2006",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.2006.A1522"
}

%0 Journal Article
%T A new fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram
%A YANG Cheng-lei
%A QI Meng
%A MENG Xiang-xu
%A LI Xue-qing
%A WANG Jia-ye
%J Journal of Zhejiang University SCIENCE A
%V 7
%N 9
%P 1522~1529
%@ 1673-565X
%D 2006
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2006.A1522

TY - JOUR
T1 - A new fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram
A1 - YANG Cheng-lei
A1 - QI Meng
A1 - MENG Xiang-xu
A1 - LI Xue-qing
A1 - WANG Jia-ye
J0 - Journal of Zhejiang University Science A
VL - 7
IS - 9
SP - 1522
EP - 1529
%@ 1673-565X
Y1 - 2006
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2006.A1522


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.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1] Choi, Y.K., Li, X.Q., Rong, F.G., Wang, W.P., Cameron, S., 2006. Computing the Minimum Directional Distance between Two Convex Polyhedra. HKU CS Tech Report TR-2006-01, University Of Hong Kong. Http://www. cs.hku.hk/research/techreps/document/TR-2006-01.pdf.

[2] Cohen, J.D., Lin, M.C., Manocha, D., Ponamgi, M.K., 1995. I-collide: An Interactive and Exact Collision Detection System for Large Scale Environments. Proceedings of ACM International 3D Graphics Conference, ACM Press, New York, 1:189-196.

[3] Dobkin, D., Kirkpatrick, D., 1990. Determining the separation of preprocessed polyhedra—A unified approach. Lecture Notes in Computer Science, 443(ICALP-90):400-413.

[4] Edelsbrunner, H., 1985. Computing the extreme distance between two convex polygons. J. Algorithms, 6(2):213-224.

[5] Guibas, L., Hsu, D., Zhang, L., 2000. A hierarchical method for real-time distance computation among moving convex bodies. Computational Geometry: Theory and Applications, 15(1-3):51-68.

[6] Hudson, T.C., Lin, M.C., Cohen, J.D., Gottschalk, S., Manocha, D., 1997. V-collide: Accelerated Collision Detection for VRML. Proceeding of VRML 1997: Second Symposium on the Virtual Reality Modeling Language. ACM Press, New York, p.119-125.

[7] Li, X.Q., Meng, X.X., Wang, C.Y., Wang, W.P., Chung, K., Yiu, S.M., 2003. Detect collision of polytopes using a heuristic search for separating vectors. Chinese Journal of Computer, 26(7):837-847.

[8] Lin, M.C., Canny, J.F., 1991. A Fast Algorithm for Incremental Distance Calculation. Proceeding of the IEEE International Conference on Robotics and Automation. IEEE Computer Society Press, Sacramento, CA, 2:1008-1014.

[9] Lin, M.C., Manocha, D., Canny, J.F., 1994. Fast Contact Determination in Dynamic Environments. Proceeding of the IEEE International Conference on Robotics and Automation. IEEE Computer Society Press, San Dieg, CA, 1:602-608.

[10] Mirtich, B., 1998. V-clip: fast and robust polyhedral collision detection. ACM Trans. on Graphics, 17(3):177-208.

[11] O’Rourke, J., 1994. Computational Geometry in C. Cambridge University Press, New York, p.260.

[12] Ponamgi, M.K., Manocha, D., Lin, M.C., 1997. Incremental algorithms for collision detection between polygonal models. IEEE Trans. on Visualization and Computer Graphics, 3(1):51-64.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE