SoloCodigo

¿Y si nos explicases qué es interpolar...?

4.  tr. Mat. Calcular el valor aproximado de una magnitud en un intervalo cuando se conocen algunos de los valores que toma a uno y otro lado de dicho intervalo.

pero sigo sin entender...

Sí, si interpolar lo entiendo, lo que no entiendo es cómo lo aplicas tú en tu ejemplo, para poder especificarte un algoritmo más concreto.

Vale, ahora está más claro que el agua  

La cuestión es si los valores aparecen en posiciones aleatorias o siguen un determinado orden, porque veo que crecen hacia la esquina superior izquierda, mientras que a derecha y abajo son más bajos (en este ejemplo, no en los anteriores)

No es exactamente una imagen, sino una red de circuitos eléctricos acoplados, pero el tratamiento debe de ser similar: son celdas con valores (en este caso, los valores son voltajes), que no se pueden mover ni ordenar porque variaría el orden de la red y por tanto no serviría.

Cuando me refiero a figuras más complejas es a las "líneas  de nivel" que hacen formas mas extrañas, como las de la imagen, en las que claramente mi algoritmo no sirve y obtengo formas extrañas.

[attachment=1:31xue8li]image.png[/attachment:31xue8li]

Cuando el resultado debería ser aproximadamente esto (obtenido con Matlab):

[attachment=0:31xue8li]untitled.jpg[/attachment:31xue8li]

Explícame un poco mas el concepto de líneas de nivel, pues creo que se aplica lo que intento realizar.

Un saludo

Te paso algunos enlaces:
Isolínea http://es.wikipedia.org/wiki/Isol%C3%ADnea
Conjunto de nivel: http://es.wikipedia.org/wiki/Conjunto_de_nivel

A tu algoritmo le puede añadir un conjunto de reglas para hacerlo más efectivo. Te iré enumerando ideas y si necesitas profundizar me lo dices.

Para empezar Deberías marcar un 'centro' es decir deberías definir el valor máximo de luminancia y el mínimo y localizarlos dentro del mapa. Ahora con ese área se marca con un único punto, este ya no podrá ser usado, salvo que haya varios adhyacentes (que no sea el único). Si hay más de uno, trata de rodearlos con una línea de puntos (más abaj se irán describiendo alguna reglas).

Ahora como ves en vez de partir desde abajo-izquierda, partimos del punto más brillante. Una vez rodeado esos pocos puntos centrales sus casillas se marcan en una matriz. Ahora buscamos el siguiente punto inferior en intensidad, cuando rodeemos con este seguiremos igualmente bajando el nivel de brillo buscando por ellos. Mientras queden áreas libres o no se alcance un nivel mínimo de brillo previamente fijado, repetiremos en forma de bucle ese paso.

Para hacer esos pasos falta definir un conjunto de reglas... las 2 primeras las hemos definido precipitadamente, hallar el punto/s central/es y desde ellos ir trazando areras externas...

La primera regla es al buscar el siguiente punto, no podrá ser candidato un punto interno a un área ya cerrada. Los cuadrantes de las áreas ya cerradas se pasan a una matriz para chequear esta regla.

La segunda regla es un punto nunca podrá avanzar directamente a una distancia superor a un 'cuadrante' , hay por tanto una relación de vecindad que se define más adelante.

La tercera regla, el área de exploración de un punto son sus 8 puntos circundantes, excepto 2 de ellos, el previo del que este viene y el 'abuelo' previo.

