Wie kann ich feststellen, ob sich ein Objekt im Uhrzeigersinn oder im Gegenuhrzeigersinn auf einem verbundenen Pfad bewegt?

19

Nehmen wir an, wir haben eine gezackte Form:

shape0

Und zwei Kreaturen, die sich entlang der Umrisse bewegen.

Dann glätten wir die Form vollständig, indem wir die Ecken herausziehen.

Wir bekommen das:

glatt

Es ist jetzt leicht zu erkennen, dass sich Orange im Uhrzeigersinn und im grünen Uhrzeigersinn bewegt. Wie kann ich feststellen, in welche Richtung sie sich bewegen, ohne die Form zu glätten?

Neues Bild

Bildbeschreibung hier eingeben

wolfdawn
quelle
Hier sind meine 2 Cent: i.imgur.com/zrBdw.png
Kendall Frey

Antworten:

27

Zeichne eine Linie bis ins Unendliche und zähle, wie oft du die Form überquerst (gerade oder ungerade), ohne das Segment zu zählen, in dem die Kreatur liegt. Dann überprüfe, ob die Kreatur sich links oder rechts von dieser Linie befindet.

Beispiel

In diesem Beispiel überqueren wir die Form zweimal (also gerade) und gehen nach links. Das Ergebnis ergibt sich unmittelbar aus dieser Tabelle:

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

Im Pseudocode:

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
sam hocevar
quelle
schließen Sie die Linie Kreatur ein, die weitergeht?
Ali1S232
@ Gajoo: nein, daher das> statt> = in Zeile 6. Ich werde einen Hinweis dazu hinzufügen. Beachten Sie jedoch, dass Sie die Zeile einfügen und den Tabelleninhalt einfach umkehren können.
Sam Hocevar
1
Ich warf die Frage zwischen einer auf dieser Methode basierenden Antwort und der Antwort, die ich gab, auf. Ich bin froh, dass wir beide Ansätze hier vertreten haben. Dieser ist konzeptionell einfacher und sehr elegant, erfordert jedoch die Durchführung von Schnittpunkttests für Liniensegmente, deren Robustheit schwierig sein kann.
Trevor Powell
@ TrevorPowell True. Das Finden der äußersten Kante kann verwirrend sein. Ich habe zuerst anhand des entferntesten Scheitelpunkts der Kante überprüft und dann eine Linie vom Mittelpunkt der Form und durch die beiden Scheitelpunktzentren (die beiden, die sich den Scheitelpunkt teilen) gezogen und festgestellt, ob eine der Linien auf dem Weg zu eine andere Kante kreuzt Unendlich nach dem Überqueren einer dieser Kanten. Es hat gut
geklappt
5

Dies hängt davon ab, über welche Informationen Sie in Ihrer Formdatenstruktur verfügen. Bei einer Kreatur, die sich im Uhrzeigersinn entlang der Kontur einer Form bewegt, befindet sich das Innere der Form jedoch immer rechts und bei einer Kreatur, die sich im Uhrzeigersinn bewegt, befindet sich das Innere der Form es ist links.

Jeff
quelle
Eine viel einfachere Lösung und auch mein erster Gedanke.
Amplify91
Woher weißt du, in welche Richtung sich die Form befindet? Ich meine, sich entlang einer Kante innerhalb der Form zu bewegen, ist entweder zu Ihrer Linken oder zu Ihrer Rechten. Woher weißt du, wie es ist?
Ali1S232,
Eine sehr elegante Lösung, aber im Allgemeinen nicht wahr. Stellen Sie sich einen Donut vor, der auf einem Tisch abgeflacht ist, um eine zweidimensionale Form zu erhalten. Sie können entlang der Kante dieser Form gehen, die Innenseite der Form auf der linken Seite belassen und je nachdem, wo Sie begonnen haben, eine Runde im oder gegen den Uhrzeigersinn fahren.
Marcks Thomas
4
  1. Berechnen Sie den Mittelpunkt Ihrer Form.
  2. Wählen Sie die am weitesten entfernte Kante Ihrer Form aus der Mitte.
    • (Wenn Sie die am weitesten entfernte Kante auswählen, wird sichergestellt, dass Sie nicht von einem umgekehrten, konkaven Teil der Form ausgehen. Dies würde dazu führen, dass die Bestimmung im Uhrzeigersinn / gegen den Uhrzeigersinn für die gesamte Form rückwärts erfolgt.)
  3. Bestimmen Sie, welche Richtung entlang dieser Kante im Uhrzeigersinn ist
    • (Bei einer einfachen Implementierung werden die Winkel von der Mitte der Form zu jedem Ende der ausgewählten Kante verglichen. Das Vorzeichen für den Unterschied zwischen den Winkeln zeigt an, ob Sie im Uhrzeigersinn oder gegen den Uhrzeigersinn arbeiten.)
  4. Durchlaufen Sie alle Kanten der Form. Beginnen Sie dabei mit der Kante, die Sie in Schritt 2 ausgewählt haben, und erstellen Sie eine Kantenliste. Speichern Sie für jede Kante die beiden Scheitelpunkte im Uhrzeigersinn.
    • (Wenn sich Ihre Form im Laufe der Zeit nicht ändert, können Sie diese Kantenliste für die spätere Verwendung speichern, sodass Sie nicht die ersten vier Schritte pro Frame ausführen müssen.)
    • (Möglicherweise haben Sie bereits eine Kantenliste. In diesem Fall können Sie diese Scheitelpunktreihenfolge im Uhrzeigersinn in derselben Liste speichern.)
  5. So bestimmen Sie, ob sich eine Entität im oder gegen den Uhrzeigersinn bewegt:
    • Bestimmen Sie, entlang welcher Kante sich das Objekt bewegt.
    • Erstellen Sie ein Skalarprodukt der Bewegungsrichtung des Objekts gegen den Vektor von den Anfangs-> Endscheitelpunkten dieser Kante im Uhrzeigersinn, die Sie zuvor in Schritt 4 bestimmt haben.
    • Wenn das Ergebnis des Skalarprodukts ein Wert größer als Null ist, bewegt sich das Objekt im Uhrzeigersinn. Weniger als Null bedeutet gegen den Uhrzeigersinn.
