Carretero Juan A, Nahon Meyer A
Department of Mechanical Engineering, University of New Brunswick, Fredericton, Canada.
IEEE Trans Syst Man Cybern B Cybern. 2005 Dec;35(6):1144-55. doi: 10.1109/tsmcb.2005.850172.
Determining the minimum distance between convex objects is a problem that has been solved using many different approaches. On the other hand, computing the minimum distance between combinations of convex and concave objects is known to be a more complicated problem. Most methods propose to partition the concave object into convex subobjects and then solve the convex problem between all possible subobject combinations. This can add a large computational expense to the solution of the minimum distance problem. In this paper, an optimization-based approach is used to solve the concave problem without the need for partitioning concave objects into convex pieces. Since the optimization problem is no longer unimodal (i.e., has more than one local minimum point), global optimization techniques are used. Simulated Annealing (SA) and Genetic Algorithms (GAs) are used to solve the concave minimum distance problem. In order to reduce the computational expense, it is proposed to replace the objects' geometry by a set of points on the surface of each body. This reduces the problem to an unconstrained combinatorial optimization problem, where the combination of points (one on the surface of each body) that minimizes the distance will be the solution. Additionally, if the surface points are set as the nodes of a surface mesh, it is possible to accelerate the convergence of the global optimization algorithm by using a hill-climbing local optimization algorithm. Some examples using these novel approaches are presented.
确定凸物体之间的最小距离是一个已经通过许多不同方法解决的问题。另一方面，计算凸物体和凹物体组合之间的最小距离是一个更复杂的问题。大多数方法建议将凹物体划分为凸子物体，然后求解所有可能子物体组合之间的凸问题。这会给最小距离问题的解决方案增加大量计算成本。在本文中，使用一种基于优化的方法来解决凹问题，而无需将凹物体划分为凸块。由于优化问题不再是单峰的（即有多个局部极小值点），因此使用全局优化技术。模拟退火（SA）和遗传算法（GA）被用于解决凹最小距离问题。为了降低计算成本，建议用每个物体表面上的一组点来代替物体的几何形状。这将问题简化为一个无约束组合优化问题，其中使距离最小化的点的组合（每个物体表面上一个）将是解决方案。此外，如果将表面点设置为表面网格的节点，则可以通过使用爬山局部优化算法来加速全局优化算法的收敛。给出了使用这些新方法的一些示例。
