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

Question

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

我的第一次研究使我开始“包装不规则形状”。在我看来这有点过火了。我只有一个容器和一个对象。

形状1通常是一个凸多边形。形状2可以是凸的，也可以是凹的。

我的应用:我有三维激光扫描仪测量原木，这给我的形状2。我也有不同的切割轮廓，我从其中考虑凸壳，给出形状1。

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

Answer 1

动机.如果你想问一个半径一定的磁盘B是否可以容纳一个多边形P，那么在计算几何中有一个标准的方法:检查最大内切圆是否有半径不小的情况；参见这个堆叠溢出的答案

​

​

上面计算最大内接圆的算法非常“简单”：计算所谓的广义Voronoi图，取最大间隙半径的Voronoi节点。(这只是动机，继续阅读一分钟。)

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

这些Voronoi图与计算偏移曲线密切相关，例如用于数控加工中的刀具轨迹规划.有关一些讨论和下图，请参见此博客文章：

​

​

半径r的球B符合P形，当且仅当距离r上有一条偏移曲线(实际上得到了所有有效中心的集合，即半径r处偏移曲线内的中心)。这些偏移曲线可以在数学上被描述为一个Minkowski差分，如博客文章所述。

Minkowski-difference.，所以现在我们可以回到原来的问题了。凸多边形B是否适合于多边形P？它是当且仅当Minkowski差(P)是一个非空集；(P)之外的任何中心都可以作为例子。

​

​

基于上图的更多细节:让我们用-B = {-v :v表示B}点反射后的形状。(在任何你喜欢的地方选择原点；我用“o”表示它的来源。)现在把-B看作是笔(蓝色)的形状，你沿着P的边界移动你的笔(实际上是十字)，你得到灰色区域。(这是P与-B的边界的-B。)去掉P中的灰色区域，得到Minkowski差分P-B。选择P.中的任何一点，并在那里放置一个B的副本；它将适合P。我为您放置了几份(橙色)。

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

​

​

以每段解决方案为例，计算P的所有段的联合，然后从P中减去这个联合，查看一下剪刀，它可以为您提供一个开源库。

得到的不仅是B是否符合P的布尔答案，还包括以多边形形式表示的B的所有有效中心的集合。也许这对您的应用程序来说也很有趣。

如果考虑到B的旋转，那么问题就会变得更加复杂，我想。也许你可以做一些旋转角度的离散化。也许你在机器人运动规划研究领域找到了一些解决方案。与计算几何中的钢琴搬运工问题相关。

Answer 2

附加条件:你应该有两个凸多边形(PolygonA，PolygonB)的所有顶点坐标。

Step1：将两个凸多边形的所有点放在一组中。

Step2:利用带新点集的grahamscan查找凸多边形。

Step3:，现在你有一个大凸多边形，它包含两个凸多边形。这意味着您有新创建的多边形的顶点，让我们将其命名为PolygonC。

Step4:

• 现在检查polygonC和PolygonA是否与相同的顶点集相同。
• 如果是，这意味着PolygonA包含PolygonB
• 如果上述条件不是真，则使用PolygonB重复相同的检查。 如果上述条件不适用于任意一个多边形，则没有一个多边形适合于另一个多边形。 格雷厄姆扫描