Comment savoir si un objet se déplace CW ou CCW autour d'un chemin connecté?

19

Disons que nous avons une forme dentelée:

forme0

Et deux créatures se déplaçant le long de son contour.

Ensuite, nous lissons complètement la forme en tirant sur les coins.

Nous obtenons ceci:

lisse

Il est facile de voir maintenant qu'Orange déplace la CW et la CCW verte. Comment savoir dans quelle direction ils se déplacent sans lisser la forme?

Nouvelle image

entrez la description de l'image ici

Wolfdawn
la source
Voici mes 2 cents: i.imgur.com/zrBdw.png
Kendall Frey

Réponses:

27

Tracez une ligne à l'infini et comptez combien de fois vous traversez la forme (paire ou impaire), sans compter le segment où se trouve la créature. Vérifiez ensuite si la créature va à gauche ou à droite de cette ligne.

exemple

Dans cet exemple, nous traversons la forme deux fois (donc même) et nous allons vers la gauche. Le résultat est immédiat de ce tableau:

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

En 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
la source
incluez-vous la créature en ligne qui se déplace?
Ali1S232
@Gajoo: non, d'où le> au lieu de> = à la ligne 6. Je vais ajouter une note à ce sujet. Mais notez que vous pouvez inclure la ligne et inverser le contenu du tableau.
sam hocevar
1
Je me disputais entre donner une réponse basée sur cette méthode et la réponse que j'ai donnée. Je suis heureux que les deux approches soient représentées ici. Celui-ci est conceptuellement plus simple et très élégant, mais nécessite d'effectuer des tests d'intersection de segments de ligne, ce qui peut être difficile à rendre robuste.
Trevor Powell
@TrevorPowell True. Trouver le bord le plus éloigné pourrait être déroutant. J'ai d'abord vérifié en fonction du sommet le plus éloigné du bord, puis en traçant une ligne à partir du centre de la forme et à travers les centres des deux bords (les deux qui partagent le sommet) et en voyant si l'une des lignes croise un autre bord sur le chemin de l'infini après avoir traversé l'un de ces bords. Ça a bien marché
wolfdawn
5

Cela dépend des informations dont vous disposez dans votre structure de données de forme, mais une créature se déplaçant en CW le long du contour d'une forme aura toujours l'intérieur de la forme à sa droite, et une créature en mouvement CCW aura l'intérieur de la forme sur sa gauche.

