¿Cómo puedo saber si un objeto se mueve CW o CCW alrededor de una ruta conectada?

19

Digamos que tenemos una forma irregular:

forma0

Y dos criaturas moviéndose a lo largo de su contorno.

Luego suavizamos la forma completamente tirando de las esquinas.

Obtenemos esto:

suave

Es fácil ver ahora que Orange está moviendo CW y verde CCW. ¿Cómo puedo saber en qué dirección se mueven sin suavizar la forma?

Nueva imagen

ingrese la descripción de la imagen aquí

Wolfdawn
fuente
Aquí están mis 2 centavos: i.imgur.com/zrBdw.png
Kendall Frey

Respuestas:

27

Dibuja una línea hasta el infinito y cuenta cuántas veces cruzas la forma (par o impar), sin contar el segmento donde se encuentra la criatura. Luego verifica si la criatura va a la izquierda o derecha de esa línea.

ejemplo

En este ejemplo, cruzamos la forma dos veces (de manera uniforme) y nos dirigimos hacia la izquierda. El resultado es inmediato de esta tabla:

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

En pseudocódigo:

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
fuente
¿incluye la línea de criatura en movimiento?
Ali1S232
@Gajoo: no, de ahí el> en lugar de> = en la línea 6. Agregaré una nota sobre esto. Pero tenga en cuenta que puede incluir la línea y simplemente invertir el contenido de la tabla.
sam hocevar el
1
Estaba dando vueltas entre dar una respuesta basada en este método y la respuesta que le di. Me alegra que tengamos ambos enfoques representados aquí. Este es conceptualmente más simple y muy elegante, pero requiere realizar pruebas de intersección de segmento de línea, lo que puede ser difícil de hacer robusto.
Trevor Powell el
@TrevorPowell Cierto. Encontrar el borde más alejado podría ser confuso. Primero verifiqué según el vértice más distante del borde y luego dibujé una línea desde el centro de la forma y a través de los centros de los dos bordes (los dos que comparten el vértice) y vi si una de las líneas cruza otro borde en el camino hacia infinito después de cruzar uno de estos bordes. Funcionó bien
wolfdawn
5

Depende de la información que tenga disponible de su estructura de datos de forma, pero una criatura que mueve CW a lo largo del contorno de una forma siempre tendrá el interior de la forma a su derecha, y una criatura que mueve CCW tendrá el interior de la forma en está a la izquierda.

Jeff
fuente
Una solución mucho más simple, y también mi primer pensamiento.
Amplify91
¿Cómo sabes qué dirección está dentro de la forma? Quiero decir, moverse a lo largo de un borde dentro de la forma está a la izquierda o a la derecha. ¿Cómo sabes de qué manera es?
Ali1S232
Una solución muy elegante, pero no es cierto en general. Imagine una rosquilla, aplanada sobre una mesa para hacer una forma bidimensional. Puede caminar a lo largo del borde de esta forma, mantener el interior de la forma a su izquierda y hacer una vuelta en sentido horario o antihorario dependiendo de dónde comenzó.
Marca Thomas el
4
  1. Calcule el punto central de su forma.
  2. Elija el borde más distante de su forma desde el centro.
    • (Elegir el borde más distante garantiza que no comience desde una parte cóncava invertida de la forma, lo que daría como resultado que la determinación en sentido horario / antihorario retroceda para toda la forma)
  3. Determine qué dirección a lo largo de ese borde es en sentido horario
    • (Una implementación simple de esto implicaría comparar los ángulos desde el centro de la forma hasta cada extremo del borde seleccionado. El signo de la diferencia entre los ángulos indicará su sentido horario frente a sentido antihorario)
  4. Itera sobre todos los bordes de la forma, comenzando desde el borde que elegiste en el paso 2, construyendo una lista de bordes. Para cada borde, almacene sus dos vértices en el sentido de las agujas del reloj.
    • (Si su forma no cambia con el tiempo, puede almacenar esta lista de bordes para su uso posterior, por lo que no tiene que hacer los primeros cuatro pasos en cada cuadro)
    • (es posible que ya tenga una lista de bordes. Si es así, puede almacenar este orden de vértices en el sentido de las agujas del reloj en la misma lista).
  5. Para determinar si una entidad se mueve en sentido horario o antihorario:
    • Determine en qué borde se mueve la entidad.
    • Haga un producto puntual de la dirección de movimiento de la entidad contra el vector desde los vértices de inicio-> fin en el sentido de las agujas del reloj que determinó en el paso 4.
    • Si el resultado del producto escalar es un valor mayor que cero, la entidad se mueve en el sentido de las agujas del reloj. Menos de cero significa en sentido antihorario.
Trevor Powell
fuente
Respuesta muy inteligente
wolfdawn
Tengo una pequeña pregunta? suponiendo que los vértices en su forma estén numerados comenzando desde el punto más a la izquierda CWW, en función de su respuesta, ¿cómo puedo saber si moverse de 6-> 7 o 9-> 10 (basado en cero) se mueve en sentido horario?
Ali1S232
Empiezas con el borde más distante y descubres en qué dirección está en sentido horario en ese borde. Digamos que el borde A está en sentido horario desde el vértice 'a' hasta 'b'. Entonces, si nos movemos al borde B (que tiene vértices 'b' y 'c'), sabemos que B está en sentido horario de 'b' a 'c'. Del mismo modo, el borde C va a estar en sentido horario de 'c' a 'd'. Una vez que sepamos la dirección correcta en el sentido de las agujas del reloj desde un borde (pasos 1-3), al continuar en esa dirección en el sentido de las agujas del reloj alrededor de los bordes de la forma, podemos deducir la dirección correcta en el sentido de las agujas del reloj para cada borde, sin mirar realmente dónde se encuentran sus bordes, entonces la concavidad está bien.
Trevor Powell el
¿Cómo puede saber si el borde A está en sentido horario de 'a' a 'b' o si está en sentido horario de 'b' a 'a'? Creo que te perdiste esa parte.
Ali1S232
@Gajoo Ese es el punto entre paréntesis en el paso 3. Probablemente no debería ser entre paréntesis, ya que es realmente el paso crítico de todo el proceso.
Trevor Powell el
2

Necesita saber en qué dirección se define el polígono, en qué dirección lo rodean los vértices.

Si no sabe esto, puede resolverlo calculando el área del polígono:

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

El signo del resultado (positivo o negativo) le dirá si es en sentido horario o antihorario. Debe probar esto para ver en qué dirección es para usted porque depende de su sistema de coordenadas.

Si la forma es en sentido horario:

  • Una criatura que avanza alrededor de la forma va en sentido horario , y
  • Una criatura que retrocede alrededor de la forma va en sentido antihorario .

Si la forma es en sentido antihorario:

  • Una criatura que avanza alrededor de la forma va en sentido antihorario , y
  • Una criatura que retrocede alrededor de la forma va en sentido horario .
Chris Burt-Brown
fuente
0

Parece que Trevor ya cubrió esta pregunta, pero aquí está mi solución:

  1. calcule el área que cubre su forma, lo que significa

    area = 0
    foreach (edge in shape)
        area += edge.begin.x * edge.end.y - edge.begin.y * edge.end.x
  2. usando el área calculada como se indica arriba, puede determinar fácilmente si la forma en sí es en sentido horario o no. es en sentido horario solo si el área está por debajo de cero.

  3. verifique si los objetos se mueven de la misma manera que los vértices están en orden o en la dirección opuesta.

Ali1S232
fuente
Relacionado: stackoverflow.com/questions/1165647/…
Trevor Powell el