Dibujando un Mapa Topográfico

Question

He estado trabajando en un proyecto de visualización para datos continuos bidimensionales. Es el tipo de cosa que podría usar para estudiar datos de elevación o patrones de temperatura en un mapa 2D. En esencia, es realmente una forma de aplanar 3 dimensiones en dos dimensiones más color. En mi campo particular de estudio, en realidad no estoy trabajando con datos de elevación geográfica, pero es una buena metáfora, por lo que me quedaré con ella a lo largo de esta publicación.

De todos modos, en este punto, tengo un "color continuo" procesador con el que estoy muy satisfecho:

El degradado es la rueda de colores estándar, donde los píxeles rojos indican coordenadas con valores altos y los píxeles violetas indican valores bajos.

La estructura de datos subyacente utiliza algunos algoritmos de interpolación muy inteligentes (si lo digo yo mismo) para permitir un zoom profundo arbitrario en los detalles del mapa.

En este punto, quiero dibujar algunas líneas de contorno topográficas (usando curvas de Bezier cuadráticas), pero no he podido encontrar ninguna buena literatura que describa algoritmos eficientes para encontrar esas curvas.

Para darle una idea de lo que estoy pensando, aquí está la implementación de un hombre pobre (donde el renderizador solo usa un valor RGB negro cada vez que encuentra un píxel que interseca una línea de contorno):

Sin embargo, hay varios problemas con este enfoque:

• Las áreas del gráfico con una pendiente más pronunciada dan como resultado líneas topográficas más delgadas (y a menudo rotas). Idealmente, todas las líneas topográficas deben ser continuas.

• Las áreas del gráfico con una pendiente más plana dan como resultado líneas topo más anchas (y a menudo regiones enteras de negrura, especialmente en el perímetro exterior de la región de representación).

Así que estoy viendo un enfoque de dibujo vectorial para obtener esas curvas bonitas y perfectas de 1 píxel de grosor. La estructura básica del algoritmo deberá incluir estos pasos:

1. En cada elevación discreta donde quiero dibujar una línea topográfica, encuentre un conjunto de coordenadas donde la elevación en esa coordenada sea extremadamente cercana (dado un valor épsilon arbitrario) a la elevación deseada.

2. Eliminar puntos redundantes. Por ejemplo, si tres puntos están en una línea perfectamente recta, entonces el punto central es redundante, ya que puede eliminarse sin cambiar la forma de la curva. Del mismo modo, con curvas bezier, a menudo es posible eliminar los puntos de anclaje al ajustar la posición de los puntos de control adyacentes.

3. Ensamble los puntos restantes en una secuencia, de modo que cada segmento entre dos puntos se aproxime a una trayectoria de elevación neutral, y de modo que no haya dos segmentos de línea que se crucen nunca. Cada secuencia de puntos debe crear un polígono cerrado o debe intersecar el cuadro delimitador de la región de representación.

4. Para cada vértice, encuentre un par de puntos de control de manera que la curva resultante muestre un error mínimo, con respecto a los puntos redundantes eliminados en el paso # 2.

5. Asegúrese de que todas las características de la topografía visibles en la escala de representación actual estén representadas por líneas topográficas apropiadas. Por ejemplo, si los datos contienen una espiga con gran altitud, pero con un diámetro extremadamente pequeño, las líneas topográficas aún deben dibujarse. Las características verticales solo deben ignorarse si el diámetro de su característica es menor que la granularidad de representación general de la imagen.

Pero incluso bajo esas restricciones, todavía puedo pensar en varias heurísticas diferentes para encontrar las líneas:

• Encuentre el punto alto dentro del cuadro delimitador de representación. Desde ese punto alto, viaje cuesta abajo a lo largo de varias trayectorias diferentes. Cada vez que la línea transversal cruce un umbral de elevación, agregue ese punto a un depósito específico de elevación. Cuando el camino transversal alcanza un mínimo local, cambie el rumbo y viaje cuesta arriba.

• Realice un recorrido de alta resolución a lo largo del cuadro delimitador rectangular de la región de representación. En cada umbral de elevación (y en los puntos de inflexión, donde la pendiente invierta la dirección), agregue esos puntos a un cubo específico de elevación. Después de terminar el recorrido del límite, comience a trazar hacia adentro desde los puntos del límite en esos cubos.

• Escanee toda la región de representación, tomando una medición de elevación en un intervalo regular disperso. Para cada medición, use su proximidad a un umbral de elevación como mecanismo para decidir si tomar o no una medición interpolada de sus vecinos. El uso de esta técnica proporcionaría mejores garantías de cobertura en toda la región de representación, pero sería difícil reunir los puntos resultantes en un orden sensible para construir rutas.

Entonces, esos son algunos de mis pensamientos ...

