Efficient Algorithms for Non-Iterative Contact Detection of Convex Polyhedra and Application on Minkowski Sum
Date Issued
2010
Date
2010
Author(s)
Liu, Chien-Chia
Abstract
The non-iterative method proposed in this research solves the contact detection problem of polyhedral blocks analytically and efficiently. The traditional contact detection of polyhedral blocks is limited to geometrical shapes. As the shapes become more complex, the computing time increases dramatically.
This research focuses on the algorithms and the implementation of polyhedral contact detection based on a non-iterative method of common plane approach. The complexity of naïve implementation is O(n^2), which n is the number of edges of the polyhedron. This research develops a control vertex data structure and the Arc Forward Intersection Decomposition (AFID) algorithm for reducing the complexity to linear order. In addition, the errors while calculating the gap in using the Cundall’s iterative scheme are shown.
Moreover, the control vertex and the AFID algorithm can apply on Minkowski sum, a well know mathematic operation. The Minkowski sum is used in many application domains, such as computer-aided design, robotics, spatial planning, mathematical morphology, and image processing. There is a great impact for computer science that improving computation of Minkowski sum. Thus, the control vertex and the AFID algorithm enable computing both contact detection for convex polyhedral and Minkowski sum efficiently.
Subjects
Contact detection
Control vertex
Minkowski sum
Common plane
Gaussian map
Slope diagram
Convex polyhedra
Computational geometry
File(s)![Thumbnail Image]()
Loading...
Name
ntu-99-R97521608-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):40448714743f0e23aac2c8d704904d5b