Programación Específica > Diseño de Algoritmos
Interpolación de valores
m0skit0:
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)
Nebire:
Tengo la impresión de que tu array parte de una imagen y que de alguna manera tratas de analizarla, traspasando los resultados al array que muestras.
Según veo el array no está ordenado. Supongo que los valores de cada casilla corresponden a una tabla inamovible y fija para un determinado array.
Lo que no alcanzo a comprender es que quieres decir exactamente con 'para figuras mas complejas no es capaz de seguir el orden natural de las figuras' porque según veo si el array tiene valores en las casillas y no están ordenados de mayor a menor, obviamente al unir puntos saltará entre casillas distantes entre sí en vez de a una adhyacente o a otro punto sobre sí misma (que creo que es lo que finalmente pretendes) Si el array estuviera ordenado te sugeriría una búsqueda binaria mejor sobre un array unidmensional y luego estraer fila y columna de la posición absoluta en aquel array. fila= index 10 : columna= index mod 10. ganarías velocidad de cálculo pero ignoro si estás limitado al mapa tal cual sin ordenar.
Si especificas claramente esto: seguir el orden natural de las figuras es posible que pueda indicarte un algoritmo..
p.d.: Puedes mostrar los números que aparecen en el 2º gráfico sin las líneas....ese que indicas como malo ???? de repente intuyo que pretendes trazar 'líneas de nivel' basados en la intensidad de la luminancia del mapa...
aTx:
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
Nebire:
En vez de dar a editar a este le di sin darme cuenta a responder, el mensaje sea ha repetido y no deja eleiminarlo, por tanto vacío este... y lo traslado a aquel.
Nebire:
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.
Navegación
[#] Página Siguiente
[*] Página Anterior
Ir a la versión completa