Autor
hola NEBIRE que tal, comento esto para preguntarte sobre la parte de las lineas azules, si mal no entendi la idea seria esta:
1) calcular el centro: diviendo la distancia horizontal /2 idem para la distancia vertical
Si, pero OJO. Esto para pasos posteriores.... para ahora mismo que vamos a detectar los picos, los cuadrantes quedan divididos, por las líneas que se cruzan delimitando el cuadrante para ese par de puntos.1) calcular el centro: diviendo la distancia horizontal /2 idem para la distancia vertical
Este cuadrante (su tamaño) varía para cada par, pero tranquilo, no examinamos todo (el área del cuadrante)...
Al crear la línea entre ambos puntos, al mismo tiempo se guardan en un array, porque esos puntos son el inicio del bucle 'x' para cada ciclo del bucle 'y' (para recorrer las filas y columnas).
El algoritmo de Bresenham, te vale muy bien, para trazar la línea, además opera con valores enteros, no con decimales... esos puntos deben guardarse, el punto x más a la derecha por cada 'y'. Es decir el tamaño del array es la altura (si hacmeos el recorrido de forma horizontal, es más cómodo así que hacerlo de forma vertical, elige el que más te convenga).
2)Luego detectar la cantidad de picos minimos, esto se haria trazando una linea y detectar cuantas veces la linea corta con la imagen, siendo impar -> entrada a img, par -> salida a la img cada vez que entre o salga de la figura sumara un contador++, luego divido /2 y obtengo los posibles picos minimos a detectar.
Exacto, te da los picos mínimos, podría haber más, pero nunca menos.3) y aqui viene mi principal duda, si no entendi mal lo que debo hacer es definir el cuadrante, cada cuadrante estara limitado por los 4 puntos que me daran 4 cuadrantes, elijo el primer cuadrante en sentido a las agujas del reloj,
Si, pero cada cuadrante queda definido por las líneas que cruzan sus líneas imaginarias (ordenada y abscisa), es decir las líneas trazadas de cada 2 puntos, ofrece un cuadrante (los 4 cuadrantes posiblemente se cortan entre ellos, no nos importa).Te adjunto una imagen de como se particiona...
si la linea toca la figura en ese cuadrante entonces yo debo tener la cantidad minima de picos y debo buscarlos en este cuadrante para luego pasar al siguiente.
Para buscar esos picos de hacer:
Si, y si no toca la figura, esa línea basta para rodear la figura en ese cuadrante.Para buscar esos picos de hacer:
Pero antes de buscar en el siguiente cuadrante, resolvemos todo el asunto de ESTE cuadrante.
Con un "scanner" horizontal, que valla aumentando filas de a 1 y en cada fila evaluara los pixeles uno por uno de izquierda a derecha, las filas hiran de arriba hacia abajo y haria un "scanner" vertical que hira sumando columnas de a 1 y en cada columna evaluara cada pixel de abajo hacia arriba, las columnas hiran de derecha a izquierda (teniendo en cuenta la img 1)
Cada pico tendra dos puntos salientes a detectar, el superior (que lo detectara el scanner horizontal, y el punto saliente que esta mas a la derecha, que lo detectara el scanner vertical).
Y la duda es: ¿como los detecto? lei lo que escribiste pero no pude encontrar por mas de que quise asimilarlo la forma de detectar los 2 puntos salientes de cada pico (superior y el de la derecha). Esta parte me genera dudas
"cada vez que una línea encuentre lo más a la derecha un contorno, en la siguientes líneas (el bucle interno anidado) empezamos en esa posición,"
entiendo la idea pero no entiendo el funcionamiento de los bucles, el externo mueve en lineas y el interno mueve en pixeles de cada linea y cuando se detecta un borde saliente superior (no se como lo detectaria) el bucle interno de pixeles va a arrancar en la siguiente linea en la posicion que detecto en la anterior no arrancara desde el comienzo.
idem para scanner vertical.
Te lo explico una vez más (pero debes tener en cuenta que lo dicho se aplica a este cuadrante, a los siguientes hay que 'desplazar' la idea... es decir es reflexivo, aplicar los cambios necesarios).Cada pico tendra dos puntos salientes a detectar, el superior (que lo detectara el scanner horizontal, y el punto saliente que esta mas a la derecha, que lo detectara el scanner vertical).
Y la duda es: ¿como los detecto? lei lo que escribiste pero no pude encontrar por mas de que quise asimilarlo la forma de detectar los 2 puntos salientes de cada pico (superior y el de la derecha). Esta parte me genera dudas
"cada vez que una línea encuentre lo más a la derecha un contorno, en la siguientes líneas (el bucle interno anidado) empezamos en esa posición,"
entiendo la idea pero no entiendo el funcionamiento de los bucles, el externo mueve en lineas y el interno mueve en pixeles de cada linea y cuando se detecta un borde saliente superior (no se como lo detectaria) el bucle interno de pixeles va a arrancar en la siguiente linea en la posicion que detecto en la anterior no arrancara desde el comienzo.
idem para scanner vertical.
Veamos, tenemos dos puntos (miremos la figura 1 de esta nueva imagen que suba, la pongo un poco más arriba). Esos dos puntos trazando sus paralelas, se cortan en un punto... que definen el cuadrante 'NorEste'. Explico siempre sobre este cuadrante...
Un poco de pseudocódigo que ayude a plantear como resolverlo...
Consta de dos bucles anidados:
p.d: He retirado el pseudocódigo, he puesto más abajo otro equivalente más optimizado... aunque era un detalle que esperaba que vieras, lo cierto es que supone bastante embrollo, así que... vas a trabajar igualmente bastante...
En realidad cada encuentro, no es pico, a menudo es solo una promesa.... si es una leve curva habrá muchos 'picos seguidos'
Mirando esta imagen te puedes hacer una idea clara, de lo que va haciendo el pseudocódigo (el recorrido del bucle interno).
Cada puntito marcado verde (el anterior que está a su izquierda), es el que se añade a "Picos".
En esta imagen (tras este párrafo) la línea azul, sería representaría los valores de dx, el recorrido del bucle horizontal que va tomando al iniciar cada línea (como está a mano alzada, no salen rectas muy rectas, pero se ve claramente el recorrido, y como cuando hay un saliente avanza del saliente y cuando la diagonal supera al saliente, tira de la diagonal... esas líneas eran:
Código:
Si (dX < LineaDiagonal(Y) ) luego dX = LineaDiagonal(Y)
Si el bucle se recorre verticalmente desde el puntoB hacia el puntoA y de izquerda a derecha... es resultado será casi idéntico y no arroja interés apreciable (salvo que con la reflexibidad lógica por los otros cuadrantes, se puedan acometer en el mismo código dos cuadrantes diferentes). En fin elige recorrerlo en horizontal o en vertical, según te acomode mejor al código, pero no hay apenas diferencias en el resultado, más abajo te pongo una imagen con el recorrido hecho de ambas maneras y verás que no hay diferencia. Las puede haber si la figura entra y sale sobre sí misma, pero lo que no falla esel resultado final de hallar los picos.)
Con la declaración de los bucles, el código y las imágenes debería quedarte claro, los pasos...
Quizás haría falta una imagen para ver como procede la criba... luego me edito, antes termino el mensaje...
Ok, Aquí la imagen que va buscando los picos salientes, esta sería la función que 'criba' los picos, y que opera justo con los puntos obtenidos...
Nota como cuando un pico es seleccionado (por su mayor ángulo), son descartados los que están más 'arriba' que él (o abajo según se mire), en la lista.
Si dos o más puntos tuvieran casualmente el mismo ángulo, se toma por bueno el que quede mas lejos (sino éste luego apuntaría al siguiente y seríans líneas rectas pasando por varios puntos que se resumen en los puntos de los extremos).
En cuatro pasos, pues solo encontró 3 puntos salientes, la imagen final traza las líneas para ver el resultado con claridad.
Código:
Array Angulos(0 a Picos.count-1) //el tamaño es el de picos
entero n = Picos.Count-1 //K-1 al inicio, pero como podemos saltarnos algunos, lo dejamos en una variable.
Salientes.Add(Picos.count-1)) //el PuntoB
Bucle para k desde Picos.Count-1 a 2 retrocediendo
// bucle para calcular el ángulo desde el punto actual al resto anteriores.
Bucle para j desde n hasta 1 retrocediendo
Angulo = CalcularAngulo(Picos(0), Picos(k), Picos(j))
Angulos (j)= Angulo //ambas lineas pueden ser solo una, se deja en dos para que quede claro que
// la función devuelve el ángulo que forman los 3 puntos en ese orden (con Picos(k) en medio).
Fin bucle
//Tomar el ángulo mayor de todos.
Bucle para j desde n-1 hasta 1 retrocediendo
Si Angulos(j) > Angulos(n) luego n = j
Fin Bucle
Salientes.Add(punto picos(n)) //
Fin bucle
Salientes.Add(Picos(0)) // El PuntoA
//Ahora puede trazarse una línea desde un punto de 'salientes' al siguiente y veremos si el trazado es correcto.
4) Una vez detectado los puntos de cada pico se trazan linea desde el punto final (o el punto de origen) hacia cada punto detectado y la linea que tenga mayor angulo sera el punto mas saliente.
Si, pero el ángulo formado entre el punto final y la línea que va de PuntoA al PuntoB (final), luego se repite desde el punto recién hallado con ángulo más saliente, el angulo será partiendo desde este al PuntoA (y a los respectivos puntos más 'hacia donde avanzamos' que quedan en la dirección opuesta de donde partimos. en este cuadrante empezamos a recorrer los picos desde el PuntoB (horariamente la aguja de las '3') y en dirección antihoraria (hasta la aguja que marca las '12'). Realmente no importa el orden en que se recorran. Si quieres reutilizar la lista previa (en vez de asignar a una nueva los válidos), empieza desde 0 hacia arriba, y eliminas los que no se quedan..Pongo otra imagen mejor, para que se vea esto... Ya está es la última imagen subida puesto más arriba.
Nota que en realidad se toma como pico (promesa) el píxel hallado blanco tras un previo hallado negro. si esto ocurre más de una vez en la misma línea (con el recorrido horizontal que hacemos), el que quede al final (el más a la derecha hallado), es el que se añade, por eso se añade al terminar el bucle... en la misma línea se va actualizando...
Esto implica que una curva, va a ofrecer muchos 'picos promesa'.... podríamos sacar una línea tangente a la curva y tomar el punto de tangencia como válido, pero no conviene que te compliques tanto, una pequeña inexactitud, no merma el resultado ni se va a notar demasiado retraso por añadir 20 puntos más que los 3 o 4 previstos inicialmente). El tiempo dependerá del tamaño de la imagen, básicamente...
Te pongo una imagen final, que muestra algunas cosas que te decía...
1 - Que no importa si eliges un recorrido horizontal a derecgha y bajando, que si eliges un recorrido vertical subiendo y a izquierda
(linea azul es bucle 'Y' y luego bucle 'X' a derecha , línea verde es bucle 'X' y dentro bucle 'Y' ascendiendo).
2 - En cyan he encerrado una zona con curva, pero luego en un dibujo más pequeño, he realizado otro apuntado por una letra 'P' en amarillo.
3 - La forma en que avanza el bucle interno. Si toca la diganonal, el bucle x comienza en ese valor, si hubo un pico antes más adelante que la diagonal, el bucle X (es decir dX) comienza ahí....
-----------
Para finalizar... podemos optimizar el bucle interno, verás:
En realidad si recorriéramos el bucle interno de derech a izquierda, nos pararíamos al encontrar el primer pixel negro, ese punto sería el que se añade y saltamos al final de la siguiente línea y retrocediendo de derecha a izquierda. A lo sumo hasta el pixel hallado en la línea anterior (dX) o el que marque la diagonal, esto no cambia. No requiere comprobar posteriores apariciones, todavez que el que está más a la derecha es el que nos interesa.
El código resultante requerirá menos comprobaciones...
Modifico el pseudocódigo, para reflejarlo, ahora verás que es bastante sencillo y despejado.
Código:
Array LineaDiagonal() <----- previamente calculada con el algoritmo de Bresenham (por ejemplo).
Entero dX= 0 // al comienzo será: PuntoSuperior.X, pero dejemos qu actúe el bucle.
Picos.Add(punto (PuntoA.Y, PuntoA.X)) //añadimos el punto inicial al comienzo (ojo, no añadirlo dos veces, si es así, empezar el bucle Y uno más adelante
// El bucle y, recorre en este cuadrante las líneas verticalmente hacia abajo
Bucle para Y desde puntoSuperior.Y hasta Punto.Derecha.Y
Si (dX < LineaDiagonal(Y) ) luego // LineaDiagonal(Y) tiene el valor de X en esa línea.
dX = LineaDiagonal(Y)
Fin si
// El bucle x es quien hace todo el trabajo de detección
Bucle para X desde PuntoDerecha.X hasta dX retrocediendo
Si (pixel(Y, X) = ColorNegro) luego //Si hay un pixel negro, es el más saliente en esta línea
// La figura era toda negra y el resto blanco, no?, o era al revés?
dX = X //en la siguiente línea el bucle terminará en dx (como máximo), y en lo que resta de alto, nunca menos de este valor..
Picos.Add(Punto (Y, dX)) // se encontró un pico se añade
salir del bucle //no hace falta seguir mirando en esta línea.
Fin si
Fin Bucle
Fin bucle
Picos.Add(Punto (PuntoB.Y,PuntoB.X)) //añadimos el punto final (ojo, no añadirlo dos veces, si es así, llegar a uno menos en el bucle Y)
PD: alguien no tendra el link de un post que hable sobre como hacer lineas en java? no me refiero al elemento graphics sino a calcular los puntos de la linea que pasa por dos puntos, lo logre hacer con trigonometria, y con funciones lineales, pero al comparar mis lineas con las del elemento graphics no son iguales tienes unas pequeñas diferencias, estare subiendo el codigo de las lineas mas tarde.
Ya te comentaba más arriba (al comienzo), el algoritmo de Bresenham, que además es muy fácil de entender y opera con enteros. Además también difiere segun el cuadrante (la dirección), lo que viene en sincronía con lo que vamos haciendo... podemos implementar 4 diferentes más simplificados uno para cada cuadrante.Esta detección (de áreas) es costosa de codificar, pero es muy precisa. Si se requiere menos precisión, puedes recurrir a otros sencillos métodos...
Si te parece bien, en otro momento te comento por encima otro método más sencillo, donde no importa tanto la exactitud de las formas, se considera similar, es adecuado por ejemplo para detectar caras, de lo que no es, coches de lo que no es, etc... es decir no se requiere una exactitud en la forma, si no una clara 'compatibilidad' de la forma. Dos rostros humanos, son similares (aunque dos personas sean muy distintas), comparados con por ejemplo una lechuga, un avión, una nube, una montaña, etc...
-------------------
p.d2.: He puesto por ahí alguna incongruencia (posibemente algo esté inexacto o tal aunque procuro asegurarme alguno se escapa, si tienes dudas por ello avisa) ... en alguna parte a los puntos de los cuadrantes los he llamado PuntoA y PuntoB y en otra PuntoSuperior y PuntoDerecha... es cosa de escribir parte ayer de madrugada y parte hoy... en vez de todo del tirón, pero sin más importancia.
En línea
