Te voy respondiendo con cita,s al ser un mensaje algo largo y por ello difícil de retener en memoria cada cuestión planteada...
Con respecto al centro de cada cuadrante ya me quedo bien claro como debe ser.
Al crear las lineas del punto central tomare la distancia x que hay entre ambos puntos salientes, eso me indicara que distancia recorrera como maximo el bucle interno del scanner horizontal, esto se cumple solo en la primera fila ya que la linea esta inclinada.
Exacto. de ahí la importancia de tener en un array los valores de x (más a la derecha), para dicha diagonal (la línea entre tales 2 puntos).
Fíjate además que ese array determina al mismo tiempo el máximo número de pícos salientes hallados. Esto es como máximo 1 por cada píxel en x. en definitiva... ya sabes el número menor de picos al contar cuantas veces se corta la figura con la línea y como máximo, la cantidad del ancho de x (nunca o casi nunca será este valor, pero nos ale saber que es el valor máximo de picos).
Con respecto al "scanner horizontal" lo hare desde fuera hacia dentro. Cuando encuentre un pixel negro entonces la siguiente linea llegara como maximo hasta esa posicion y agregará el pixel a un array.
Como máximo hasta esa posición...
o la línea diagonal si aparece antes de esa posición. Pero en este último caso, no se añade píxel solo se actualiza el valor límite (yo lo llamé 'dX').
Mira la última imagen que puse,. date cuenta como casi lllegando a la parte baja, se encuentra la diagonal, y todavía después encuentra algún pico...
Se puede decir que el "scanner" horizontal no me detectara el punto mas saliente de cada pico, sino que me detectara un conjunto de posibles puntos salientes, en ese conjunto de puntos esta incluido el punto saliente que estoy buscando
Si. Y luego con la siguient eparte de calcular el ángulo más saliente, identifica finalmente los correctos dejando fuera al resto de 'promesas'.
Aún así, se puede optimizar bastante... date cuenta que si en la línea se detecta un pico en x en 345, y 3 líneas más abajo en 543, la diferencia horizontal entre solo 3 líneas hace descartar la previa.... pero primero logra que funciones correctamente y luego ya te entretienes en optimizarlo. Si te hubier apuesto un pseudocódigo muy optimizado, a buen seguro sería muy farrafgoso de entender el por qué de cada cosa... tal como te lo dejé es sencillo de entender y se presta a optimizaciones aún...
teniendo en cuenta la siguiente imagen:
Esto seria el scanner horizontal en el cuadrante cuatro (anti reloj)
Por ejemplo en la imagen cada cuadrado amarillo es un punto detectado por el scanner entonces cada punto amarillo sera agregado al arraylist "posiblesPuntosSalientes"
No. Cada punto amarillo que tienes no. Solo si está más a la derecha que el punto anteriormente añadido. Es decir si tienes un punto en x=234 en Y=7, lo añades, pero no hay que añadir el x=234 para Y=8, Y=9, y=10...
De hecho al recorrerlo verticalmente (este cuadrante desde arriba hacia abajo) casi aseguramos que el bueno cuando varios en vertical son 'igual de salientes' el más prometedor será el que esté más arriba. Y digo casi para no entrar en polémica...
En tu dibujo, suponiendo que cada cuadradito fuera:
---- un píxel solo habría unos 5-6 puntos (contando el primero y el último).
---- una retícula de 5x5 píxels, seguramente haya tantos como 18 (sobre unos 30 que esería el ancho).
Se añaden siempre al comienzo, antes del bucle el PuntoA, y al final tras el bucle el PuntoB. De tal modo que si finalmente todo el tramo entre ellos estuyviera interno a la línea diagonal, solo esos 2 puntos definirían el perímetro exterior en ese cuadrante.
luego queda ver cual de todos esos puntos son los que busco (en la imagen son solo 2 puntos los que busco ya que son dos picos pero en el array de posibles puntos tendre: 14 puntos, para saber cual es el que busco entonces calculo el angulo en esos catorce puntos tomando el ultimo punto del cuadrante como punto central y el posible punto saliente que mas angulo me dé será el más saliente de todos, eso me lleva a decir tambien que los angulos que luego usare para comparar no se calcularan con cada punto saliente sino que se calculara con cada posible punto saliente, es correcto esto?...
Hago una imagen con ángulos y puntos más acentuados que permitan ver mejor los detalle y añado más comentarios que aclaren la situación. Ya están (varias, ahora las explico).
En la primera imagen, en el apartado 1. Cada 'e' (entra) y 's' (sale), cuenta los picos mínimos... 7 en total.
La línea amarilla, es la solución, 4 puntos intermedios + los 2 externos = 6 puntos delimitan ese cuadrante.
La línea cyan, deine el valor que en cada cilo tomará 'dX' al comienzo del bucle. Esta línea no son todos los puntos salientes. Las líneas verticales y horizontales (cyan), no se añadirán como 'promesas'. Tampoco (aunque en este ejemplo no sucede ninguna vez), cuando tocan la línea diagonal. esos tampoco se añaden, solo se añade aquel punto que en una línea hace el cambio de blanco a negro (o negro a blanco, según hayamos tratado la imagen) y que está en esa línea lo más a la derecha posible (para este cuadrante).
En la última imagen que subiré, he trazado la misma línea y luego he tachado los puntos que no se añadirán y luego a distancia he reasaltado (en azul) los que se irán añadiendo (las promesas).
En la siguiente imagen he trazado varias líneas fiormando ángulos (la diagonal roja va desde el PuntoA (Picos(0) al PuntoB (Picos(k) y desde éste a cada uno de los que forman el bucle 'j'. Lógicamente he abreviado, habrá muchos más puntos promesa...
En esta otra, ahora el punto K, es el que antes fue el 'j' elegido como el de mayor ángulo. Y el bucle 'j' recorre los puntos que están 'por encima de él' (encima, debajo, ya saber que depende de la forma de recorrer los bucles, la imagen ayuda aentender y fijar el caso).
Para el caso concreto, he vuelto a trazar de rojo, la línea que va desde Picos(0) a Picos(k) (el que ahora es k, el bucle externo).
Fíjate que una posible optimización es descartar todos los picos (por encima de él), que tengan ángulo inferior a 0, es decir los que queden a la izquierda de la línea roja entre él y el puntoA de origen. al caos he marcado 2 puntos (color verde), como representantes de este caso.
Ahora bien esa optimización solo lo será en función de cuantos haya, si sale más caro una cosa que otra. Pero en cualquier caso, si el ánguilo es negativo, ya ni siquiera lo comparamos, se descarta...o mejor se eliminan d ela colección, así cuando vayamos subiendo más arriba no hay que volverlos a calcular ni comparar...
En la siguiente imagen ya quedan pocos puntos promesas (serán más, yo resumo para nio poner tantas líneas que no quede claro).
Finalmente hallamos el último punto, es decir es el de origen, no pasa por poco por otro en medio.
Fíjate que tiene ángulo negativo. En cambio el ángulo resultante es 0.
Ahora una imagen que muestra otros aspectos de interés y que espero que ayude a aclararte las dudas que puedna quedarte.
Tiene 3 apartados, al 1º me refiero aquí, los otros dos son para más abajo, donde voy respondiendo, y no se hace necesario poner más imágenes independientes.
Nota como los "puntos promesa", realmente sólo son aquellos que tiran por la línea azul. De las líneas que 'caen verticalmente solo se toma como promesa el que se encuentra por primera vez, si en la siguiente línea no hay uno más a la derecha que ese anterior, no se añade.
Con las líneas horizontales pasa los mismo, solo se añade el que está más a la derecha.
Igualmente aunque estén más a la derecha que en líneas anteriores, si no cambian tocando un pixel de blanco a negro, no cuentan aunque toquen la diagonal y estén más a la derecha... porque 'acaba la línea' sin haber tocado un punto negro', luego no se añade.
Con respecto a calcular el angulo he visto en el pseudocodigo que para calcular el angulo envias tres parametros, Picos(0), Picos(k), Picos(j), por que no se envian solo dos parametros? punto central y punto del que se quiere saber el angulo?
En efecto, Picos(0) es fijo para todos... pero el ángulo se calcula con 3 puntos. Además el orden de estos es importante, si no estarías tomando otro ángulo del 'triángulo que forman los 3 puntos.
En la última imagen subida, en el apartado 3, constan 3 puntos y el ángulo que forman entre si...
Si llamas a una función, puede pasar solo el 2º y 3º puntos siempre y cuando compartas el array y por tanto la función llamada, pueda saber el valor del punto primero ( Picos(0) ).
Picos(0) : Es el punto superior que hallamos al comienzo.
Picos(k) : Es el punto desde el cual estamos tirando ángulos hasta el resto de picos.
Picos(j) : Son cada uno de los puntos que en el presente bucle interno, nos dará los ángulos entre los cuales, se debe conocer el ángulo mayor.
Hallado el punto de este bucle, este hallado pasa a ser el el siguiente ciclo el Picos(k). (en el siguiente bucle, se descartan los picos intermedios entre el k actual y el j, es decir k pasa a ser j... este bucle puede ser un while... pero no quiero condicionarte con detalles, tu busca la salida y ya si te alejas mucho yo te reoriento...
" Si dos o más puntos tuvieran casualmente el mismo ángulo, se toma por bueno el que quede mas lejos "
Supongo que sera mas lejos del punto que se toma como central para calcular los angulos en este caso el punto B.
En la última imagen en el apartado '2', pongo un ejemplo con dos casos. Hay varios picos salientes, pero están en líonea.
Es decir, los angulos: IAB, IAC, IAD e IAE, son iguales, luego sus puntos están alineados en línea recta).
Entonces el punto más alejado es IAE, ya que sería redundante dar por válido como picos a B,C,D y E.
Al decir más alejado, me refiero a la dirección en la que avance el bucle, como los picos los vamos recorriendo hacia atrás, el más 'lejano' será: E, si fuera creciente, desde E, el más lejano sería A (B,C y D serían redundantes).
He puesto el mismo caso con E, F, G, H e I , están en línea recta, todos tienen el mismo ángulo:
IEF = IFG = IGH = IHI (olvida el caso de que I esté alineado con ellos, y el ángulo sea 0...
Nota que todos los pìcos por dentro de la diagonal IA, tienen ángulo menor de 0, por eso la respuesta en ese caso sería la línea I-A.
Sobre el pseodocodigo:
si, la figura es toda negra y el fondo es blanco.
si aplico este pseudocodigo pasara lo de la imagen de arriba, cada vez que detecte pixel negro se agregara al array, pero esto no garantiza que el pixel que se agrega sea el punto saliente sino que sera un posible punto saliente y entre esas posibilidades esta el que se busca (el mas saliente de ese pico) que se detectara con su angulo mayor al de los demas (para ese pico).
Si, lo hemos comentado más arriba...
Sobre el algoritmo de Bresenham, lo busque y lo estuve viendo, algunas cosas las entiendo otras no... igual para mi suerte puede implementarlo y usarlo para hacer lineas rectas, eso queda pendiente saber como funciona al 100% ese algoritmo, una de las dudas era:
p = 2*dy - dx; Eso se puede leer como: 2 veces la distancia en el eje 'y' menos 1 vez la distancia en el eje 'x' pero no se que es eso visto del punto de vista de la matematica, que representa, que nombre tiene, que significa... etc.
Ok, mañana a ver si después de comer saco un tiempito y te doy unas explicaciones y un sencillo pseudocódigo que te ayude a entenderlo bien...
He escrito algo de codigo, el codigo resuelve el primer cuadrante de cada imagen, los cuadrantes se cuentan en sentido contrario a las agujas del reloj, lo hice asi por que asi habia comenzado a hacerlo con la idea anterior (la del scanner con lineas diagonales) y para no perder tiempo modificando algo que ya estaba hecho lo hice de esta manera
El codigo tiene algunos comentarios, se hace partiendo desde la deteccion de poligono ya que lo anterior es para convertir la img en escala de grises y sacar los bordes, pintar la img etc. Tambien se incluye la imagen (que trae 5 imagenes dentro 5 en 1) esta img se llama "a.png". Al ejecutar el programa guarda en el disco "D:/" varias imagenes, que son los pasos del programa, las que tienen mas importancia son las imagenes llamadas "PPS0.png", "PPS1.png"... en esas imagenes se ven los resultados del scanner horizontal donde cada posible punto saliente es marcado en verde, los puntos rojos son los puntos mas salientes de cada lado. Luego las imagenes que se llaman "TrazarLineaX.png"... son las imagenes que muestran los puntos mas salientes y los posibles puntos salientes pero ademas de eso tambien muestra los puntos salientes que resuelven ese cuadrante (puntos de color azul), en la imagen 4 hay un error que es por la forma en que se calculan los angulos entre dos puntos, toma una recta en el eje de absisas positivo como perteneciente al cuadrante 4 entonces eso hace que tenga angulo de 360 cuando tiene 0.
Bien, aunque lo descargué tengo pendiente mirarlo, a ver si saco tiempo y te comento.
PD: en entos dias subire una imagen que refleje una duda que tengo sobre esta forma de detectar los puntos salientes.
De acuerdo.
Piensa que se puede optimizar, pero lo interesante al principio es que lo entiendas bien y te funcione correctamente. Luego cuando ya lo tengas perfectamente claro puedes tratar de optimizarlo.
es evidente que si te pongo un pseudiocódigo muy optimizado, resultará complejo entender y no quedará claro el porqué de cada cosa... ahora mismo tal como está es muy sencillo y fácil de entender (creo yo, claro
o al menos esa es la idea
).
Mostrar Mensajes