Trevor Powell
quelle
Sehr clevere Antwort
Wolfdawn
Ich habe eine kleine Frage? Angenommen, die Eckpunkte in seiner Form werden beginnend mit dem linken Punkt im Uhrzeigersinn nummeriert. Anhand Ihrer Antwort kann ich erkennen, ob sich eine Bewegung von 6-> 7 oder 9-> 10 (nullbasiert) im Uhrzeigersinn bewegt.
Ali1S232
Sie beginnen mit der am weitesten entfernten Kante und stellen fest, in welcher Richtung sich diese Kante im Uhrzeigersinn befindet. Nehmen wir an, dass die Kante A vom Scheitelpunkt 'a' bis 'b' im Uhrzeigersinn verläuft. Wenn wir uns dann zu Kante B bewegen (die die Eckpunkte 'b' und 'c' hat), wissen wir, dass B von 'b' nach 'c' im Uhrzeigersinn ist. In ähnlicher Weise wird die Kante C von "c" nach "d" im Uhrzeigersinn sein. Sobald wir die richtige Richtung im Uhrzeigersinn von einer Kante aus kennen (Schritte 1-3), können wir durch Fortsetzung dieser Richtung im Uhrzeigersinn um die Kanten der Form die richtige Richtung im Uhrzeigersinn für jede Kante ableiten, ohne tatsächlich zu sehen, wo sich die Kanten befinden. so Konkavität ist in Ordnung.
Trevor Powell
Wie können Sie feststellen, ob Kante A im Uhrzeigersinn von 'a' nach 'b' oder im Uhrzeigersinn von 'b' nach 'a' ist? Ich denke, Sie haben diesen Teil verpasst.
Ali1S232
@ Gajoo Das ist der Klammerpunkt in Schritt 3. Sollte wahrscheinlich kein Klammerpunkt sein, da dies wirklich der kritische Schritt des gesamten Prozesses ist.
Trevor Powell
2

Sie müssen wissen, in welche Richtung das Polygon definiert ist und in welche Richtung die Eckpunkte es umgeben.

Wenn Sie das nicht wissen, können Sie es durch Berechnen der Fläche des Polygons herausfinden:

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;
}

Das Vorzeichen des Ergebnisses (positiv oder negativ) zeigt an, ob es im Uhrzeigersinn oder gegen den Uhrzeigersinn ist. Sie müssen dies versuchen, um herauszufinden, wie es für Sie ist, da es von Ihrem Koordinatensystem abhängt.

Wenn die Form im Uhrzeigersinn ist:

  • Eine Kreatur, die vorwärts geht bewegt, bewegt sich im Uhrzeigersinn und
  • Eine Kreatur, die sich rückwärts um die Form dreht, geht bewegt gegen Uhrzeigersinn .

Wenn die Form gegen den Uhrzeigersinn ist:

  • Eine Kreatur, die vorwärts um die Gestalt geht, geht bewegt , bewegt gegen Uhrzeigersinn und
  • Eine Kreatur, die sich rückwärts um die Form dreht, bewegt sich im Uhrzeigersinn .
Chris Burt-Brown
quelle
0

Es scheint, dass Trevor diese Frage bereits behandelt hat, aber hier ist meine Lösung:

  1. Berechnen Sie den Bereich, den Ihre Form abdeckt

    area = 0
    foreach (edge in shape)
        area += edge.begin.x * edge.end.y - edge.begin.y * edge.end.x
  2. Wenn Sie die wie oben berechnete Fläche verwenden, können Sie leicht feststellen, ob die Form selbst im Uhrzeigersinn ist oder nicht. Es ist nur im Uhrzeigersinn, wenn der Bereich unter Null liegt.

  3. Überprüfen Sie, ob sich die Objekte auf die gleiche Weise wie die Scheitelpunkte in der Reihenfolge oder in der entgegengesetzten Richtung bewegen.

Ali1S232
quelle