Odnajdywanie zorientowanego obwiedni kadłuba wypukłego w XNA przy użyciu obrotowych suwaków

Question

Być może jest to raczej pytanie matematyczne niż pytanie programistyczne, ale próbowałem wdrożyć algorytm obracających się suwaków w XNA.

Wydedukowałem wypukły kadłub z mojego zestawu punktów za pomocą monotonnego łańcucha, jak to opisano na wikipedii.

Teraz staram się modelować mój algorytm, aby znaleźć po jednym ÖBB znaleźć tutaj: http://www.cs.purdue.edu/research/technical_reports/1983/TR%2083-463.pdf

Jednak nie rozumiem, jakie metody DOTPR i CROSSPR wymienia na ostatniej stronie mają wracać.

Rozumiem, jak uzyskać produkt punktowy z dwóch punktów i produktu krzyżowego z dwóch punktów, ale wygląda na to, że te funkcje mają zwracać produkty punktowe i krzyżowe dwóch krawędzi/segmentów linii. Moja znajomość matematyki jest wprawdzie ograniczona, ale to jest mój najlepszy przypuszczenie, co algorytm szuka

public static float PolygonCross(List<Vector2> polygon, int indexA, int indexB) 
    { 
     var segmentA1 = NextVertice(indexA, polygon) - polygon[indexA]; 
     var segmentB1 = NextVertice(indexB, polygon) - polygon[indexB]; 

     float crossProduct1 = CrossProduct(segmentA1, segmentB1); 
     return crossProduct1; 
    } 

    public static float CrossProduct(Vector2 v1, Vector2 v2) 
    { 
     return (v1.X * v2.Y - v1.Y * v2.X); 
    } 

    public static float PolygonDot(List<Vector2> polygon, int indexA, int indexB) 
    { 
     var segmentA1 = NextVertice(indexA, polygon) - polygon[indexA]; 
     var segmentB1 = NextVertice(indexB, polygon) - polygon[indexB]; 

     float dotProduct = Vector2.Dot(segmentA1, segmentB1); 
     return dotProduct; 
    } 

Jednak, kiedy stosować te same metody, jak jest w tej części mojego kodu ...

  while (PolygonDot(polygon, i, j) > 0) 
      { 
       j = NextIndex(j, polygon); 
      } 

      if (i == 0) 
      { 
       k = j; 
      } 
      while (PolygonCross(polygon, i, k) > 0) 
      { 
       k = NextIndex(k, polygon); 
      } 

      if (i == 0) 
      { 
       m = k; 
      } 
      while (PolygonDot(polygon, i, m) < 0) 
      { 
       m = NextIndex(m, polygon); 
      } 

..To zwraca ten sam indeks, j, k, kiedy dać mu zestaw testowy punktów:

List<Vector2> polygon = new List<Vector2>() 
     { 
      new Vector2(0, 138), 
      new Vector2(1, 138), 
      new Vector2(150, 110), 
      new Vector2(199, 68), 
      new Vector2(204, 63), 
      new Vector2(131, 0), 
      new Vector2(129, 0), 
      new Vector2(115, 14), 
      new Vector2(0, 138), 
     }; 

uwaga, że ​​zadzwonię polygon.Reverse umieszczenie tych punktów w porządku lewo jak ind zawarty w dokumencie technicznym z perdue.edu. Mój algorytm wyszukiwania kadłuba wypukłego zbioru punktów generuje listę punktów w kolejności przeciwnej do ruchu wskazówek zegara, ale przyjmuje, że y < 0 jest wyższe niż y> 0, ponieważ podczas rysowania na ekranie 0,0 jest lewym górnym rogiem . Cofanie listy wydaje się wystarczające. Usuwam również duplikat na końcu.

Po tym procesie dane przedstawia się następująco:

• Vector2 (115, 14)
• Vector2 (129, 0)
• Vector2 (131, 0)
• Vector2 (204, 63)
• Vector2 (199, 68)
• Vector2 (150, 110)
• Vector2 (1, 138)
0.123.
• Vector2 (0, 138)

Ten test nie powiedzie się w pierwszej pętli gdy j wynosi 0 jest równy 3. Okazuje się, że przekrój produktu na linii (115,14) do (204,63) i linia (204,63) do (199,68) wynosi 0. Następnie okazuje się, że produkt kropki z tych samych linii również wynosi 0, więc j i k dzielą ten sam indeks.

W przeciwieństwie do tego, kiedy dana ten zestaw testowy: http://www.wolframalpha.com/input/?i=polygon+%282%2C1%29%2C%281%2C2%29%2C%281%2C3%29%2C%282%2C4%29%2C%284%2C4%29%2C%285%2C3%29%2C%283%2C1%29

Mój kod pomyślnie zwraca ten ÖBB: http://www.wolframalpha.com/input/?i=polygon+%282.5%2C0.5%29%2C%280.5%2C2.5%29%2C%283%2C5%29%2C%285%2C3%29

Czytałem nad algorytmem C++ znalezionego na http://www.geometrictools.com/LibMathematics/Containment/Wm5ContMinBox2.cpp ale jestem zbyt gęsta, aby podążaj za tym całkowicie.Wydaje się również, że różni się znacznie od tej opisanej w powyższym artykule.

Czy ktoś wie, jaki krok pomijam lub widzę błąd w moim kodzie do znalezienia produktu kropki i iloczynu dwóch segmentów linii? Czy ktoś pomyślnie zaimplementował ten kod wcześniej w C# i ma przykład?

Answer 1

Zakładam, że DOTPR jest normalnym produktem z kropką wektorową, crosspr jest produktem krzyżowym. dotproduct zwróci normalną liczbę, crossproduct zwróci wektor, który jest prostopadły do ​​podanych dwóch wektorów. (podstawowa matematyka wektorowa, sprawdź wikipedia)

są one faktycznie zdefiniowane w artykule jako DOTPR (i, j) zwraca iloczyn wektorów od wierzchołków i do i + 1 i j do j + 1. to samo dla CROSSPR, ale z produktem krzyżowym.

Answer 2

Punkty i wektory jako struktury danych to w zasadzie to samo; oba składają się z dwóch elementów pływających (lub trzech, jeśli pracujesz w trzech wymiarach). Tak więc, gdy poproszony o pobranie kropek z krawędzi, przypuszczam, że oznacza to pobranie iloczynu kropek wektorów, które definiują krawędzie. Podany kod działa dokładnie tak.

Twoja implementacja CrossProduct wydaje się być poprawna (patrz Wolfram MathWorld). Jednak w PolygonCross i PolygonDot myślę, że nie powinieneś normalizować segmentów. Wpłynie to na wielkość zwracanych wartości PolygonDot i i PolygonCross. Usuwając zbędne połączenia z numerem Vector2.Normalize można przyspieszyć kod i zmniejszyć ilość szumu w wartościach zmiennoprzecinkowych. Jednak normalizacja nie ma wpływu na poprawność wklejanego kodu, ponieważ porównuje wyniki tylko z zerem.

Należy zauważyć, że papier, do którego się powołujesz, zakłada, że ​​wierzchołki wielokątów są wymienione w kolejności przeciwnej do ruchu wskazówek zegara (strona 5, pierwszy akapit po "Początek komentarzy"), ale twój przykład polygon jest zdefiniowany zgodnie z ruchem wskazówek zegara. Dlatego PolygonCross(polygon, 0, 1) jest ujemny i otrzymujesz tę samą wartość dla j i k.