獲取通過移動多邊形創建的多邊形

Question

我不知道該進程是否具有特定名稱。我想獲得通過平移多邊形創建的多邊形。有沒有一個算法。例如： 。

凸外殼適用於凸多邊形，但我想要一個通用的解決方案。另外我會很高興聽到是否有辦法獲取通過旋轉創建的多邊形。

Answer 1

看來您正在尋找多邊形的Minkowski sum以及描述您的運動的線段。

CGAL library包2D Minkowski Sums可以計算它們。

Answer 2

給你的意見給瞭解釋，直接的方法是這樣的：

Let v be a vector describing the linear movement 
For each edge (p,q) in the polygon 
    construct quadrilateral (p, q, q+v, p+v) 
Compute the union of all the quadrilaterals plus the original polygon 

計算多邊形工會是一個很好研究的問題與高效的算法。