Cómo encontrar el píxel que está más alejado de otro en el mismo grupo de píxeles

Question

Por "Grupo" me refiero a un conjunto de píxeles para que cada píxel tenga al menos un píxel adyacente en el mismo conjunto, el dibujo muestra un ejemplo de Un grupo.

me gustaría encontrar el píxel que está teniendo la mayor distancia de línea recta desde un píxel designado (por ejemplo, el píxel verde). Y la línea recta que conecta los dos píxeles (la línea roja) no debe salir del grupo.

Mi solución es recorrer los grados y simular el progreso de las líneas a partir del píxel verde con el grado y ver qué línea recorrió la distancia más lejana.

longestDist = 0 
bestDegree = -1 
farthestX = -1 
farthestY = -1 
FOR EACH degree from 0 to 360 
    dx=longestDist * cos(degree); 
    dy=longestDist * sin(degree); 
    IF Point(x+dx , y+dy) does not belong to the group 
     Continue with next degree 
     //Because it must not be the longest line, so skip it 
    END IF 
    (farthestX , farthestY) = simulate(x,y,degree) 
    d = findDistance(x , y , farthestX , farthestY) 
    IF d > longestDist 
     longestDist = d 
     bestDegree = degree 
    END IF 
END FOR 

Obviamente no es el mejor algoritmo. Por lo tanto, estoy pidiendo ayuda aquí.

Gracias y lo siento por mi pobre inglés.

Answer 1

Primero, tenga en cuenta que la discretización de ángulo en su algoritmo puede depender del tamaño de la cuadrícula. Si el paso es demasiado grande, puede perder ciertas celdas; si es demasiado pequeño, terminará visitando la misma celda una y otra vez.

Le sugiero que enumere las celdas de la región y pruebe la condición para cada una individualmente. La enumeración se puede hacer usando la búsqueda de ancho primero o profundidad primero (creo que esto último sería preferible, ya que permitirá establecer un límite inferior rápidamente y hacer una poda).

Se puede mantener el punto X más alejado encontrado hasta el momento y para cada nuevo punto en la región, verificar si (a) el punto está más alejado que el encontrado hasta ahora y (b) está conectado al origen línea recta que pasa a través de las celdas de la región solamente. Si se cumplen ambas condiciones, actualice la X, de lo contrario, continúe con la búsqueda. Si la condición (a) no se cumple, la condición (b) no tiene que verificarse.

La complejidad de esta solución sería O(N*M), donde N es el número de células en la región y M es la dimensión más grande de la región (max(width,height)). Si el rendimiento es esencial, se pueden aplicar heurísticas más sofisticadas, pero para una cuadrícula de tamaño razonable esto debería funcionar bien.

Answer 2

Buscar píxel, no para pendiente. Pseudocódigo.

bestLength = 0 
for each pixel in pixels 
    currentLength = findDistance(x, y, pixel.x, pixel.y) 
    if currentLength > bestLength 
    if goodLine(x, y, pixel.x, pixel.y) 
     bestLength = currentLength 
     bestX = pixel.x 
     bestY = pixel.y 
    end 
    end 
end 

Es posible que desee ordenar los píxeles que descienden por | dx | + | dy | antes de que.

Answer 3

No trabajaría con ángulos. Pero estoy bastante seguro de que la distancia más grande siempre estará entre dos píxeles en el borde del conjunto, así haré un seguimiento del contorno: desde cualquier píxel del conjunto, vaya en cualquier dirección hasta llegar al borde del conjunto. Luego, mueva (couter) en el sentido de las agujas del reloj a lo largo del borde. Haga esto con cualquier píxel como punto de partida y podrá encontrar la distancia más grande. Todavía es bastante codicioso, pero pensé que podría darte un punto de partida alternativo para mejorar.

Editar: Lo que me viene a la mente: Cuando tienes un píxel de inicio s y el píxel final e. En la primera iteración usando s, el e correspondiente será adyacente (el siguiente a lo largo del borde en el sentido de las agujas del reloj).A medida que itera a lo largo del borde, puede ocurrir que no haya una línea recta a través del conjunto entre s y e. En ese caso, la línea llegará a otra parte del set-edge (el píxel p). Puede seguir iteración del borde en ese píxel (e = p)

Edit2: Y si se golpea un p usted sabrá que no puede haber dejado de distancia entre s y e por lo que en la próxima iteración de s puede omitir esa parte entera del borde (entre s y p) y comienza de nuevo en p.

Edit3: Utilice el método anterior para buscar el primero p. Tome ese p como siguiente s y continúe. Repita hasta llegar a su primer p nuevamente. La distancia máxima estará entre dos de esos p a menos que el borde del conjunto sea convexo, en cuyo caso no encontrará un p.

responsabilidad: Este no se ha probado y son sólo ideas de la parte superior de la cabeza, no se han hecho dibujos para corroborar mis reclamos y todo lo que podrían estar equivocados (es decir, pensar en ello por sí mismo antes de implementarlo; D)

Answer 4

Utilice una técnica de doble estructura:

• uno que contiene los píxeles según el ángulo.
• El segundo clasificado por distancia (para un acceso rápido, este también debe contener "punteros" para la primera estructura de datos).

Camine por el ángulo ordenado, y compruebe cada píxel que la línea se encuentra dentro de la región. Algunos píxeles tendrán el mismo ángulo, por lo que puede caminar desde el origen a lo largo de la línea y seguir hasta salir de la región. Puede eliminar todos los píxeles que están más allá de ese punto. Además, si la distancia máxima aumenta, elimine todos los píxeles que tienen una distancia más corta.

Answer 5

Trate su región como un polígono en lugar de una colección de píxeles. A partir de esto, puede obtener una lista de segmentos de línea (los bordes de su polígono).

Dibuja una línea desde el píxel de inicio a cada píxel que estás verificando. La línea más larga que no se cruza con ninguno de los segmentos de línea de su polígono indica su píxel más distante al que se puede acceder mediante una línea recta desde su píxel.

Hay varias optimizaciones que puede realizar en este y en algunos casos de bordes para verificar, pero avíseme si entiende la idea antes de publicarla ... en particular, ¿entiende lo que quiero decir al tratar como un polígono en lugar de una colección de píxeles?

Para agregar, este enfoque será mucho más rápido que cualquier enfoque o enfoque basado en ángulos que requiera "andar" para todas las colecciones de píxeles menos las más pequeñas. Puede optimizar aún más porque su problema es equivalente a encontrar el punto final más distante de un borde de polígono que se puede alcanzar a través de una línea recta no seintersectada desde su punto de inicio. Esto se puede hacer en O (N^2), donde N es el número de aristas. Tenga en cuenta que N será mucho más pequeño que el número de píxeles, y muchos de los algoritmos propuestos que usan ángulos o iteraciones de píxeles dependerán del número de píxeles.