algorithm - topograficos - Dibujando un mapa topográfico

planos topograficos pdf (9)

He estado trabajando en un proyecto de visualización para datos continuos bidimensionales. Es el tipo de cosa que podrías usar para estudiar los datos de elevación o los patrones de temperatura en un mapa 2D. En esencia, es una manera 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, así que me quedaré con ella a lo largo de esta publicación.

De todos modos, en este punto, tengo un renderizador de "color continuo" 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 acercamiento arbitrario profundo a los detalles del mapa.

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

Para darte una idea de lo que estoy pensando, aquí hay una implementación de un hombre pobre (donde el procesador solo usa un valor RGB negro cada vez que encuentra un píxel que intersecta 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 (ya menudo rotas). Idealmente, todas las líneas topo deben ser continuas.
Las áreas del gráfico con una pendiente más plana dan como resultado líneas topográficas más anchas (y a menudo regiones enteras de negrura, especialmente en el perímetro exterior de la región de reproducción).

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

En cada elevación discreta en la que 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.
Elimina los 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 las curvas de bezier, a menudo es posible eliminar los puntos de anclaje de cetain ajustando la posición de los puntos de control adyacentes.
Ensamble los puntos restantes en una secuencia, de modo que cada segmento entre dos puntos se aproxime a una trayectoria neutra de elevación, y de tal forma que no se crucen dos segmentos de línea alguna vez. Cada secuencia de puntos debe crear un polígono cerrado o intersecarse con el cuadro delimitador de la región de representación.
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.
Asegúrese de que todas las características de la topografía visible en la escala de representación actual estén representadas por líneas topográficas apropiadas. Por ejemplo, si los datos contienen un pico 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 entidad es menor que la granularidad de representación general de la imagen.

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

Encuentra el punto más alto dentro del cuadro delimitador de representación. Desde ese punto alto, viaja 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 segmento específico de elevación. Cuando la ruta transversal alcance un mínimo local, cambie de rumbo y viaje cuesta arriba.
Realice un recorrido transversal de alta resolución a lo largo del cuadro delimitador rectangular de la región de renderizado. En cada umbral de elevación (y en los puntos de inflexión, donde sea que 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 límite en esos cubos.
Escanee toda la región de representación, tomando una medición de elevación en un intervalo regular escaso. Para cada medición, utilice su proximidad a un umbral de elevación como un mecanismo para decidir si realiza 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 renderizado, pero sería difícil ensamblar los puntos resultantes en un orden razonable para construir rutas.

Entonces, esos son algunos de mis pensamientos ...

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

Editar:

Estoy especialmente interesado en la sugerencia de "Gradiente" hecha por ellisbben. Y mi estructura de datos básicos (ignorando algunos de los métodos abreviados de interpolación de optimización) se puede representar como la suma de un conjunto de funciones gaussianas en 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 para 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!

ACTUALIZAR:

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

Aquí hay representaciones actualizadas, con y sin el renderizador de topo basado en rastros 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 ninguna 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.

¡Disfrutar!

(NOTA: Estas representaciones utilizan una topografía de superficie diferente a las representaciones anteriores, ya que genero aleatoriamente las estructuras de datos en cada iteración, mientras estoy prototipando, pero el método de representación del núcleo es el mismo, así que estoy seguro de que obtienes la idea.)

Aquí hay un hecho divertido: en el lado derecho de estas representaciones, verás un grupo de líneas de contorno extrañas con ángulos perfectos horizontales y verticales. 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 del núcleo. Todas esas líneas de contorno extrañas ocurren en el límite entre dos celdas de cuadrícula interpoladoras.

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

Y como una indulgencia final antes de irme a dormir, aquí hay otro par de representaciones, una en el estilo de "color continuo" de la vieja escuela y otra con 20,000 muestras de degradado. En este conjunto de representaciones, eliminé el punto rojo para las muestras de puntos, ya que desordena innecesariamente la imagen.

Aquí, puedes ver realmente los artefactos de interpolación a los que me he referido 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 del contorno final (ya que la diferencia de magnitud entre dos celdas interpoladoras adyacentes es menor que la profundidad de bit de la imagen renderizada).

¡¡Buen provecho!!

Alternativamente, existe el algoritmo de cuadrados de marcha que parece apropiado para su problema, aunque es posible que desee suavizar los resultados si utiliza una grilla gruesa.

Las curvas topo que desea dibujar son isosuperficies de un campo escalar de más de 2 dimensiones. Para las isosuperficies en 3 dimensiones, existe el algoritmo de los cubos de marcha .

En respuesta a su comentario a @erickson y para responder el punto sobre el cálculo del gradiente de su función. En lugar de calcular los derivados de su función de 300 términos, puede 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 mayor pendiente)

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 espaciado en su grilla. 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 la matriz, A = [0 -1, 1 0] dando

c = [-w,v]

Siempre controlo lugares como http://mathworld.wolfram.com antes de profundizar por mi cuenta :)

Tal vez su sección de curvas ayudaría? O tal vez la entrada en los mapas .

Yo mismo he querido 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 se basan en vectores (en otras palabras, tiene un modelo 3D de su superficie), debería poder hacer cálculos matemáticos reales para encontrar las curvas de intersección con planos horizontales a diferentes alturas.

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 evitar el alias de 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.

Tal vez algunos ejemplos ayuden. Supongamos que el píxel actual está a una "elevación" de 12 pies, un vecino está a una elevación de 8 pies y las líneas de contorno son cada 10 pies. Luego, hay una línea de contorno a medio camino entre ellas; Pinte 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)

