凹多边形的 Minkowski 差异

Question

当尝试计算两个凸多边形的 Minkowski 差异时，我可以简单地找到顶点集并使用礼品包装算法找到凸包。（见下文。）

然而，对于凹多边形，凸包算法不合适，因为它会给我一个误报，有没有一种方法可以调整我的代码，使用已经生成的点轻松找到正确的扩展？

public List<Vector2D> MinkowskiDifference(Polygon other)
{
   List<Vector2D> vList = new List<Vector2D>();

   foreach (Vector2D vT in this.vertices)
   {
        foreach (Vector2D vO in other.vertices)
        {
            vList.Add((vT+this.position) - (vO+other.position));
        }
   }
   return vList;
}

public static Polygon ConvexHull(List<Vector2D> vList)
{
    List<Vector2D> S = vList;
    List<Vector2D> P = new List<Vector2D>();
    Vector2D endpoint;

    Vector2D pointOnHull = LeftMostPoint(S);
    int i = 0;
    do
    {
        P.Add(pointOnHull);
        endpoint = S[0];
        for (int j = 1; j < S.Count; j++)
        {
            if (endpoint == pointOnHull || RelPosition(P[i], endpoint, S[j]) == -1)
            {
                    endpoint = S[j];
            }
        }
        i++;
        pointOnHull = endpoint;
    } while (endpoint != P[0]);
    return new Polygon(P);
}

Answer 1

通常的方法是将凹多边形分解成凸块，并在每个多边形的凸块之间成对迭代寻找碰撞。如果其中一个多边形太大而无法简单地执行此操作（由 100 个凸面组成），您可以将每个面添加到一个宽相中。

请注意，如果您正在执行类似 GJK 的操作，则不会将 Minkowski 差异显式构造为多边形。相反，您通过在其上找到沿给定方向最远的 "support" 个顶点来隐含地绕过它。因为 Minkowski 差异是线性可分的，所以您可以单独对每个多边形执行此操作，然后找到它们的差异。

这个想法可能有点难以理解，但请参阅示例：http://www.dyn4j.org/2010/04/gjk-distance-closest-points/

凹多边形的 Minkowski 差异

Minkowski difference with concave polygons

c#

collision-detection

computational-geometry