将凸多边形拟合到另一个多边形

Question

我正在寻找一种算法,我可以检查凸多边形(形状1)是否适合另一个多边形(形状2).

我的第一项研究将我带到了"包装不规则形状".这在我看来有点矫枉过正.我只有一个容器和一个对象.

形状1通常是凸多边形.形状2可以是凸的或凹的.

我的应用:我有三维激光扫描仪测量原木,这给我形状2.我也有不同的切割轮廓,我认为凸形船体,形状1.

现在我想检查切割轮廓是否适合我的激光轮廓.

Answer 1

动机。如果你问某个半径的圆盘 B 是否可以放入多边形 P 中，那么计算几何中有一个标准的方法：检查最大内切圆的半径是否不小于；看到这个stackoverflow答案：

上述计算最大内切圆的算法相当“简单”：计算所谓的广义Voronoi图，取间隙半径最大的Voronoi节点。（这只是动机，请继续阅读一分钟。）

在你的情况下，你的形状 2 不是一个球；好吧，准确地说，不是欧几里得球。但是，实际上，您的形状 2 作为凸多边形 B，可以定义凸距离函数并计算该多面体距离函数下的Voronoi 图。但这是更多的理论背景，可能不是您想要为生产代码实现的东西。

这些 Voronoi 图与计算偏移曲线密切相关，例如，用于 NC 加工中的刀具路径刨削。有关一些讨论和下图，请参阅此博客文章：

当且仅当距离 r 处有一条偏移曲线时，半径为 r 的球 B 适合形状 P。（您实际上获得了所有有效中心的集合，即半径 r 处的偏移曲线内的那些中心。）并且这些偏移曲线可以在数学上描述为Minkowski 差，如博客文章中所述。

闵可夫斯基差。 所以现在我们可以回到你最初的问题了。凸多边形 B 是否适合多边形 P？当且仅当 Minkowski 差 (PB) 是一个非空集时它才会这样做；(PB) 以外的任何中心都可以作为示例。

基于上图的更多细节：让我们用 -B = {-v : v in B} 表示点反射后的形状 B。（在任何你喜欢的地方选择原点；我用小十字表示原点。）现在把 -B 想象成一支钢笔（蓝色）的形状，你沿着边界移动你的钢笔（实际上是十字） P. 你得到了灰色区域。（这是P 与 -B 的边界的Minkowski 和。）从 P 中去除灰色区域，您得到 Minkowski 差 PB。选择 PB 内的任意一点，并在那里放置 B 的副本；它将适合 P。我为您放置了一些副本（橙色）。

执行。 您可以通过单独考虑 P 的每个段 s 并沿着它滑动 -B 来构建灰色区域。更准确地说，您在 s 的每个端点上放置一个 -B 的副本，并找到形成灰色区域边界的 -B 的两个副本的切线：

获取每个段的解决方案并计算 P 的所有段的联合。然后从 P 中减去这个联合。看看Clipper的开源库，它可以为你做到这一点。

你得到的不仅是 B 是否适合 P 的布尔答案，而且是一组多边形形式的 B 的所有有效中心的集合。也许这对您的应用程序也很有趣。

如果你也允许 B 的旋转，那么我认为问题会变得更加复杂。也许您可以对旋转角度进行一些离散化。也许您在机器人运动规划领域找到了一些解决方案。与计算几何中的钢琴搬运工问题有关。