Cuarta regla cuando haya 2 o más puntos elegibles, se elegirá aquel que más se aproxime al centro (al píxel que definimos como centro del mapa, para ello si es preciso se hace en cálculo de distancia euclidiana.

Si hay más de 1 punto elegible con la misma distancia se elegirá con preferencia aquel que avance en la dirección actual de avance (avance general respecto del cuadrante, el cuadrante no es partir el mapa por el centro sino dividirlo por el punto más brillante, vertical y horizontalmente, estar en un cuadrante implica la dirección de subir, bajar, derecha o izquierda. Al caso un área en forma de rombo define más claramente una dirección pero su cálculo resulta más costoso).

Un punto que sale del mapa por un lateral debe intentar continuar por el siguiente cuadrante en el primer área libre. Si en el cuadrante por el que sale aún hubiera en su dirección de avance áreas libres haría a entrar y si se precisa volver a salir, pero avanzando en la dirección de giro.

Si un punto no encuentra avance próximo a su dirección de avance puede cambiar su avance '90º'  con preferencia a '180º', es decir debe elegir el punto más favorable a seguir su dirección hasta que salga del cuadrante, una vez salido del cuadrante la norma que prevalece es la norma del nuevo cuadrante. a efectos de 'tramas' complejas, resultará más útil marcar 6,8 o más cuadrantes, de hecho para una aproximación más realista usar 360 cuadrantes basados en grados respecto de lo que definimos como centro sería muy efectivo manteniendo a la vez uno de 4 cuadrantes y operando buleanamente sobre ambos. Habria que dar ponderación mayor al de grados a medida   que el 'radio' aumenta.

Un punto debería intentar buscar al primero como meta tras completar el cuadrante 3º, al hacerlo  se considera área cerrada la interna a dichas líneas, se marcan en la matriz y se procede a por otro nivel inferior en el bucle de brillo.
-----------

En vez de hacer una interpolación de los puntos yo te sugeriría una intercalación, subdiviiiidiendo cada área en 5 a lo largo y 5 a lo ancho, así un área actual puede ser 'pisada por bastantes más puntos y trazar líneas más fielmente. La diferencia con el sistema que tienes ahora es que el sistema actual es más analógico y menos digital, aunque es más preciso el punto exacto es un área muy grande para ser retirada modularlo te permite ir retirando a una matriz los ya visitados. En la práctica un punto podría ser pisado por tantas líneas como se quiera, pero nunca interior al nivel anterior ya cerrado. Muchas líneas muy prósimas indicarán una caída abrupta del nivel, de ahí que las líneas tiendan a juntarse.

El sistema de oclusión y definición de un centro (0 varios) te permite ir descartando áreas libres y definir reglas.

Piensa en el mapa con el siguiente ejemplo. Imaginemos que hay una nube sobre una población, que esa nube no se moverá en cierto tiempo y que deseamos recorrrer perimetralmente la sombra proyectada sobre el suelo, pero en forma de espiral empezando por un centro de 50 metros hasta el radio externo de 1km.... hechamos a andar y todo va bien es fácil seguir el terreno liso, de repende hay que saltar colina abajo en terrazas, no nos está permitido saltar x terrazas a la vez si no una a una. Ahora imagina que llegamos a un precipicio, no resulta posible pasar, hay que bordear, pero alejándose lo menos posible, finalmente encontramos un pequeño puente que atraviesa un estrecho desfiladero... auqneue rodeemos varias veces (como dijimos en espiral), al llegar a este punto siempre deberemos cruzar por este puente, excepto que alejándonos más exista otro puente u otro  accidente que facilite su acceso. Básicamente en ese ejemplo se dan las mismas circunstancias que al caso que tienes, por tanto cuando te atranques puedes pensar en ello de un modo no abstracto, marcando la similitud entre los casos.

Luego otro método, dependiendo de lo fidedigno que tengas o deses hacer el trazado, yo equivaldría los valores de los voltajes con más variedad de colores y como te digo seccionado cada área en otras mucho más pequeñas. Ya que entonces podrías filtrar la imagen resultante, podrías hacer un histograma y ecualizarlo después... Al trabajar con imágenes se habla de segmentación, que es el primer paso para su análisis, por tanto aplicando un filtro de detección de bordes, tu algoritmo sería finalmente más sencillo de que funcionara, igualmente un filtro direccional sería muy eficaz. Un filtro de este tipo (3*3) aplicado a una imagen de pongamos 800*600 píxeles se aplica en unos pocos segundos en VB...incluso.

Según lo que necesites y por tanto por el método que te decidas podría darte otras indicaciones, para no extenderme vanamente.
-----

p.d.: Se me pasó una regla importante... Dado qu parece que obtienes el siguiente valor a localcizar en el mapa de una forma directa (quizás basado en una variable temporal (elativa al tiempo)), tu problema puede simplificarse ya que las reglas irían condicionadas a buscar el camino desde el punto a hasta el punto a +1 (el nuevo) y mediar que si la distancia es superior a unárea entonces buscar el camino de puntos intermedios hasta alcanzar aquél. La estrategia es algo distinta en cuanto se conoceel destino y se trata de buscar el camino más propicio siguiendo las reglas. como indiqué no es correcto saltar de un área a otra que no sea contigua sino 'bordeando', como hicimos en el ejemplo al llegar al precipicio... al caso la regla para bordear es que el área elegida debe tener un brillo comprendido entre el punto actual y el punto objetico, pero ni mayor ni menor y por supuesto manteniendo las otras reglas de no visitar áreas internas a otras regiones, aunque sí el mismo borde de la última.

En la práctica esto supone que a partir de que el siguiente punto sea distante (por ejemplo en el primer gráfico malo el punto a-6 con respecto a c-6), debe crearse un árbol para definir la ruta a trazar, siendo el punto actual el nodo padre, cada nodo debería tener al menos 3 valores, el siguiente punto que elegimos para seguir después de éste, si descendenciendo por aquella rama resultare ineficaz, necesitamos un valor para especificar que fue recorrido y descartado y otro valor más que indique que desde ese nodo había x nodos (puntos) que perfectamente erán accesibles, esos x nodos se colocaron como hijos de aquel pero se empezó a recorrer el primero de ellos (se supone que al añadirlos como hijos se hizo en orden de preferencia de acuerdo alas reglas implicadas: lleva la misma dirección la diferencia de brillo es la menor  con respecto a él, etc... si después de seguir un camino nos 'pierde'  , vamos ascendiendo en el árbol hasta encontrar un nodo que marque tener más de un hijo posible, entonces marcamod como rechazado el visitado y avazamos por el hermano de éste... Hay algoritmos eficaces para encontrar un camino dadas unas condiciones, sin embargo debes adaptarlo a tus necesidades. Una vez hallada la ruta debes colocar llos puntos que por el árbol llevan desde el objetivo subiendo hasta el actual.

Te adjunto un pequeña imagen de este paso que debería hacer tu algoritmo... estos pasos no están fijados por tu 'generador' de valores y puedes considerarlos al caso como una pérdida de resolución que debes suplir.

Para no estar dando palos de ciego....  prueba los cambios en tu algorimo con una función muy útil para estos casos llamada 'función de Rosembrock'... posiblemente encuentres más info en inglés que en español...

Hola, estoy de nuevo por aquí xD
En la imagen se ve para cada punto, su orden de dibujo. Si uniese ordenadamente las líneas, como en un juego de niños, no saldría la figura correcta, como me pasaba en casos anteriores. ¿Tienes alguna idea para solucionar esto?

Te contesto rápidamente  y mañana con más tranquilidad reviso el archivo y le dedico un poco más de tiempo: Dada una secuencia como la que tienes ahora, para que no se desvirtúe si se sigue el 'orden', hay que proceder de una manera similar a la siguiente:

a ) empezamos por un extremo (localizar un punto tal que al norte no tenga más o si es por abajo al sur no tenga más, o si es a los costados ídem...) en el caso que están todos dispuestos casi verticalmente es relativamente fácil, otra cosa es cuando ýa describen un área cerrada.) igualmente encontrar el otro extremo...