Lamentablemente, no tengo el código a mano, y podría haber sido un poco más (recuerdo vagamente también mirar vecinos diagonales, y ajustar por sqrt(2) / 2 ). Espero esto lo suficiente como para darte la esencia.

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

Se me ocurrió que lo que está tratando de 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 pueda 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 curvas de nivel. Podrías mirar ese código para un algoritmo e implementación que es casi seguro matemáticamente sólido. O bien, puede descargar el procesamiento a Octave. Consulte la página en la interfaz con otros idiomas para ver si eso sería más fácil.

Divulgación: no he usado mucho Octave, y realmente no he probado su trazado de curvas de nivel. Sin embargo, desde mi experiencia con MATLAB, puedo decir que le dará casi todo lo que está solicitando en unas pocas líneas de código, siempre que obtenga sus datos en MATLAB.

Además, felicidades por hacer un diagrama de campo de pendientes muy similar a VanGough.

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

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 empinado. 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

seleccione valores de altura en los que dibujará líneas
crea un montón de puntos en una cuadrícula fina y regularmente espaciada, luego camina cada punto en pequeños pasos en la dirección del degradado hacia la altura más cercana a la que quieras dibujar una línea
cree curvas haciendo que cada punto sea perpendicular al degradado; elimine los puntos de exceso matando un punto cuando otra curva se acerca demasiado a él, pero para evitar destruir el centro del reloj de arena como las figuras, puede que necesite comprobar 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 calcula sea siempre de 90 grados en la misma dirección).

Recomiendo el enfoque CONREC :

Crear una lista de segmentos de línea vacía
Divida sus datos en cuadrados regulares de la cuadrícula
Para cada cuadrado de cuadrícula, divide el cuadrado 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:
    - Calcule sus puntos finales
    - Almacenar el segmento de línea en la lista
Dibuja cada segmento de línea en la lista de segmentos de línea

Si las líneas son demasiado irregulares, usa una cuadrícula más pequeña. Si las líneas son lo suficientemente lisas y el algoritmo tarda demasiado, use una grilla más grande.

Escriba los datos como un archivo HGT (formato de datos de elevación digital muy simple utilizado por USGS) y use la herramienta gratuita y de código abierto gdal_contour para crear contornos. Eso funciona muy bien para mapas terrestres, la restricción es que los puntos de datos son números de 16 bits con signo, que se ajusta 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 los mapas del terreno.