Antes de sumergirme profundamente en una implementación, quería ver si alguien más en StackOverflow tiene experiencia con este tipo de problema y podría proporcionar indicadores para una implementación precisa y eficiente.

Edición :

Estoy especialmente interesado en el "Gradiente" sugerencia hecha por ellisbben. Y mi estructura de datos central (ignorando algunos de los atajos de optimización de interpolación) puede representarse como la suma de un conjunto de funciones gaussianas 2D, que es totalmente diferenciable.

Supongo que necesitaré una estructura de datos para representar una pendiente tridimensional, y una función para calcular ese vector de pendiente en un punto arbitrario. Fuera de mi cabeza, no sé cómo hacerlo (aunque parece que debería ser fácil), pero si tienes un enlace que explique las matemáticas, ¡estaría muy agradecido!

UPDATE:

Gracias a las excelentes contribuciones de ellisbben y Azim, ahora puedo calcular el ángulo de contorno para cualquier punto arbitrario en el campo. ¡Dibujará las líneas topo reales en breve!

Aquí hay representaciones actualizadas, con y sin el renderizador topográfico basado en ráster de ghetto que he estado usando. Cada imagen incluye mil puntos de muestra aleatorios, representados por puntos rojos. El ángulo de contorno en ese punto está representado por una línea blanca. En ciertos casos, no se puede medir la pendiente en el punto dado (en función de la granularidad de la interpolación), por lo que el punto rojo se produce sin una línea de ángulo de contorno correspondiente.

¡Disfruta!

(NOTA: Estas representaciones usan una topografía de superficie diferente a las representaciones anteriores, ya que genero aleatoriamente las estructuras de datos en cada iteración, mientras estoy creando prototipos, pero el método de representación central es el mismo, así que Estoy seguro de que tienes la idea.)

??

??

Aquí hay un hecho divertido: en el lado derecho de estas representaciones, verá un montón de líneas de contorno extrañas en ángulos horizontales y verticales perfectos. Estos son artefactos del proceso de interpolación, que utiliza una cuadrícula de interpoladores para reducir el número de cálculos (en aproximadamente un 500%) necesarios para realizar las operaciones de representación central. Todas esas líneas de contorno extrañas se producen en el límite entre dos celdas de la cuadrícula del interpolador.

Afortunadamente, esos artefactos en realidad no importan. Aunque los artefactos son detectables durante el cálculo de la pendiente, el renderizador final no los notará, ya que opera a una profundidad de bits diferente.

---

ACTUALIZAR DE NUEVO:

Aaaaaaay, como una indulgencia final antes de que me vaya a dormir, aquí hay otro par de representaciones, una en la vieja escuela "color continuo" estilo, y uno con 20,000 muestras de gradiente. En este conjunto de representaciones, he eliminado el punto rojo para muestras puntuales, ya que innecesariamente abarrota la imagen.

Aquí, realmente puede ver los artefactos de interpolación a los que me referí anteriormente, gracias a la estructura de cuadrícula de la colección de interpoladores. Debo enfatizar que esos artefactos serán completamente invisibles en la representación final del contorno (ya que la diferencia de magnitud entre dos celdas interpoladoras adyacentes es menor que la profundidad de bits de la imagen renderizada).

¡Buen provecho!

??

??

Answer 1

El gradiente es un operador matemático que puede ayudarlo.

Si puede convertir su interpolación en una función diferenciable, el gradiente de la altura siempre apuntará en la dirección del ascenso más pronunciado. Todas las curvas de igual altura son perpendiculares al gradiente de altura evaluado en ese punto.

Su idea de comenzar desde el punto más alto es sensata, pero podría perder características si hay más de un máximo local.

Sugeriría

1. seleccione valores de altura en los que dibujará líneas
2. cree un montón de puntos en una cuadrícula fina y regularmente espaciada, luego camine cada punto en pequeños pasos en la dirección del gradiente hacia la altura más cercana a la que desea dibujar una línea
3. crea curvas al pasar cada punto perpendicular al gradiente; elimine el exceso de puntos eliminando un punto cuando otra curva se acerque demasiado a él, pero para evitar destruir el centro del reloj de arena como figuras, es posible que deba verificar el ángulo entre el vector orientado perpendicular al gradiente para ambos puntos. (Cuando digo orientado, quiero decir, asegúrese de que el ángulo entre el gradiente y el valor perpendicular que calcule sea siempre de 90 grados en la misma dirección).

Answer 2

Alternativamente, existe el algoritmo cuadrados de marcha que parece apropiado para su problema, aunque usted puede querer suavizar los resultados si usa una grilla gruesa.

Las curvas topográficas que desea dibujar son isosuperficies de un campo escalar en 2 dimensiones. Para isosuperficies en 3 dimensiones, está el algoritmo cubos de marcha .

Answer 3

