获取通过移动多边形创建的多边形

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 

计算多边形工会是一个很好研究的问题与高效的算法。