El alto del algoritmo de generación?

Question

Yo estaba buscando alrededor de la Internet y no podía encontrar un algoritmo perfecto para este problema en particular:

Nuestro cliente tiene un conjunto de puntos y los datos de peso a lo largo de cada punto como se puede demostrar por esta imagen:

puntos ponderados http://chakrit.net/files/stackoverflow/so_heightmap_points.png

De los cuales, tenemos un programa de SIG que podría generar un "mapa de altura" o un tipo de datos sobre el terreno de estos puntos y sus valores de peso, sino como que tenemos cerca de un millar de puntos de datos y que éstos va a cambiar con el tiempo, le gustaría crear nuestras propias herramientas para auto-generar estos mapas de altura.

Hasta ahora, he tratado de calcular el peso para cada píxel de su distancia al punto de datos más cercano con Sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2) y aplicando el peso y el factor de la distancia al color del punto de datos para producir el color del gradiente resultante para ese píxel en particular:

de alturas resultan http://chakrit.net/files/stackoverflow/so_heightmap_result.png

Se puede ver que todavía hay problemas con cierta configuración de puntos de datos y el algoritmo a veces producir una imagen en lugar poligonal cuando hay una gran cantidad de puntos de datos. El resultado ideal debería parecerse más a una elipsis y menos como un polígono.

Esta es una imagen de ejemplo del artículo de Wikipedia sobre el ascenso del gradiente que demuestra el resultado que quiero:

montañas http://chakrit.net/files/stackoverflow/so_gradient_descent.png

El algoritmo de gradiente de ascenso no es de mi interés. Lo que me interesa; es el algoritmo para calcular la función original en que la imagen en primer lugar, siempre que los puntos de datos con los pesos.

No he tomado ninguna clase en matemáticas topológicas, pero puedo hacer algo de cálculo. Creo que puede estar pasando algo y estoy bastante perdido en lo que debería escribir en ese cuadro de búsqueda de Google.

Necesito algunos consejos.

Gracias!

Answer 1

Lo que se busca es la interpolación de superficie.

Existen algunos productos para hacer esto (aquí está uno )

La función / spline resultante / otra construcción matemática puede entonces ser interrogado en la resolución requerida para suministrar el mapa de altura.

Su función de interpolación

Sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2) 

métodos ponderado inverso de la distancia, excepto que están aplicando un filtro arbitrario y descartando muchos de los otros puntos de datos.

La mayoría de estas técnicas se basan en un número razonable de muestras y 'terreno-como' la conducta que sustenta los valores.

sugiere emplear el peso que la muestra de altura y tratando método simple de Shepard en el segundo link (No filtrar los píxeles para empezar), tomando la proporción de una contribución puntos de muestra para el valor global altura a un punto de interpolación se pueden mezclar los colores de las muestras en esas proporciones para colorear también el punto. Utilice la intensidad (en términos generales la escala de grises en el espacio RGB sencilla) para mostrar la altura o añadir curvas de nivel de negro como lo hace la imagen de ejemplo.

Answer 2

Este problema no es tan fácil como se ve en la superficie. Su problema es que ambos lados de la frontera de dos regiones deben tener la misma altura, es decir, la altura a un píxel dado está determinada por más de un vecino más cercano.

Si he entendido bien, se necesitan al menos dos algoritmos (y una tercera pieza de la jerga).

Para hacer esto correctamente, es necesario romper el plano en una de Voronoi tesselation .

Usted probablemente va a querer utilizar un rel="nofollow noreferrer"> kd-árbol para ayudarle encontrar el vecino más cercano. En lugar de tomar O (n ^ 2), esto va a bajarla a O (n log (n)) (el beneficio añadido es que su fase de generación región de Voronoi será lo suficientemente rápida en el desarrollo para trabajar en la fase de cálculo de la altura).

Ahora que tiene un mapa 2-D indexación de cada punto de su vecino más cercano i, tiene que caminar a través de cada x, y punto en el mapa y calcular su altura.

Para hacer eso por un punto dado x, y, primero agarrar su vecino más cercano y se adhieren i que en una lista, a continuación, recoger todas las regiones contiguas en el diagrama de Voronoi. Una forma fácil es usar encontrar todos los puntos de la región, a continuación, mire a su alrededor la frontera y recoger las otras identidades.

El uso de esta lista de todos los vecinos más cercanos, ahora tiene una oportunidad de interpolación correctamente! (Ver otras respuestas a los regímenes de interpolación).

Answer 3

