3D中两个凸多边形之间的距离

我在3D中有两个凸多边形。他们都在不同的平面上，所以他们是一对面孔。3D中两个凸多边形之间的距离

什么来计算这两个多边形之间的最近距离的最简单的方法？

编辑：具有在第1多边形的端点以及在第二多边形另一个另一端点最短的线的长度。我正在寻找的距离是这条最短的线的长度。

来源

2011-02-24 Dmi

您是否正在寻找他们的两个最接近的边缘之间的距离的质心之间的距离，还是？ – 2011-02-25 00:00:43

两个最近的边缘。 – Dmi 2011-02-25 00:05:27

那么不是两个最近点之间的距离呢？你如何定义“最近边缘”，并给出一个合适的定义，你如何定义两个最近边缘之间的距离？ – Troubadour 2011-02-25 00:20:13

这是线性约束和二次目标函数的简单优化有限。有许多可以使用的算法，例如梯度下降。

来源

2011-02-25 02:15:44

您能否请进一步解释 - 二次函数是什么？ – 2011-02-25 02:28:11

目标是“最小化（x2 - x1）** 2 +（y2 - y1）** 2 +（z1 - z1）** 2”。给出最小距离的点也给出最小距离的平方。 – 2011-02-25 02:38:44

啊，对于每个边，约束条件是“x1，y1，z1位于这样的平面上”，“x1，y1，z1位于平面的这一半上”。辉煌！只要你能用一个等式*（我相信你可以，但说实话，我没有任何想法）在三维空间中划分一个平面，这会起作用，而且会更容易和比我的方法更容易出错。 +1！ – 2011-02-25 13:22:32

-3

环路通过所述第一对象的所有顶点，然后在循环中，通过所述第二对象的所有顶点循环。在最内层的循环中，比较两个当前顶点之间的距离并存储最小距离。我一直这样做，只要你没有一个可笑的大网眼，它几乎是瞬间的。

来源

2011-02-25 00:06:56 Davido

顶点可能不排队。例如，这两个多边形可以以直角相互接触，其中一个第二个多边形的顶点接触中间的第一个多边形。 – Dmi 2011-02-25 00:10:20

它不清楚你试过了什么。

This看起来可能对部分本身。

那么你所要做的就是检查所有的边缘对。我希望在尝试优化之前先实现这一点。

有可能是在考虑从一个质心的载体是在那个方向某种意义上其他，只考虑边缘的优化。

来源

2011-02-25 00:54:38 Keith

这和Davido的回答不一样。 – 2011-02-25 01:27:25

@BlueRaja，@Dmi。好的，错过了指出的情况。它仍然看起来像一个相对愚蠢的算法应该工作。计算原始（表面，边缘，顶点）对之间的距离还是确定需要计算哪些基元对的问题？或者确定即使检查所有原始对符合要求？ – Keith 2011-02-25 01:57:44

这样很好，除了一个多边形可以以直角“接触”其中一个多边形的中心。在这种情况下，第二多边形将具有接触第一多边形的平面的边或顶点，但仍然与第一多边形的边缘相距一定距离。 – Dmi 2011-02-25 02:10:46

那么，只有几种可能性;两个多边形之间的最短线路可以是：

之间的两个顶点
边缘和顶点
两个边缘（想像垂直平面内的两个多边形）
顶点之间之间关系与多边形的内部
或者多边形相交

案例1-3的全部都通过将每个边+顶点对视为线段来处理，并列举distance between all line-segment pairs。

情况4，找到distance between each vertex and the other polygon's plane。检查以确保该线（从顶点到平面上的最近点）位于另一个多边形内部;如果不是，那么最短的路线到另一多边形将在其周边，这是已经在情况1或2
照顾（请确保为做这种检查既多边形）

对于情况5，至少一个线段必须与另一个多边形的区域相交 - 如果它们在它们的周界相交，我们将在1-3情况下捕获它，并且如果顶点与该区域相交，则我们将具有在案例4中发现它。因此，只需检查intersection of each edge with the other polygon's plane并查看交点是否在另一个多边形内。
（请确保为两个多边形做此项检查）

采取所有这些发现的最小距离，我们就大功告成了。

来源

2011-02-25 02:14:01

这看起来很简单，我会试试看。 – Dmi 2011-02-25 03:30:59

我想你忘了提及2个多边形平行的情况。它包含在1-4中，所以没有问题，但是在进行投影等数学运算时应该牢记这一点。由于搜索交叉点而不考虑并行情况往往会导致令人讨厌的错误。例如，5的检查需要观察（每个边与另一个多边形平面的交点）。 – Alink 2011-02-25 06:27:28

@Alink：正确，我没有提到它，因为它包含在1-4中，但这是值得担心的。其他多边形案例中的边缘/内部是另一个案例：它包含在案例3-4中，但仍然需要注意（至少用于测试）。 – 2011-02-25 13:10:39

大多数人都提出了这个线程是“走一个多边形的所有点/边，并比较各点其他的/边缘”。如果你所做的只是比较两个相当简单的多边形，并且你不太关心如何快速做到这一点，那么这可能会正常工作。

但是，如果你想有一个相当简单和更好的方法。如Ben Voigt所建议的那样，使用二次优化方法（即Quadratic Programming）。基本上，您的多边形是您的一组线性约束，即您的解决方案点必须位于多边形的每个边的内侧（这是一个不等式约束）。而你的优化成本函数就是欧几里得距离，即标准公式中的Q就是单位矩阵。一旦出现这样的问题，你可以使用一个解决这个问题的库（这里有许多这样的问题），或者你可以从一本书中学习它，并为它编译你自己的代码（这是一个相当简单的编码算法）。

如果你想这样做，例如，如果是简单的多边形到多边形测试是迈向更复杂的三维形状的第一步（如由多边形的固体）真正的方法。那么，你应该很可能只是使用已经做到这一点的软件包。 Here是一组碰撞检测库，其中许多输出穿透深度或等效最小距离。

来源

2011-02-25 03:14:47

谢谢，这看起来像一个有趣的话题。我不会走向更复杂的形状，只是寻找3D面的简单距离对。 – Dmi 2011-02-25 03:28:47

3D中两个凸多边形之间的距离

回答

相关问题