Research on Exact Minkowski Sum Algorithm of Convex Polyhedron Based on Direct Mapping

Qing Jia Geng; Xi Juan Guo; Ya Zhang

doi:10.4028/www.scientific.net/AMR.225-226.377

Paper Titles

A Brief Study on Successful Reform of English Teaching in China Based on Web
p.360

Studies on the Expanded Sequence Matrix and its Application in Flowshop Layout
p.364

GASD Based Relayout Method in Mass Customization Manufacturing Quality Assurance
p.368

Multi-Objective Optimization Algorithm Based on Gene Expression Programming and Virus Evolution
p.372

Research on Exact Minkowski Sum Algorithm of Convex Polyhedron Based on Direct Mapping
p.377

GM(1,1) Model of Moving Average Operation to the Original Sequence and its Application
p.381

A System Design and Implementation of Home Monitoring Based on ZigBee Technology
p.385

The Numerical Simulation of the Aquifer Thermal Energy Storage Technology
p.390

Suggestion of Introducing the Human Reliability into Dam Risk Analysis
p.395

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 225-226Research on Exact Minkowski Sum Algorithm of...

Research on Exact Minkowski Sum Algorithm of Convex Polyhedron Based on Direct Mapping

Abstract:

Minkowski sum has become an effective method in collision detection problem, which is a branch of computation geometry. Separated from the previous algorithm based on the traditional Gaussian Map, a new algorithm of computing exact Minkowski sum of convex polyhedron is proposed based on direct mapping method in the paper, and the correctness of direct mapping method is testified. The algorithm mapping the convex polyhedron into the bottom of regular tetrahedron according to the definition of Regular Tetrahedron Mapping and Point Projection, so the problem become form 3D to 2D. Comparing with the previous algorithm, the algorithm posed in the paper establishes mapping from 3D to 2D directivity, and only compute the overlay of one pair of planar subdivision. So, the algorithm’s executing efficiency has been improved in compare with the previous algorithm.

You might also be interested in these eBooks

Advanced Research on Automation, Communication, Architectonics and Materials

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 225-226)

Pages:

377-380

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.225-226.377

Citation:

Cite this paper

Online since:

April 2011

Authors:

Qing Jia Geng, Xi Juan Guo, Ya Zhang

Keywords:

Convex Polyhedron, Minkowski Sum, Overlay Algorithm, Point Projection, Regular Tetrahedron Mapping

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] T.Lozano-Perez. Spatial Planning: A Configuration Space Approach. IEEE Trans- action on Computers, 32(2):108-120. (1983)

DOI: 10.1109/tc.1983.1676196

Google Scholar

[2] P.K. Ghosh. A Unified Computational Framework for Minkowski Operations. Computer and Graphics, 17(4):357-378. (1993)

DOI: 10.1016/0097-8493(93)90023-3

Google Scholar

[3] Y.Y.Wu, J.J. Sha, J.K. Dayidson. Improvements to Algorithms for Computing the Minkowski Sum of 3-polytopes. Computer-Aided Design, 35(13):1181-1192. (2003)

DOI: 10.1016/s0010-4485(03)00023-x

Google Scholar

[4] E.Fogel, D.Halperin. Exact Minkowski Sums of Convex Polyhedra. In Proceedings of the 21st ACM Symposium on Computational Geometry, Pisa, Italy, 382-383. (2005)

DOI: 10.1145/1064092.1064157

Google Scholar

[5] X.J. Guo, Y.L. Gao, Y. Liu. Optimization Algorithm for Computing Exact Minkowski sum of 3D Convex Polyhedra, IJIJIC, 1401-1410. (2008)

Google Scholar

[6] X.J. Guo, L. Xie. Optimal accurate Minkowski sum approximation, ICIC 2008, 197–206. (2008)

Google Scholar

[7] M.de Berg, M.van Kreveld, and M.Overmars, etal. Computational Geometry: Algorithm and application, Second Edition, Beijing: Tsinghua University Press. (2005)

Google Scholar