b ) desde dicho punto medir la distancia hasta el otro extremo P0(x,y) - Pn(x,y) y dividirlo entre el total de puntos. a este valor lo llamaremos algo así como paso. será una constante a la que recurrimos al inicio  de cada elemento del bucle dentro del bucle otra variable con este valor inicial podrá irr variando, no es un valor fijo, sólo es una aproximación de entrada...

c )Iniciar un bucle encontrar siguiente elemento :  iniciar bucle localiz_puntos_enradio  mientras_no_se_encuentren_puntos_ aumentar el área: intentoslocalizar +=1:  distancia= paso * intentoslocalizar; Con la distancia distancia averiguar que puntos caen dentro de ese círculo con respecto al punto actual (ahora en este justo instante sería el punto P0,) y descartar de esta matriz de posibles los que ya con anterioridad se hubieran encontrado y admitidos en la secuencia (más adelante se explica esto), el área a barrer podría ser circular o cuadrada, cuadrada es más cómoda de recorrer pero también menos exacta, si el área es cuadrada, convendría que fuera impar para que el punto de referencia esté justo en el centro y eliminar dudas).

c1 ) si no se encontró pntos en ese espacio aumentar distancia por un factor a discreción (paso se obtuvo como una referencia de densidad, pero evidentemente si hubiera una distribución ampliamente lateral aparte de vertical la posibilidad de no hallar puntos a una distancia dada aumentaría), el factor puedes decidirlo de entrada como acumulativo (1,2,3,4,5,6.. sea de radio o de área) una vez cierta experiencia quizás si hay un patrón decidas ajustarlo.

