Efficient distance computation between non-convex objects
Efficient distance computation between non-convex objects
复制标题
DOI：
10.1109/robot.1994.351059
复制
发表时间：
1994-05
期刊：
影响因子：
--
通讯作者：
Sean Quinlan
中科院分区：
文献类型：
--
作者：
Sean Quinlan
本文描述了一种计算非凸物体之间距离的有效算法。对象被建模为一组凸组件的并集。从这个模型出发，我们构造了一个基于球的层次边界表示。对象之间的距离是通过使用现有技术计算凸分量对之间的距离来确定的。效率的关键是一个简单的搜索例程，它使用边界表示来忽略大多数可能的组件对。通过接受返回结果中的相对错误，可以进一步提高效率。提出了几个实证试验来检验该算法的性能
This paper describes an efficient algorithm for computing the distance between nonconvex objects. Objects are modeled as the union of a set of convex components. From this model we construct a hierarchical bounding representation based on spheres. The distance between objects is determined by computing the distance between pairs of convex components using preexisting techniques. The key to efficiency is a simple search routine that uses the bounding representation to ignore most of the possible pairs of components. The efficiency can further be improved by accepting a relative error in the returned result. Several empirical trials are presented to examine the performance of the algorithm.>