Usted ha pedido información sobre los algoritmos para 2-D interpolación de datos irregulares, que es una zona bastante compleja. Puesto que usted dice que tiene ArcGIS, I recomiendo encarecidamente le permite interpolar automáticamente en ArcGIS utilizando su base de características para los cálculos automáticos. Estoy seguro de que será mucho más fácil que escribir su propio algoritmo de interpolación. He hecho algunas automatización de ArcGIS, es bastante sencillo.

Si escribe su propio código de interpolación - Te aconsejo que no - lo primero es elegir el algoritmo adecuado ya que hay varios, cada uno con sus propias ventajas y desventajas. He aquí algunos consejos cribbed de la ayuda para la excelente herramienta de interpolación Surfer (que BTW también puede ser automatizado con bastante facilidad). Existen varios algoritmos, estos son sólo los que he probado.

• Kriging es uno de los métodos más flexibles y es útil para gridding casi cualquier tipo de conjunto de datos. Con la mayoría de los conjuntos de datos, Kriging con el variograma lineal por defecto es bastante eficaz. En general, nos lo más a menudo recomiendan este método. Kriging es el método por defecto de cuadriculado, ya que genera un buen mapa para la mayoría de los conjuntos de datos. Para los conjuntos de datos más grandes, Kriging puede ser bastante lento. Kriging puede extrapolar valores de la cuadrícula más allá de gama Z de sus datos.
• ponderación de distancia inversa es rápido, pero tiene la tendencia a generar "ojo de buey" patrones de contornos concéntricos alrededor de los puntos de datos. Distancia inversa a una potencia no extrapola valores Z más allá del rango de datos. Un simple algoritmo de ponderación de distancia inversa es fácil de aplicar, pero será slowish.
• La triangulación con interpolación lineal es rápida. Cuando se utiliza pequeños conjuntos de datos, triangulación con interpolación lineal genera caras triangulares entre distintos puntos de datos. La triangulación con interpolación lineal no extrapolar valores Z más allá del rango de datos.
• Método de Shephard es similar a la distancia inversa a una potencia, pero no tiende a generar "ojo de buey" patrones, especialmente cuando se utiliza un factor de suavizado. Método de Shepard pueden extrapolar los valores más allá del rango Z de sus datos.

A fin de aplicar los algoritmos: Usted puede intentar buscar en Google, o seguir los enlaces en algunas de las otras respuestas. Hay algunos SIG de código abierto que incluyen la interpolación, lo que tal vez puede extraer los algoritmos de ellos si te gusta la espeleología a C ++. O este libro por David Watson es aparentemente considerado un clásico, a pesar de que es una lectura difícil y el código de ejemplo es el espagueti básico !! Pero, por lo que escucho, que es la mejor disponible. Si cualquier otra persona en el desbordamiento de pila conoce mejor, por favor corríjanme ya que no puedo creer.

Answer 4

Kriging es uno de los métodos de peso pesado para hacer esto, en particular en el campo de la GIS . Tiene varias propiedades matemáticas agradables - la desventaja es que puede ser lento dependiendo de su .

Si quieres algo más sencillo, hay muchas rutinas de interpolación que manejan esta bastante bien. Si usted puede conseguir el ahold de una copia de Numerical Recipes , capítulo 3 está dedicado a explicar muchas variantes para la interpolación, e incluye ejemplos de código y descripciones de sus propiedades funcionales.

Answer 5

  

es el algoritmo para calcular el   función original de esa imagen en   el primer lugar, los puntos de datos proporcionados   con pesos.

Es posible. Si usted comienza con los puntos únicos que siempre va a terminar con los círculos, pero si el peso de los puntos de datos y toma en cuenta que se puede aplastar a los círculos en óvalos como en la imagen ..

La razón que usted está terminando con polígonos es que usted está utilizando una función discreta en su cálculo -. Primero a encontrar el color más cercano, a continuación, a determinar el color

En su lugar debe mirar en algoritmos de gradiente que asigna un color para un punto en función de la distancia y el peso de los tres puntos de datos que encierran ese punto en un triángulo.

algoritmo de gradiente

Depende de lo que estás tratando de mostrar. Un algoritmo simplista sería:

Para cada píxel:

• Para los tres puntos que forman el triángulo más pequeño que rodean este pixel

• Establecer este punto a la (sistema de color HSV) de color que se ve afectada tanto por el peso y la distancia a cada punto de datos:

  pixel.color = datapoint[1].weight * distance(pixel, datapoint[1]) * datapoint[1].color + datapoint[2].weight * distance(pixel, datapoint[2]) * datapoint[2].color + datapoint[3].weight * distance(pixel, datapoint[3]) * datapoint[3].color