c2 ) se encuentran puntos: se totalizan y se obtiene el punto más cercano. Finaliza este bucle, distancia volverá a ser= a paso,  repetimos bucle global hasta alcanzar el último punto (que debería ser otro extremo ).  Pueden darse casos de equidistancia típicos de un triángulo,( es harto difícil que hubiera más de 2 equidistantes si el trazado es correcto) en dicho caso se debería tomar el más 'extraño' . El más extraño sería una especie de componente, que se las trae, pero que te explico, sobre la línea imaginaria entre el extremo inferior y superior el más extraño es el que: c2a ) si el punto actual está más cerca que los puntos de la línea, el que más se aparta a dicha línea. c2b ) si el punto actual está más lejos que ambos, igual que el paso anterior, c2c ) si el punto actual está aun lado de la línea y los puntos al otro lado el más cercano a la línea, por fin  c2d ) si el punto actual está a un lado y los otrs puntos uno a cada lado de la línea, el que está al mismo lado de la línea. (haciendo unos pequeños dibujos a manos se ve menos lioso que tanta palabra). Trataré de hacer mañana un dibujito sencillo mostrando los 4 casos. Es harto difícil demostrar que el más extraño sea la mejor opción, digamos que abre la posibilidad a no perder nodos teniendo que volver hacia atrás  (a  veces esto no sólo no es indeseable sino necesario, según el digujo).

d ) Paso retomar el estado inicial (cuando lo calculamos por primera vez)  vaciamos la matriz de puntos cercanos, los puntos ya marcados se van indicando en la matriz encontrados, ahora cuando busquemos puntos para un radio cuando se encuentren todos, la matriz de posibles serán esos menos los ya encontrados, es decir rechazaremos los que consten en la matriz encontrados... el ciclo se repite hasta llegar al último punto.

e ) tras alcanzar el último punto hay que verificar si el tamaño de la matriz encontrados es igual al tamaño total de puntos, ya que puede darse un caso extremo (o menos). Por ejemplo supongamos que en ese trazado (el último dibujo que tienes) hubiera un punto en 407... debemos considerarlo un error en el algoritmo o debemos considerarlo un punto erróneo (ruido) durante el marcado ???. En ese momento tu debes interpretar ( no coonozco claramente el objetivo final) si es un fallo en el algoritmo o una detección de ruido que el algoritmo consigue filtrar... y si en el punto 407 hay varios puntos formando una isla (redundando) aislada a cierta distancia del resto ???.  Para solucionar casos así es necesario saber como se debe interpretar, como yo desconozco ese punto, si te sucede y te quedas atascado me das alguna razón del porqué esos puntos para buscar una opción válida al caso que necesites.

Nota que está todo un poco desordenado ya que es una respuesta rápida... con un lápiz y un trozo de papel entresaca en seudocódigo el algoritmo que subyace.

Para facilitar todas las tareas de localización en vez de buscar en el mapa del dibujo es mejor (supongo que así lo llevas) usar una matriz con una estructura de 3 datos,  las cordenadas de cada punto 'x','y' y el 'valor' ( la vas completando cuando lo vas trazando).  Así no buscas en superficies vacías del mapa sino en la matriz. al encontrar un punto pasa al índice alto. El primer punto se envía al final de la matriz y se fija un puntero_tope= tamaño_matriz -1, el próximo punto localizado se intercambia con esa posición y se actualiza el puntero puntero_tope= puntero_tope -1, es claro que el bucle finalizará cuando puntero_tope=1.

p.d.: cuando el trazado describe, un área cerrada , se puede empezar arbitrariamente por cualquiera, el otro extremo será el mismo, pero con la consideración que una vez completo el camino, debe examinarse tota la matriz y (si es lo que se desea) romper la cadena justo por los 2 puntos que mas equidisten entre sí dentro de la secuencia. Esto lógicamente será opcional dependiendo de a qué vaya destinado problema.

La línea imaginaria que señalamos más arriba, puede no ser muy correcta si está muy desviada, por ejemplo si la línea de trazos describen una 'C', para estos casos puede usarse una línea imaginaria más inteligente, sumando los valores máximos y mínimos de x, la línea sería el punto proporcional entre esos límites, por ejemplo si el valor x mínimo es 40 y el máximo 120, parecería que debiera ser 80, pero no, 80 es ahora un divisor, repasamos y sumamos todos los valores que sobrepasan 80 y todos los que no llegan por ejemplo valores 100,110,107 y al otro lado 50,55 . entonces (100-80) + (110-80) + (107-80)= 77  y al otro lado (80-55) + (80-50)= 55: 77 - 55= 22 :  22/2=11:  linea va en 80 +11 (11 sería la ponderacón). Este ejemplo es referido a un caso donde los extremos tomados fueron verticalmente sea límite superior e inferior si es un camino abierto, si es un camino cerrado debería seguirse una línea redonde o una curva si forma una línea muy curva sin cerrar. Para casos más complejos hay que hacer una detección bordes y usarla como guía respecto del punto actual... trataré de ponerte un ejemplo de este tipo, pués son más útiles de lo que pueda parecer..