java algorithm vba interpolation triangulation

java - Ubique el triángulo que contiene el punto arbitrario en la superficie triangulada de Delaunay



algorithm vba (5)

Estoy buscando hacer una interpolación lineal de una función muestreada irregularmente z(x,y) basada en una triangulación de Delaunay. Digamos que tengo una colina para la cual obtuve una triangulación de Delaunay:

Sé la altitud z en cada uno de los vértices del triángulo (muestras). Quiero la altitud z en un punto arbitrario (x,y) .

  • ¿Cómo puedo saber qué triángulo contiene el punto (x,y) ? Una vez que sé esto, creo que es bastante sencillo interpolar entre los tres vértices del triángulo.

  • ¿Conoces una implementación ya hecha de esto? Tal vez con el bit de interpolación incluido también? Estoy seguro de que debe haber una implementación de código abierto de esto en algún lugar. Estoy especialmente interesado en Java (fuente o JAR), pero cualquier sabor de VB o algún otro lenguaje podría ser útil también.

El conocimiento de mis algoritmos está un poco oxidado. En lugar de mi respuesta anterior, probablemente sea mejor utilizar un diagrama de Voronoi .

Se puede construir una estructura de datos de ubicación de puntos sobre el diagrama de Voronoi para responder a las consultas vecinas más cercanas, donde uno quiere encontrar el objeto más cercano a un punto de consulta dado. Las consultas de vecinos más cercanos tienen numerosas aplicaciones. Por ejemplo, uno podría querer encontrar el hospital más cercano o el objeto más similar en una base de datos.

No puedo ayudarte con los detalles de esto, pero espero que esto te pueda orientar en la dirección correcta.

Supongo que también podrías usar un R-tree en el que enlazas a tus triángulos.

Una búsqueda rápida en google con ''java r-tree'' debería ayudarlo a encontrar bibliotecas existentes.

Esta no es una pregunta fácil de responder, y depende del rendimiento que requiera de su búsqueda, y de la cantidad de memoria que esté preparado para negociar para obtener ese rendimiento.

Si esta es una operación muy rara, o su número de triángulos es pequeño, entonces siempre puede iterar a través de todos los triángulos. Probar un triángulo que contenga un punto no es muy caro. Probablemente deberías codificar esto primero y ver si da un rendimiento aceptable.

Si no es aceptable, puede intentar caminar a través de la triangulación , esencialmente comenzar con un triángulo y luego encontrar el siguiente más cercano al punto que está buscando. Esto asume que tienes algo de información extra sobre una simple lista de triángulos, específicamente que puedes encontrar los triángulos que usan un vértice dado (o encontrar un triángulo de su triángulo vecino, que es aproximadamente equivalente en complejidad). Si no tiene esto calculado, entonces es casi tan caro como encontrar un punto.

Si eso no es lo suficientemente rápido, necesitas configurar algún tipo de R-Tree . Esto le permite encontrar triángulos desde sus ubicaciones muy rápidamente, pero necesita mucho preprocesamiento y una gran cantidad de memoria para el árbol.

Puede encontrar que el tiempo para calcular el preproceso para cada uno de los segundos y terceros métodos es más que el tiempo para buscar los triángulos mediante una búsqueda exhaustiva, si no lo hace a menudo.

Puedes encontrar el triángulo objetivo caminando a través de la triangulación hacia el punto buscado. Esto supone que puede acceder a triángulos vecinos en tiempo constante, que es el caso si la triangulación está almacenada en una lista de bordes doblemente conectados o estructuras similares. La implementación es sencilla porque no necesita estructuras de datos adicionales.

Detalles adicionales : Sea P el punto buscado. Tome cualquier triángulo T0 y un punto P0 en T0. Si P está en T0, has terminado. De lo contrario, encuentre el borde E0 de T0 que cruza la línea P0-P. Vaya al triángulo vecino T1 de T sobre el borde E0 y tome un punto P1 en T1. Ahora repite hasta que el triángulo Tn contenga P.

Encontré una implementación que funciona aquí: http://www.cs.bgu.ac.il/~benmoshe/DT/

El método find encuentra el triángulo que contiene un punto dado, y el método z realiza la interpolación plana.

Desafortunadamente es un JAR compilado, así que no sé cuál es el algoritmo, pero siento que "camina a través de la triangulación" como lo sugieren @Jiri y @DJClayworth.

También desafortunada es la nomenclatura bastante poco convencional utilizada en este JAR. Puedo terminar escribiendo una clase contenedora con una nomenclatura más agradable.