CLC number: TP202
On-line Access: 2024-08-27
Received: 2023-10-17
Revision Accepted: 2024-05-08
Crosschecked: 0000-00-00
Cited: 1
Clicked: 5627
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.
[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>