我正在寻找一种算法，可以检查一个凸多边形（形状1）是否适应另一个多边形（形状2）。
我的第一次研究引导我到“填装不规则形状”。在我看来，这有点过度了。我只有一个容器和一个物体。
形状1通常是凸多边形。形状2可以是凸多边形或凹多边形。
我的应用：我有3D激光扫描仪来测量原木，它给出了形状2。我还有不同的切割轮廓，其中我考虑凸包，得到形状1。
现在我想检查一个切割轮廓是否适合我的激光轮廓。
2个回答
7
动机。 如果您想知道一个半径为B的磁盘是否可以适应多边形P，那么在计算几何中有一种标准方法：检查最大内切圆的半径是否不小于B；参见this stackoverflow answer:
在您的情况下，您的形状2不是球; 好吧，准确地说，不是欧几里得球。但是，实际上，您的形状2作为凸多边形B，可以定义一个凸距离函数，并计算在此多面体距离函数下的沃罗诺伊图。但这更多是理论背景，可能不是您想要用于生产代码的内容。
那些沃罗诺伊图与计算偏移曲线密切相关，例如，在NC加工中进行工具路径规划。请参见此博客文章以进行一些讨论和以下图像：
Minkowski差异。 现在我们可以回到您最初的问题。凸多边形B是否适合于多边形P中？当且仅当Minkowski差异（P-B）是非空集时才适用;（P-B）之外的任何中心都可以作为示例。
使用每个部分的解决方案并计算 P 的所有部分的并集。然后从 P 中减去此并集。查看开源库Clipper，它可以为您完成这项工作。
您得到的不仅是布尔答案，即 B 是否适合 P，而且还得到了所有有效中心点的集合，形式为多边形集合。也许这对您的应用程序也很有趣。
如果还允许旋转 B，则问题就会变得更加复杂。也许您可以使用一些旋转角度的离散化。也许您可以在机器人运动规划领域或与钢琴搬运工问题相关的计算几何领域找到一些解决方案。
- S. Huber
1
非常感谢您对Minkowski求和/差异的视觉解释（我仍然不知道哪个是哪个，甚至不知道它们是否是不同的东西），但您选择的形状和非居中原点的多边形B非常有帮助。当我没有使用它们的中心作为原点时，我试图理解为什么我的两个矩形的碰撞检测代码失败了。现在我终于明白了：我没有“反射”。在我看来，您的图像将是对Minkowski求和严重缺乏视觉效果的维基百科文章的非常受欢迎的补充。谢谢！ - user1593842
2
福利：你需要拥有两个凸多边形（PolygonA和PolygonB）的所有顶点坐标。
步骤1：将两个凸多边形的所有点放在同一集合中。
步骤2：使用 Graham Scan 算法找到新点集的凸多边形。
步骤3：现在你有了一个大的凸多边形，它包含了两个凸多边形。也就是说，你已经得到了新创建的多边形（称之为 PolygonC）的顶点。
步骤4：
现在检查 PolygonC 和 PolygonA 是否具有相同的顶点点集
如果是，则表示 PolygonA 包含 PolygonB
如果上述条件不成立，请使用相同的方法检查 PolygonB。
如果任何一个多边形都无法匹配另一个多边形，则没有多边形与另一个多边形匹配。
- Rahul K Singh
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
log，方向确实很重要。 想到的：包含形状_1的（最小）圆形 cc：比较面积以衡量“紧凑度”。 类似地，找到适合于形状_2的（最大）圆形 ic - 如果遇到比cc更大的圆形，则已完成（包括方向）。 如果没有，请找到形状_1的最大直径 length （及其两侧的最大距离（总和））为一个限制措施，或者是包含形状_1的最小矩形。 相关但不是鼓舞人心的阅读：Cutting stock。 - greybeard