Jak mogę stwierdzić, czy obiekt porusza się w kierunku CW lub CCW wokół połączonej ścieżki?

Powiedzmy, że mamy postrzępiony kształt:

I dwa stworzenia poruszające się po obrysie.

Następnie całkowicie wygładzamy kształt, wyciągając rogi.

Otrzymujemy to:

Teraz widać, że Orange porusza się w kierunku CW, a zielony w kierunku przeciwnym. Jak mogę określić, w którym kierunku się poruszają, bez wygładzania kształtu?

Nowy wygląd

Narysuj linię do nieskończoności i policz, ile razy przekroczysz kształt (parzysty lub nieparzysty), nie licząc segmentu, w którym leży stworzenie. Następnie sprawdź, czy stwór idzie w lewo, czy w prawo od tej linii.

W tym przykładzie przecinamy kształt dwa razy (więc nawet) i idziemy w lewo. Wynik jest natychmiastowy z tej tabeli:

   # Crosses | even  | odd
  Direction  |       |
-------------+-------+------
    left     | CCW   |  CW
    right    |  CW   | CCW

W pseudokodzie:

x, y = position of creature
vx, vy = direction of creature movement
crossings = 0
for each x1, y1, x2, y2 in shape segments:
    if (x1 < x and x <= x2) or (x2 < x and x <= x1):
        if y - y1 > (x - x1) * (y2 - y1) / (x2 - x1):
            ++crossings
if (crossings & 1) == (vx < 0):
    return CW
else
    return CCW

Zależy to od tego, jakie informacje masz dostępne ze struktury danych kształtu, ale stworzenie poruszające się CW wzdłuż konturu kształtu zawsze będzie miało wnętrze kształtu po prawej stronie, a stworzenie poruszające się w kierunku przeciwnym do ruchu będzie miało wnętrze kształtu na jego lewa strona.

1. Oblicz punkt środkowy swojego kształtu.
2. Wybierz najodleglejszą krawędź swojego kształtu od środka.
   
   • (Wybranie najbardziej odległej krawędzi gwarantuje, że nie zaczniesz od odwróconej, wklęsłej części kształtu, co spowodowałoby cofnięcie oznaczenia w prawo / w lewo dla całego kształtu)
3. Określ kierunek wzdłuż tej krawędzi zgodnie z ruchem wskazówek zegara
   • (Prosta implementacja tego wymagałaby porównania kątów od środka kształtu do każdego końca wybranej krawędzi. Znak różnicy między kątami pokaże twój ruch w prawo lub w lewo)
4. Iteruj po wszystkich krawędziach kształtu, zaczynając od krawędzi wybranej w kroku 2, tworząc listę krawędzi. Dla każdej krawędzi przechowuj jej dwa wierzchołki w kolejności zgodnej z ruchem wskazówek zegara.
   
   • (Jeśli twój kształt nie zmienia się w czasie, możesz zapisać tę listę krawędzi do późniejszego wykorzystania, więc nie musisz robić pierwszych czterech kroków w każdej klatce)
   • (być może masz już listę krawędzi. Jeśli tak, możesz zapisać tę kolejność wierzchołków zgodnie z ruchem wskazówek zegara na tej samej liście).
5. Aby ustalić, czy jednostka porusza się w prawo czy w lewo:
   • Określ, na której krawędzi porusza się jednostka.
   • Wykonaj iloczyn iloczynu kierunku ruchu bytu względem wektora od wierzchołków tej krawędzi zgodnie z ruchem wskazówek zegara -> wierzchołków, które określiłeś w kroku 4.
   • Jeśli wynik iloczynu jest wartością większą od zera, jednostka porusza się zgodnie z ruchem wskazówek zegara. Mniej niż zero oznacza przeciwnie do ruchu wskazówek zegara.

Musisz wiedzieć, w którą stronę zdefiniowany jest wielokąt, w którą stronę otaczają go wierzchołki.

Jeśli nie wiesz o tym, możesz to rozwiązać, obliczając powierzchnię wielokąta:

float Polygon::area() {
    float result = 0.0f;

    for(int a = 0; a < vertexCount; a ++) {
        int b = (a+1) % vertexCount;
        result += vertices[a].x * vertices[b].y;
        result -= vertices[a].y * vertices[b].x;
    }

    return result * .5f;
}

Znak wyniku (dodatniego lub ujemnego) powie, czy jest to prawo lub w lewo. Musisz spróbować, aby sprawdzić, która z tych opcji jest dla Ciebie, ponieważ zależy to od układu współrzędnych.

Jeśli kształt jest zgodny z ruchem wskazówek zegara:

• Stworzenie poruszające się dookoła kształtu porusza się zgodnie z ruchem wskazówek zegara i
• Stworzenie poruszające się do tyłu wokół kształtu idzie w kierunku przeciwnym do ruchu wskazówek zegara .

Jeśli kształt jest przeciwny do ruchu wskazówek zegara:

• Stworzenie poruszające się dookoła kształtu idzie w kierunku przeciwnym do ruchu wskazówek zegara , i
• Stwór poruszający się dookoła kształtu porusza się zgodnie z ruchem wskazówek zegara .

Wygląda na to, że Trevor już omówił to pytanie, ale oto moje rozwiązanie:

1. obliczyć obszar, który pokrywa twój kształt, co oznacza

   area = 0
   foreach (edge in shape)
       area += edge.begin.x * edge.end.y - edge.begin.y * edge.end.x

2. używając obszaru obliczonego jak wyżej, możesz łatwo stwierdzić, czy sam kształt jest zgodny z ruchem wskazówek zegara, czy nie. jest zgodny z ruchem wskazówek zegara tylko wtedy, gdy obszar jest poniżej zera.

3. sprawdź, czy obiekty poruszają się w taki sam sposób, jak wierzchołki są uporządkowane, czy w przeciwnym kierunku.