Minkowski求和與弧

Question

形狀有一個問題：我想計算Minkowski求和兩個幾乎凸多邊形，其中幾乎凸多邊形 - 多邊形，通過與弧更換部分邊緣與0獲得PI弧度在凸多邊形中。

我希望有O（n + m）解決方案，其中n，m - 在的幾何凸幾何凸。

對於凸形的問題是微不足道的，但這個問題困擾我。任何人都可以幫助我提供任何建議/想法/解決方案。提前致謝！

Answer 1

首先，可視化Minkowski總和（help with that here）。接下來，瞭解弧和絃之間的區域（這是半硬的部分here）。如果您的多邊形是凸面的，而弧線是凸面方向的，那麼它只會將面積添加到閔可夫斯基和。具體來說，它將完全添加弧和和絃所描述的區域。當且僅當您在凸方向上處理凸多邊形和圓弧時，您可以簡單地將您在多邊形上使用的完全相同的圓弧替換爲Minkowski和的相應邊。請注意，閔可夫斯基和的每個邊緣都完全對應於相關多邊形之一的邊緣。

我在Minkowski鏈接上製作了一張幻燈片的快速屏幕帽來說明我的觀點。原諒我說這是不準確的，但我認爲你會明白。紫色區域將被添加到閔可夫斯基和的區域。

如果您正在使用此運動計劃或類似的，你可以點遏制幾乎平凡適應傳統算法。

編輯： 我認爲如果弧線處於凹形方向，這只是區域減法而不是加法的問題。保持簡單性的重要之處在於其中一個多邊形是凸面的，並且弧形替換髮生在凸多邊形或另一個的凸包中的邊緣上。