¿Cómo identifico en qué región cae un punto generado aleatoriamente en un mapa?Ya publiqué esta pregunta en stackoverflow pero se señaló a la comunidad ya que es más probable que obtenga una respuesta. También hay una representación gráfica de lo que implica mi problema.
Básicamente, tengo un "mapa" que consta de varias regiones rectangulares. Tengo acceso a las coordenadas de todos los vértices de cada región rectangular (sus x_min, x_max, y_min, y_max).
Genero al azar un punto que se encuentra en cualquier lugar de ese mapa. Conozco las coordenadas de ese punto (xey). El problema que quiero resolver es averiguar en qué región se encuentra el punto.
lo que he hecho es simplemente pasar por una declaración de condición grande verificando una por una si la coordenada x e y del punto está entre x_min y x_max e y_min e y_max de cada región. Sin embargo, siento que tiene que haber una forma más escalable, generalizable y eficiente de hacer esto, pero no puedo encontrar una manera de hacerlo, al menos no algo que no esté en una biblioteca para un lenguaje de programación diferente. Pensé en tal vez hacer algo donde dividir el mapa por la mitad, averiguar en qué mitad se encuentra el punto, contar todas las regiones en esa mitad, verificar si queda una región y, si no es así, dividir el mapa por la mitad nuevamente y repita el proceso de nuevo. Simplemente no tengo una buena idea de cómo se puede implementar y si eso es factible o mejor que el método actual que tengo.
ScriptingVentanasRe: ¿Cómo identifico en qué región cae un punto generado aleatoriamente en un mapa?Si estuviera inventando un algoritmo para las regiones rectangulares en mosaico, usaría la función KDTable y cargaría todos los puntos de las esquinas en la tabla. Algo como esto:
one to four rectangles share each cornerde uno a cuatro rectángulos comparten cada esquina
KDTable le dirá de manera eficiente qué esquina está más cercana a cualquier ubicación xy consultada. Si mantiene otra tabla de todos los rectángulos que comparten ese punto, solo necesita marcar hasta cuatro. Dependiendo de cómo ordene los datos, el simple hecho de saber
KDTable está haciendo prácticamente lo que describió, en dimensiones K. para datos xy, K == 2.
Re: ¿Cómo identifico en qué región cae un punto generado aleatoriamente en un mapa?O quizás sea más difícil.
This will find the wrong corner.Esto encontrará la esquina equivocada.
Re: ¿Cómo identifico en qué región cae un punto generado aleatoriamente en un mapa?¿Cuánta resolución necesitas? Si un mapa de bits de 10K por 10K sería lo suficientemente bueno y hay menos de 16E6 polígonos, puede dibujar los rectángulos en el mapa de bits con colores únicos (2 ^ 24 colores son 16 millones de colores) y consultar un píxel xy redondeado al instante. Hice algo así en JSL BLOB en un reloj ESP32 para búsquedas de GPS en un mapa de zona horaria. En mi caso, tomé la resolución que pude obtener, que estaba a una milla o dos cerca de un límite de zona horaria; No necesitaba tanto la velocidad como poder codificar el mapa de bits para que quepa en una computadora pequeña.
editar: aparentemente hice un mapa de bits así de grande
composition = J( 16000, 30000, 0 );
que se quedó sin memoria o excedió el límite de píxeles si crecía ... Usé 16000 para la latitud de +/- 90 grados y 30K (no 32K) para la longitud de +/- 180 grados. Eso es más de un GB sin comprimir. Necesitaría un archivo PNG, NO un JPG. JPG no conservaría los colores.
