Différence de Minkowski avec des polygones concaves

Question

En essayant de calculer la différence de Minkowski de deux polygones convexes, je peux simplement trouver l'ensemble des sommets et utiliser un algorithme d'emballage de cadeaux pour trouver la coque convexe. (

Cependant, pour les polygones concaves, l'algorithme de coque convexe n'est pas approprié car il me donnera un faux positif sur les collisions, est-il possible d'adapter mon code pour trouver facilement la bonne expansion en utilisant les points déjà généré?

---

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

La méthode habituelle consiste à décomposer le polygone concave en morceaux convexes, et itérer par paires entre les pièces de chaque polygone convexe à la recherche d'une collision. Si l'un des polygones est trop grand pour le faire naïvement (composé de centaines de peignes convexes), vous pouvez ajouter chaque pièce à une phase large.

Notez que si vous faites quelque chose comme GJK, vous ne construisez pas explicitement la différence Minkowski comme un polygone. Au contraire, vous le contournez implicitement en y trouvant des sommets de «soutien» qui sont les plus éloignés d'une direction donnée. Parce que la différence de Minkowski est séparable linéairement, vous pouvez le faire pour chaque polygone séparément, puis trouver leur différence.

L'idée peut être un peu difficile à grok, mais voir par exemple: http://www.dyn4j.org/2010/04/gjk-distance-closest-points/