En respuesta a su comentario a @erickson y para responder al punto sobre el cálculo del gradiente de su función. En lugar de calcular las derivadas de su función de 300 términos, podría hacer una diferenciación numérica de la siguiente manera.

Dado un punto [x, y] en su imagen, podría calcular el gradiente (dirección de la pendiente más pronunciada)

g={  ( f(x+dx,y)-f(x-dx,y) )/(2*dx), 
  {  ( f(x,y+dy)-f(x,y-dy) )/(2*dy) 

donde dx y dy podrían ser el espacio en su cuadrícula. La línea de contorno se ejecutará perpendicular al gradiente. Entonces, para obtener la dirección del contorno, c, podemos multiplicar g = [v, w] por matriz, A = [0 -1, 1 0] dando

c = [-w,v]

Answer 4

Yo mismo quería algo como esto, pero no he encontrado una solución basada en vectores.

Sin embargo, una solución basada en ráster no es tan mala, especialmente si sus datos están basados ??en ráster. Si sus datos también están basados ??en vectores (en otras palabras, tiene un modelo 3D de su superficie), debería poder hacer algunos cálculos matemáticos reales para encontrar las curvas de intersección con planos horizontales a diferentes elevaciones.

Para un enfoque basado en ráster, miro cada par de píxeles vecinos. Si uno está por encima de un nivel de contorno y uno está por debajo, obviamente, una línea de contorno corre entre ellos. El truco que utilicé para suavizar la línea de contorno es mezclar el color de la línea de contorno en ambos píxeles, proporcional a su cercanía a la línea de contorno idealizada.

Quizás algunos ejemplos ayuden. Supongamos que el píxel actual está en una elevación '' de 12 pies, un vecino está a una altura de 8 pies, y las líneas de contorno son cada 10 pies. Luego, hay una línea de contorno a medio camino; pintar el píxel actual con el color de la línea de contorno al 50% de opacidad. Otro píxel está a 11 pies y tiene un vecino a 6 pies. Colorea el píxel actual al 80% de opacidad.

alpha = (contour - neighbor) / (current - neighbor)

Desafortunadamente, no tengo el código a mano, y podría haber sido un poco más (recuerdo vagamente que también miré a los vecinos diagonales y ajusté por sqrt (2) / 2 ) Espero que esto sea suficiente para darte una idea general.

Answer 5

Se me ocurrió que lo que intentas hacer sería bastante fácil de hacer en MATLAB, usando la función de contorno. Hacer cosas como hacer aproximaciones de baja densidad a sus contornos probablemente se puede hacer con un procesamiento posterior bastante simple de los contornos.

Afortunadamente, GNU Octave, un clon de MATLAB, tiene implementaciones de varias funciones de trazado de contornos. Podrías mirar ese código para un algoritmo y una implementación que casi seguramente sea matemáticamente sólida. O bien, es posible que pueda descargar el procesamiento a Octave. Consulte la página en interactuando con otros idiomas para ver si eso sería más fácil.

Divulgación: no he usado mucho Octave, y en realidad no he probado su trazado de contorno. Sin embargo, según mi experiencia con MATLAB, puedo decir que le dará casi todo lo que está pidiendo en solo unas pocas líneas de código, siempre que ingrese sus datos en MATLAB.

Además, felicidades por hacer una trama de pendiente muy parecida a VanGough.

Answer 6

Siempre reviso lugares como http://mathworld.wolfram.com antes de profundizar solo :)

¿Quizás su sección curvas ayudaría? O tal vez la entrada en mapas .

Answer 7

compara lo que has renderizado con un mapa topográfico del mundo real: ¡me parecen idénticos! no cambiaría nada ...

Answer 8

Escriba los datos como un archivo HGT (muy simple formato de datos de elevación digital utilizado por USGS) y use la herramienta gratuita y de código abierto gdal_contour para crear contornos Eso funciona muy bien para los mapas terrestres, la restricción es que los puntos de datos son números con signo de 16 bits, lo que se adapta muy bien al rango terrenal de alturas en metros, pero puede no ser suficiente para sus datos, lo que supongo que no es un mapa del terreno real, aunque mencionas mapas de terreno.

Answer 9

Recomiendo el CONREC enfoque:

• Crear una lista de segmentos de línea vacía
• Divide tus datos en cuadrados de cuadrícula regulares
• Para cada cuadrado de la cuadrícula, divídalo en 4 triángulos componentes:
  • Para cada triángulo, maneje los casos (a hasta j):
    • Si un segmento de línea cruza uno de los casos:
      • Calcular sus puntos finales
      • Almacenar el segmento de línea en la lista
• Dibuje cada segmento de línea en la lista de segmentos de línea

Si las líneas son demasiado irregulares, use una cuadrícula más pequeña. Si las líneas son lo suficientemente suaves y el algoritmo está tardando demasiado, use una cuadrícula más grande.