Estoy usando + aquí, pero es necesario para determinar el algoritmo 'promedio' adecuado para su aplicación.

-Adán

Answer 6

interpolación de superficie parece ser un problema difícil y matemática. Otra, mucho más barato que hacer es:

For each pixel:
For each point:
pixel.addWeight(weight(point, pixel))

def addWeight(w):
totalweight += w
numberofweights += 1
weight = totalweight / numberofweights

función Ejemplo peso:

def weight(point, pixel):
return point.weight * 1/(1 + sqrt((point.x - pixel.x)^2 + (point.y - pixel.y)^2))

Es un buen método de fuerza bruta, pero es simple.

Answer 7

He implementado algo como esto en Winamp AVS hace un tiempo. Se utiliza un "metaballs" enfoque de tipo de cálculo de la inversa al cuadrado distancia (para evitar la sqrt para la velocidad) de cada punto de datos, la limitación de que (por ejemplo a 1,0), y teniendo una suma de esas distancias para cada punto de la rejilla 2D. Esto dará un mapa de color / altura que varía suavemente.

Si quiere mirar el código, está en el preset "Glowy" de mi J10 AVS empacar .

EDIT: La sola observación de que he añadido algunos otros jazz para que se vea más bonita, la parte que es más importante es:

d1=s/(sqr(px1-rx)+sqr(py1-ry));
d2=s/(sqr(px2-rx)+sqr(py2-ry));
d3=s/(sqr(px3-rx)+sqr(py3-ry));
d4=s/(sqr(px4-rx)+sqr(py4-ry));
d5=s/(sqr(px5-rx)+sqr(py5-ry));
d6=s/(sqr(px6-rx)+sqr(py6-ry));
d=d1+d2+d3+d4+d5+d6;

¿Qué lleva a la suma de los 6 puntos. Todo lo demás hecho para los valores de salida de color rojo, verde y azul es para que se vea más bonito. 6 puntos no es mucho, pero tenga en cuenta que yo estaba tratando de hacer esta carrera en tiempo real en una cuadrícula de 320x200 en una máquina de 400 MHz cuando era nuevo (que lo hace en ~ 20 cuadros por segundo). :)

Reemplazar los = rojo, verde y azul = = ... con líneas de color rojo = d; etc ... para ver lo que quiero decir. Toda la hermosura se va y lo que queda es una imagen en escala de grises con problemas de diferentes manchas alrededor de los puntos de datos.

Otra edit: me olvidó decir "s" es el peso compartido para todos los puntos, cambiándolo para cada uno da pesos individuales para cada punto, por ejemplo, d1 = 2 / (...) y d2 = 1 / (...) daría D1 doble de altura en su centro como d2. También puede ser que desee limitar la expresión en la parte inferior con algo como d1 = 2 / max (..., 1.0) para alisar la parte superior de los puntos por lo que no alcanzar su punto máximo en el infinito en el medio. :)

Lo siento por el desorden de la respuesta ... pensé publicar el ejemplo de código sería lo suficientemente bueno pero en una inspección mi código es confuso y difícil de leer. : (

Answer 8

Sé que esto es bastante una vieja pregunta, pero me encontré con que al tratar de resolver un problema similar.

Hay un proyecto de código abierto llamado Surfit que implementa exactamente este tipo de funcionalidad.

Answer 9

Usted está buscando algo que Blender llamadas " metaballs " ( Wikipedia artículo con enlaces , ejemplo ). Piénsalo de esta manera:

Sus objetos son conos que sobresalen del suelo. Todos ellos son parábolas y el peso indica la distancia que sobresalen del suelo. Por otra parte, hacer que todos la misma altura y ajuste el "aplanamiento" de la parábola en consecuencia, por lo que un gran peso hace que el cono muy amplia, mientras que un bajo peso hace que sea agudo. Tal vez incluso ambos a un cierto grado.

Sugiero que implemente esto y ver cómo se ve.

A continuación, tiene que pasar un paño o una lámina de goma sobre el resultado. La tela se estira por una cierta cantidad y se cuelgan generalmente debido a la gravedad. Los conos sigan así.

Mientras usted está cerca del centro de un cono, la coordenada Z es sólo la posición en la superficie del cono. Al salir del centro del cono, la gravedad empieza a tirar hacia abajo y la influencia de otros conos crece.