有一个问题：我想计算两个几乎凸多边形的Minkowski和，其中几乎凸多边形，通过用凸多边形中0到PI弧度的弧替换某些边得到。
我希望有o（n+m）解，其中n，m-几乎凸多边形中的顶点数。
对于凸形状，这个问题很简单，但这个问题让我困惑有人能帮我提些建议/主意/解决办法吗？提前谢谢！
最佳答案
首先，可视化minkowski和（help with that here）。接下来，了解弧和弦之间的区域（这是半硬部分here）。如果你的多边形是凸的，并且弧在凸的方向上，那么它只会把面积加到minkowski和上。具体来说，它将精确地添加由弧和弦描述的区域如果且仅当处理凸多边形和凸方向上的弧时，可以将多边形上使用的完全相同的弧替换为Minkowski和的相应边注意，minkowski和的每一条边正好对应于一个相关多边形的边。
我从Minkowski链接制作了一个幻灯片的快速屏幕帽来说明我的观点原谅我说的不准确，但我想你会明白的。紫色区域将添加到minkowski sum区域。
如果你用它来做运动规划或者类似的，你可以用传统的算法来进行点包容。
编辑：
我认为如果弧是凹的方向，那只是面积减法而不是加法的问题保持简单性的重要一点是其中一个多边形是凸的，并且在另一个凸多边形或凸壳中的边上发生圆弧替换。