¿Lo quieres como una cadena o una enumeración? (sí, importa)
Philipp
O bien, ya que se usará en ambos sentidos :) Aunque si tuviera que elegir, tomaría una cuerda.
izb
1
¿Le preocupa también el rendimiento o solo la concisión?
Marcin Seredynski
2
ángulo var = Math.atan2 (y, x); return <Direction> Math.floor ((Math.round (angle / (2 * Math.PI / 8)) + 8 + 2)% 8); Yo uso este
Kikaimaru
Conciso: marcado por la brevedad de la expresión o declaración: libre de toda elaboración y detalles superfluos. Solo tirando eso por ahí ...
Dialock
Respuestas:
25
Probablemente, la forma más simple es obtener el ángulo del vector usando atan2(), como sugiere Tetrad en los comentarios, y luego escalarlo y redondearlo, por ejemplo (pseudocódigo):
// enumerated counterclockwise, starting from east = 0:enum compassDir {
E =0, NE =1,
N =2, NW =3,
W =4, SW =5,
S =6, SE =7};// for string conversion, if you can't just do e.g. dir.toString():conststring[8] headings ={"E","NE","N","NW","W","SW","S","SE"};// actual conversion code:float angle = atan2( vector.y, vector.x );int octant = round(8* angle /(2*PI)+8)%8;
compassDir dir =(compassDir) octant;// typecast to enum: 0 -> E etc.string dirStr = headings[octant];
La octant = round( 8 * angle / (2*PI) + 8 ) % 8línea podría necesitar alguna explicación. En casi todos los idiomas que conozco que lo tienen, la atan2()función devuelve el ángulo en radianes. Dividiéndolo por 2 π, se convierte de radianes a fracciones de un círculo completo, y al multiplicarlo por 8, se convierte en octavos de círculo, que luego redondeamos al número entero más cercano. Finalmente, lo reducimos en el módulo 8 para encargarnos de la envoltura, de modo que tanto 0 como 8 estén correctamente asignados al este.
La razón de esto + 8, que omití anteriormente, es que en algunos idiomas atan2()puede arrojar resultados negativos (es decir, de - π a + π en lugar de de 0 a 2 π ) y el operador de módulo ( %) puede definirse para devolver valores negativos para argumentos negativos (o su comportamiento para argumentos negativos puede ser indefinido). Agregando8 (es decir, un giro completo) a la entrada antes de la reducción asegura que los argumentos sean siempre positivos, sin afectar el resultado de ninguna otra manera.
Si su idioma no proporciona una función conveniente de redondear a la más cercana, puede usar una conversión de números enteros truncados y simplemente agregar 0.5 al argumento, así:
int octant =int(8* angle /(2*PI)+8.5)%8;// int() rounds down
Tenga en cuenta que, en algunos idiomas, la conversión flotante a entera predeterminada redondea las entradas negativas hacia arriba en lugar de hacia abajo, lo cual es otra razón para asegurarse de que la entrada siempre sea positiva.
Por supuesto, puede reemplazar todas las apariciones de 8esa línea con algún otro número (por ejemplo, 4 o 16, o incluso 6 o 12 si está en un mapa hexadecimal) para dividir el círculo en tantas direcciones. Simplemente ajuste la enumeración / matriz en consecuencia.
Tenga en cuenta que generalmente atan2(y,x)no atan2(x,y).
sam hocevar
@Sam: Vaya, corregido. Por supuesto, atan2(x,y)también funcionaría si uno simplemente enumerara los encabezados de la brújula en el sentido de las agujas del reloj comenzando desde el norte.
Ilmari Karonen
2
+1 por cierto, realmente creo que esta es la respuesta más directa y rigurosa.
sam hocevar
1
@TheLima:octant = round(8 * angle / 360 + 8) % 8
Ilmari Karonen
1
Ten en cuenta que esto puede ser fácilmente convertida en un compás de 4 vías: quadtant = round(4 * angle / (2*PI) + 4) % 4y el uso de enumeración: { E, N, W, S }.
Spoike
10
Tiene 8 opciones (o 16 o más si desea una precisión aún más fina).
Use atan2(y,x)para obtener el ángulo de su vector.
atan2() funciona de la siguiente manera:
Entonces x = 1, y = 0 dará como resultado 0, y es discontinuo en x = -1, y = 0, que contiene tanto π como -π.
Ahora solo necesitamos mapear la salida de atan2()para que coincida con la de la brújula que tenemos arriba.
Probablemente, lo más sencillo de implementar es una comprobación incremental de ángulos. Aquí hay algunos pseudocódigos que se pueden modificar fácilmente para aumentar la precisión:
//start direction from the lowest value, in this case it's west with -πenum direction {
west,
south,
east,
north
}
increment =(2PI)/direction.count
angle = atan2(y,x);
testangle =-PI + increment/2
index =0while angle > testangle
index++if(index > direction.count -1)return direction[0]//roll over
testangle += increment
return direction[index]
Ahora para agregar más precisión, simplemente agregue los valores a la dirección enum.
El algoritmo funciona verificando valores crecientes alrededor de la brújula para ver si nuestro ángulo se encuentra en algún lugar entre el último lugar donde verificamos y la nueva posición. Es por eso que comenzamos en -PI + incremento / 2. Queremos compensar nuestros controles para incluir el mismo espacio alrededor de cada dirección. Algo como esto:
West se divide en dos debido a que los valores de retorno de atan2()en West son discontinuos.
Una forma fácil de "convertirlos en un ángulo" es usar atan2, aunque tenga en cuenta que 0 grados probablemente sería este y no norte.
Tetrad
1
No necesita los angle >=cheques en el código anterior; por ejemplo, si el ángulo es menor que 45, el norte ya habrá sido devuelto, por lo que no es necesario verificar si el ángulo> = 45 para la verificación este. Del mismo modo, no necesita ningún cheque antes de regresar al oeste: es la única posibilidad que queda.
MrKWatkins
44
No llamaría a esto una forma concisa de obtener la dirección. Parece bastante torpe y requerirá muchos cambios para adaptar esto a diferentes "resoluciones". No hablar de un montón de ifdeclaraciones si quieres ir por 16 direcciones o más.
bummzack
2
No es necesario normalizar el vector: el ángulo permanece igual sobre los cambios de magnitud.
Kylotan
Gracias @bummzack, he editado la publicación para hacerlo más conciso y fácil de aumentar la precisión simplemente agregando más valores de enumeración.
MichaelHouse
8
Siempre que se trate de vectores, considere operaciones fundamentales de vectores en lugar de convertir a ángulos en algún marco en particular.
Dado un vector de consulta vy un conjunto de vectores unitarios s, el vector más alineado es el vector s_ique maximiza dot(v,s_i). Esto se debe a que el producto puntual dado longitudes fijas para los parámetros tiene un máximo para vectores con la misma dirección y un mínimo para vectores con direcciones opuestas, que cambian suavemente entre ellos.
Esto se generaliza trivialmente en más dimensiones que dos, es extensible con direcciones arbitrarias y no sufre problemas específicos de cuadros como gradientes infinitos.
En cuanto a la implementación, esto se reduciría a la asociación de un vector en cada dirección cardinal con un identificador (enumeración, cadena, lo que sea necesario) que represente esa dirección. Luego, recorrerá su conjunto de direcciones, encontrando la que tenga el producto de punto más alto.
map<float2,Direction> candidates;
candidates[float2(1,0)]= E; candidates[float2(0,1)]= N;// etc.for each (float2 dir in candidates){float goodness = dot(dir, v);if(goodness > bestResult){
bestResult = goodness;
bestDir = candidates[dir];}}
Esta implementación también se puede escribir sin ramas y vectorizada sin demasiados problemas.
Promete
1
A mapcon float2como la clave? Esto no parece muy serio.
Sam Hocevar
Es un "pseudocódigo" de manera didáctica. Si desea implementaciones optimizadas para el pánico, es probable que GDSE no sea el lugar al que ir para su copia de pasta. En cuanto a usar float2 como clave, un float puede representar exactamente los números enteros que usamos aquí, y puede hacer un comparador perfectamente bueno para ellos. Las claves de punto flotante solo no son adecuadas si contienen valores especiales o si intenta buscar resultados calculados. Iterar sobre una secuencia asociativa está bien. Podría haber usado una búsqueda lineal en una matriz, claro, pero sería un desorden inútil.
Lars Viklund
3
Una forma que no se ha mencionado aquí es tratar los vectores como números complejos. No requieren trigonometría y pueden ser bastante intuitivos para sumar, multiplicar o redondear rotaciones, especialmente porque ya tiene sus encabezados representados como pares de números.
En caso de que no esté familiarizado con ellos, las direcciones se expresan en forma de a + b (i) con un ser el componente real yb (i) es el imaginario. Si imagina que el plano cartesiano con X siendo real e Y siendo imaginario, 1 sería este (derecha), sería norte.
Aquí está la parte clave: 8 direcciones cardinales se representan exclusivamente con los números 1, -1 o 0 para sus componentes reales e imaginarios. Entonces, todo lo que tiene que hacer es reducir sus coordenadas X, Y como una razón y redondear ambas al número entero más cercano para obtener la dirección.
NW (-1+ i) N (i) NE (1+ i)
W (-1)Origin E (1)
SW (-1- i) S (-i) SE (1- i)
Para la conversión de rumbo a diagonal más cercana, reduzca X e Y proporcionalmente para que el valor mayor sea exactamente 1 o -1. Conjunto
Redondeando ambos componentes de lo que originalmente era (10, -2) le da 1 + 0 (i) o 1. Entonces, la dirección más cercana es este.
Lo anterior en realidad no requiere el uso de una estructura numérica compleja, pero pensar en ellos como tal hace que sea más rápido encontrar las 8 direcciones cardinales. Puede hacer matemática vectorial de la manera habitual si desea obtener el encabezado neto de dos o más vectores. (Como números complejos, no sumas, sino que multiplicas por el resultado)
Esto es increíble, pero comete un error similar al que cometí en mi propio intento. Las respuestas son cercanas pero no correctas. El ángulo límite entre E y NE es 22.5 grados, pero esto se corta a 26.6 grados.
izb
Max(x, y)debería ser Max(Abs(x, y))trabajar para los cuadrantes negativos. Lo intenté y obtuve el mismo resultado que izb: esto cambia las direcciones de la brújula en los ángulos incorrectos. Supongo que cambiaría cuando header.y / header.x cruza 0.5 (por lo que el valor redondeado cambia de 0 a 1), que es arctan (0.5) = 26.565 °.
amitp
Una forma diferente de usar números complejos aquí es observar que la multiplicación de números complejos implica una rotación. Si construyes un número complejo que representa 1/8 de una rotación alrededor de un círculo, entonces cada vez que lo multiplicas, te mueves un octavo. Entonces podría preguntar: ¿podemos contar cuántas multiplicaciones se necesitaron para ir del Este al rumbo actual? La respuesta a "cuántas veces tenemos que multiplicar por esto" es un logaritmo . Si busca logaritmos para números complejos ... usa atan2. Entonces esto termina siendo equivalente a la respuesta de Ilmari.
Lo más probable es que no haya una explicación detrás de su código. ¿Por qué es esta la solución y cómo funciona?
Vaillancourt
lo corriste?
Ray Tayek el
No, y dado el nombre de la clase, supuse que sí y funcionó. Y eso es genial. Pero preguntaste por qué la gente votó en contra y yo respondí; Nunca he dado a entender que no funcionó :)
Vaillancourt
-2
E = 0, NE = 1, N = 2, NW = 3, W = 4, SW = 5, S = 6, SE = 7
Por ahora, esto es solo un montón de personajes que no tienen mucho sentido; ¿Por qué es esta una solución que funcionaría para la pregunta? ¿Cómo funciona?
Vaillancourt
Escribo la fórmula como escribí jn excel y está funcionando perfectamente.
// main direction constants
DIR_E =0x1
DIR_W =0x2
DIR_S =0x4
DIR_N =0x8// mixed direction constants
DIR_NW = DIR_N | DIR_W
DIR_SW = DIR_S | DIR_W
DIR_NE = DIR_N | DIR_E
DIR_SE = DIR_S | DIR_E
// calculating the direction
dir =0x0if(x >0) dir |= DIR_E
if(x <0) dir |= DIR_W
if(y >0) dir |= DIR_S
if(y <0) dir |= DIR_N
return dir
Una ligera mejora en el rendimiento sería colocar las <comprobaciones en la rama else de las >comprobaciones correspondientes , pero me abstuve de hacerlo porque perjudica la legibilidad.
Lo siento, pero eso no dará exactamente la respuesta que estoy buscando. Con ese código solo producirá "N" si el vector está precisamente al norte, y NE o NW si x es cualquier otro valor. Lo que necesito es la dirección de la brújula más cercana, por ejemplo, si el vector está más cerca de N que de NW, entonces producirá N.
izb
¿Esto realmente daría la dirección más cercana? Parece que un vector de (0.00001,100) te daría el noreste. editar: me ganaste izb.
CiscoIPPhone
No dijiste que querías la dirección más cercana.
Philipp
1
Lo siento, lo escondí en el título. Debería haber sido más claro en el cuerpo de preguntas
izb
1
¿Qué pasa con el uso de la norma infinita? Al dividir entre max (abs (vector.components)) se obtiene un vector normalizado con respecto a esa norma. Ahora podría escribir una pequeña tabla de chequeo basada en if (x > 0.9) dir |= DIR_Etodo lo demás. Debería ser mejor que el código original de Phillipp y un poco más barato que usar la norma L2 y atan2. Tal vez o tal vez no.
Respuestas:
Probablemente, la forma más simple es obtener el ángulo del vector usando
atan2()
, como sugiere Tetrad en los comentarios, y luego escalarlo y redondearlo, por ejemplo (pseudocódigo):La
octant = round( 8 * angle / (2*PI) + 8 ) % 8
línea podría necesitar alguna explicación. En casi todos los idiomas que conozco que lo tienen, laatan2()
función devuelve el ángulo en radianes. Dividiéndolo por 2 π, se convierte de radianes a fracciones de un círculo completo, y al multiplicarlo por 8, se convierte en octavos de círculo, que luego redondeamos al número entero más cercano. Finalmente, lo reducimos en el módulo 8 para encargarnos de la envoltura, de modo que tanto 0 como 8 estén correctamente asignados al este.La razón de esto
+ 8
, que omití anteriormente, es que en algunos idiomasatan2()
puede arrojar resultados negativos (es decir, de - π a + π en lugar de de 0 a 2 π ) y el operador de módulo (%
) puede definirse para devolver valores negativos para argumentos negativos (o su comportamiento para argumentos negativos puede ser indefinido). Agregando8
(es decir, un giro completo) a la entrada antes de la reducción asegura que los argumentos sean siempre positivos, sin afectar el resultado de ninguna otra manera.Si su idioma no proporciona una función conveniente de redondear a la más cercana, puede usar una conversión de números enteros truncados y simplemente agregar 0.5 al argumento, así:
Tenga en cuenta que, en algunos idiomas, la conversión flotante a entera predeterminada redondea las entradas negativas hacia arriba en lugar de hacia abajo, lo cual es otra razón para asegurarse de que la entrada siempre sea positiva.
Por supuesto, puede reemplazar todas las apariciones de
8
esa línea con algún otro número (por ejemplo, 4 o 16, o incluso 6 o 12 si está en un mapa hexadecimal) para dividir el círculo en tantas direcciones. Simplemente ajuste la enumeración / matriz en consecuencia.fuente
atan2(y,x)
noatan2(x,y)
.atan2(x,y)
también funcionaría si uno simplemente enumerara los encabezados de la brújula en el sentido de las agujas del reloj comenzando desde el norte.octant = round(8 * angle / 360 + 8) % 8
quadtant = round(4 * angle / (2*PI) + 4) % 4
y el uso de enumeración:{ E, N, W, S }
.Tiene 8 opciones (o 16 o más si desea una precisión aún más fina).
Use
atan2(y,x)
para obtener el ángulo de su vector.atan2()
funciona de la siguiente manera:Entonces x = 1, y = 0 dará como resultado 0, y es discontinuo en x = -1, y = 0, que contiene tanto π como -π.
Ahora solo necesitamos mapear la salida de
atan2()
para que coincida con la de la brújula que tenemos arriba.Probablemente, lo más sencillo de implementar es una comprobación incremental de ángulos. Aquí hay algunos pseudocódigos que se pueden modificar fácilmente para aumentar la precisión:
Ahora para agregar más precisión, simplemente agregue los valores a la dirección enum.
El algoritmo funciona verificando valores crecientes alrededor de la brújula para ver si nuestro ángulo se encuentra en algún lugar entre el último lugar donde verificamos y la nueva posición. Es por eso que comenzamos en -PI + incremento / 2. Queremos compensar nuestros controles para incluir el mismo espacio alrededor de cada dirección. Algo como esto:
West se divide en dos debido a que los valores de retorno de
atan2()
en West son discontinuos.fuente
atan2
, aunque tenga en cuenta que 0 grados probablemente sería este y no norte.angle >=
cheques en el código anterior; por ejemplo, si el ángulo es menor que 45, el norte ya habrá sido devuelto, por lo que no es necesario verificar si el ángulo> = 45 para la verificación este. Del mismo modo, no necesita ningún cheque antes de regresar al oeste: es la única posibilidad que queda.if
declaraciones si quieres ir por 16 direcciones o más.Siempre que se trate de vectores, considere operaciones fundamentales de vectores en lugar de convertir a ángulos en algún marco en particular.
Dado un vector de consulta
v
y un conjunto de vectores unitarioss
, el vector más alineado es el vectors_i
que maximizadot(v,s_i)
. Esto se debe a que el producto puntual dado longitudes fijas para los parámetros tiene un máximo para vectores con la misma dirección y un mínimo para vectores con direcciones opuestas, que cambian suavemente entre ellos.Esto se generaliza trivialmente en más dimensiones que dos, es extensible con direcciones arbitrarias y no sufre problemas específicos de cuadros como gradientes infinitos.
En cuanto a la implementación, esto se reduciría a la asociación de un vector en cada dirección cardinal con un identificador (enumeración, cadena, lo que sea necesario) que represente esa dirección. Luego, recorrerá su conjunto de direcciones, encontrando la que tenga el producto de punto más alto.
fuente
map
confloat2
como la clave? Esto no parece muy serio.Una forma que no se ha mencionado aquí es tratar los vectores como números complejos. No requieren trigonometría y pueden ser bastante intuitivos para sumar, multiplicar o redondear rotaciones, especialmente porque ya tiene sus encabezados representados como pares de números.
En caso de que no esté familiarizado con ellos, las direcciones se expresan en forma de a + b (i) con un ser el componente real yb (i) es el imaginario. Si imagina que el plano cartesiano con X siendo real e Y siendo imaginario, 1 sería este (derecha), sería norte.
Aquí está la parte clave: 8 direcciones cardinales se representan exclusivamente con los números 1, -1 o 0 para sus componentes reales e imaginarios. Entonces, todo lo que tiene que hacer es reducir sus coordenadas X, Y como una razón y redondear ambas al número entero más cercano para obtener la dirección.
Para la conversión de rumbo a diagonal más cercana, reduzca X e Y proporcionalmente para que el valor mayor sea exactamente 1 o -1. Conjunto
Redondeando ambos componentes de lo que originalmente era (10, -2) le da 1 + 0 (i) o 1. Entonces, la dirección más cercana es este.
Lo anterior en realidad no requiere el uso de una estructura numérica compleja, pero pensar en ellos como tal hace que sea más rápido encontrar las 8 direcciones cardinales. Puede hacer matemática vectorial de la manera habitual si desea obtener el encabezado neto de dos o más vectores. (Como números complejos, no sumas, sino que multiplicas por el resultado)
fuente
Max(x, y)
debería serMax(Abs(x, y))
trabajar para los cuadrantes negativos. Lo intenté y obtuve el mismo resultado que izb: esto cambia las direcciones de la brújula en los ángulos incorrectos. Supongo que cambiaría cuando header.y / header.x cruza 0.5 (por lo que el valor redondeado cambia de 0 a 1), que es arctan (0.5) = 26.565 °.esto parece funcionar:
fuente
E = 0, NE = 1, N = 2, NW = 3, W = 4, SW = 5, S = 6, SE = 7
f (x, y) = mod ((4-2 * (1 + signo (x)) * (1 signo (y ^ 2)) - (2 + signo (x)) * signo (y)
fuente
Cuando quieres una cadena:
Esto le da constantes al utilizar campos de bits:
Una ligera mejora en el rendimiento sería colocar las
<
comprobaciones en la rama else de las>
comprobaciones correspondientes , pero me abstuve de hacerlo porque perjudica la legibilidad.fuente
if (x > 0.9) dir |= DIR_E
todo lo demás. Debería ser mejor que el código original de Phillipp y un poco más barato que usar la norma L2 y atan2. Tal vez o tal vez no.