Jeff
la source
Une solution beaucoup plus simple, et aussi ma première pensée.
Amplify91
comment savez-vous quelle direction est à l'intérieur de la forme? Je veux dire que se déplacer le long d'un bord à l'intérieur de la forme est à votre gauche ou à votre droite. comment savez-vous de quelle façon c'est?
Ali1S232
Une solution très élégante, mais pas vraie en général. Imaginez un beignet, aplati sur une table pour créer une forme en deux dimensions. Vous pouvez marcher le long du bord de cette forme, garder l'intérieur de la forme sur votre gauche et faire un tour dans le sens horaire ou antihoraire selon l'endroit où vous avez commencé.
Marcks Thomas
4
  1. Calculez le point central de votre forme.
  2. Choisissez le bord le plus éloigné de votre forme depuis le centre.
    • (La sélection du bord le plus éloigné garantit que vous ne commencez pas à partir d'une partie inversée et concave de la forme, ce qui entraînerait une rétrogradation dans le sens horaire / antihoraire pour toute la forme)
  3. Déterminez la direction le long de ce bord dans le sens horaire
    • (Une implémentation simple de cela impliquerait de comparer les angles du centre de la forme à chaque extrémité du bord sélectionné. Le signe de la différence entre les angles dira votre sens horaire par rapport à anti-horaire)
  4. Itérer sur tous les bords de la forme, en commençant par le bord choisi à l'étape 2, en créant une liste d'arêtes. Pour chaque arête, stockez ses deux sommets dans le sens des aiguilles d'une montre.
    • (Si votre forme ne change pas au fil du temps, vous pouvez stocker cette liste de bords pour une utilisation ultérieure, vous n'avez donc pas à effectuer les quatre premières étapes à chaque image)
    • (vous avez peut-être déjà une liste d'arêtes. Si c'est le cas, vous pouvez stocker cet ordre de sommet dans le sens horaire dans cette même liste.)
  5. Pour déterminer si une entité se déplace dans le sens horaire ou antihoraire:
    • Déterminez le bord sur lequel l'entité se déplace.
    • Faites un produit scalaire de la direction du mouvement de l'entité contre le vecteur à partir des sommets de début et de fin de cette arête que vous avez déterminés à l'étape 4.
    • Si le résultat du produit scalaire est une valeur supérieure à zéro, l'entité se déplace dans le sens horaire. Moins de zéro signifie dans le sens inverse des aiguilles d'une montre.
Trevor Powell
la source
Réponse très intelligente
wolfdawn
J'ai une petite question? en supposant que les sommets de sa forme sont numérotés à partir du point CWW le plus à gauche, en fonction de votre réponse, comment puis-je savoir si le déplacement de 6-> 7 ou 9-> 10 (basé sur zéro) se déplace dans le sens horaire?
Ali1S232
Vous commencez par le bord le plus éloigné et déterminez dans quel sens se trouve le sens horaire sur ce bord. Disons que l'arête A est dans le sens horaire du sommet «a» à «b». Ensuite, si nous passons au bord B (qui a les sommets «b» et «c»), nous savons que B est dans le sens horaire de «b» à «c». De même, l'arête C va être dans le sens horaire de «c» à «d». Une fois que nous connaissons la bonne direction dans le sens des aiguilles d'une montre à partir d'un bord (étapes 1 à 3), en continuant dans cette direction dans le sens des aiguilles d'une montre autour des bords de la forme, nous pouvons déduire la bonne direction dans le sens des aiguilles d'une montre pour chaque bord, sans vraiment regarder où se trouvent ses bords, donc la concavité est ok.
Trevor Powell
comment savoir si le bord A est dans le sens horaire de 'a' à 'b' ou s'il est dans le sens horaire de 'b' à 'a'? Je pense que vous avez manqué cette partie.
Ali1S232
@Gajoo C'est le point entre parenthèses à l'étape 3. Ne devrait probablement pas être entre parenthèses, car c'est vraiment l'étape critique de tout le processus.
Trevor Powell
2

Vous devez savoir dans quel sens le polygone est défini, dans quel sens les sommets le contournent.

Si vous ne le savez pas, vous pouvez le calculer en calculant l'aire du polygone:

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

Le signe du résultat (positif ou négatif) vous dira s'il est dans le sens horaire ou antihoraire. Vous devez essayer ceci pour voir de quel côté il s'agit pour vous car cela dépend de votre système de coordonnées.

Si la forme est dans le sens horaire:

  • Une créature qui avance autour de la forme va dans le sens horaire , et
  • Une créature qui recule autour de la forme va dans le sens inverse des aiguilles d'une montre .

Si la forme est dans le sens inverse des aiguilles d'une montre:

  • Une créature qui avance autour de la forme va dans le sens inverse des aiguilles d'une montre , et
  • Une créature qui recule autour de la forme va dans le sens des aiguilles d'une montre .
Chris Burt-Brown
la source
0

Il semble que Trevor ait déjà couvert cette question, mais voici ma solution:

  1. calculer la zone couverte par votre forme, ce qui signifie

    area = 0
    foreach (edge in shape)
        area += edge.begin.x * edge.end.y - edge.begin.y * edge.end.x
  2. en utilisant la zone calculée comme ci-dessus, vous pouvez facilement dire si la forme elle-même est dans le sens horaire ou non. il n'est dans le sens des aiguilles d'une montre que si la zone est inférieure à zéro.

  3. vérifiez si les objets se déplacent de la même manière que les sommets sont dans l'ordre ou dans la direction opposée.

Ali1S232
la source