船体和盒子之间的最短距离

Question

如何找到凸包与轴对齐的盒子之间最接近的距离？所谓最接近的距离是指凸包和盒子上最靠近彼此的点。我们可以假设凸包和盒子不相交。

凸包由面、顶点组成，如果必要，我可以将面三角化。

- I J

Answer 1

这篇文章提供了一种算法来寻找两个凸包之间的最近点对。链接在此：http://realtimecollisiondetection.net/pubs/SIGGRAPH04_Ericson_GJK_notes.pdf 有一段时间，我认为其中一个凸包是AABB就可以使这个算法变得不必要。但不幸的是，我没有发现这是真的。

这个算法的思想是你取两个凸包的Minkowski差。最近的点对将是该Minkowski差中距离原点最近的点。Cartheodory定理表明，在d维空间中，你只需要d+1个点来表示凸包中的一个点。所以基本上你选择d+1个大小的Minkowski差集，并找到它们与原点的最近距离。通过迭代算法找到最靠近原点的点。

- I J

Answer 2

对于凸多边形在盒子内（或任何其他凸对象）的情况：

如果它们不相交，则凸多边形上最近的点将是凸多边形的顶点，而不是面的中心。

简单地遍历凸多边形的所有顶点并计算到盒子每一侧的距离，将让您找到一对点（凸多边形的顶点+盒子面上的点）。请注意，如果凸多边形的面与盒子的面平行，则会得到多个距离相同的点对。

凸多边形在盒子外：

点对包含凸多边形或盒子边缘上的点和第二个对象上的点。遍历凸多边形和盒子的所有边缘，并计算到另一个对象的所有面的距离似乎是一种方法，但更好的方法应该存在。

- Alexei Levenkov

---

不要这么想。想象一下一个AABB和另一个凸包，这是一个定向盒子，它有一个面最靠近盒子角的面。在这种情况下，最近的一对是盒子的角和凸包表面上的一个点。 - I J

我认为最接近的一对点总是有一个盒子顶点或一个包络顶点。然后，一种可能的解决方案是首先迭代盒子顶点并找到与包络面的最近距离。然后迭代包络顶点并找到与盒子面的最近距离。不确定是否漏掉了某种可能性。 - I J

在我的考虑中，我只考虑了盒子内的外壳。如果盒子不包含外壳，那么盒子的一个顶点可能在这对点之间。只需要一个点是顶点 - 想象一下巨大的盒子，旁边是小小的外壳，位于盒子的中心。所以，是的，你的建议更通用，并且看起来是正确的。 - Alexei Levenkov

我会收回我的声明。想象一个巨大的盒子和一个微小的船体以一定角度经过边缘。最近的一对将是边缘上的一个点和船体表面上的一个点。 - I J

这可能就是它：http://realtimecollisiondetection.net/pubs/SIGGRAPH04_Ericson_GJK_notes.pdf - I J