algorithm - 带有弧线的形状的 Minkowski 和

Question

有一个问题：我想计算两个几乎凸多边形的 Minkowski 和，其中几乎凸多边形- 多边形是通过用凸多边形中 0 到 PI 弧度的弧替换一些边获得的。

我希望有 O(n + m) 解决方案，其中 n, m -几乎凸多边形中的顶点数。

对于凸形状，这个问题是微不足道的，但这个问题让我很困惑。任何人都可以帮助我提供任何建议/想法/解决方案。提前致谢！

Answer 1

首先，可视化 Minkowski 和（在此处提供帮助）。接下来，了解圆弧和弦之间的区域（这里是半硬部分）。如果你的多边形是凸的，并且弧在凸的方向，那么它只会增加 Minkowski 和的面积。具体来说，它将精确地添加由弧和弦描述的区域。当且仅当您处理凸多边形和凸方向的弧时，您可以简单地将多边形上使用的完全相同的弧替换为 Minkowski 和的相应边。请注意，闵可夫斯基和的每条边都与相关多边形之一的边完全对应。

我从 Minkowski 链接中制作了一张幻灯片的快速屏幕截图来说明我的观点。请原谅我说的不准确，但我想你会明白的。紫色区域将被添加到 Minkowski 和的区域中。

如果您将其用于运动规划或类似用途，您几乎可以轻松地将传统算法用于点包含。

编辑：我认为如果弧线在凹方向，这只是面积减法而不是加法的问题。保持简单的重要一点是其中一个多边形是凸的，并且弧替换发生在凸多边形或另一个凸包中的边上。