Come trovare il pixel più lontano da un altro nello stesso gruppo di pixel

Question

Per "Gruppo", intendo un insieme di pixel tale che ogni pixel abbia almeno un pixel adiacente nello stesso set, il disegno mostra un esempio di un gruppo.

desidero trovare il pixel che sta avendo la massima distanza retta da un pixel designato (per esempio, il pixel verde). E la linea retta che collega i due pixel (la linea rossa) non deve lasciare il gruppo.

La mia soluzione sta eseguendo il ciclo dei gradi e simulando l'avanzamento delle linee partendo dal pixel verde con il grado e osservando quale linea ha percorso la distanza più lontana.

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 

Ovviamente non è il miglior algoritmo. Quindi sto chiedendo aiuto qui.

Grazie e scusa per il mio povero inglese.

Answer 1

Innanzitutto, si noti che la discretizzazione dell'angolo nel proprio algoritmo può dipendere dalla dimensione della griglia. Se il passo è troppo grande, puoi perdere certe celle, se è troppo piccolo, finirai per visitare la stessa cella ancora e ancora.

Suggerisco di enumerare le celle nella regione e verificare invece le condizioni per ciascuna di esse singolarmente. L'enumerazione può essere fatta usando la ricerca in ampiezza o in profondità (penso che quest'ultima sia preferibile, dal momento che consentirà di stabilire rapidamente un limite inferiore e fare qualche potatura).

Si può mantenere il punto più lontano X trovato finora e per ogni nuovo punto nella regione, verificare se (a) il punto è più lontano di quello trovato finora e (b) è collegato all'origine da un linea retta che passa solo attraverso le celle della regione. Se entrambe le condizioni sono soddisfatte, aggiorna la X, altrimenti vai avanti con la ricerca. Se la condizione (a) non è soddisfatta, la condizione (b) non deve essere verificata.

La complessità di questa soluzione sarebbe O(N*M), dove N è il numero di cellule nella regione e M è la dimensione maggiore della regione (max(width,height)). Se la prestazione è essenziale, è possibile applicare un'euristica più sofisticata, ma per una griglia di dimensioni ragionevoli ciò dovrebbe funzionare correttamente.

Answer 2

Ricerca pixel, non per pendenza. Pseudocodice.

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 

È possibile ordinare i pixel decrescente di | dx | + | dy | prima di ciò.

Answer 3

Non vorrei lavorare con gli angoli. Ma sono abbastanza sicuro che la distanza maggiore sarà sempre tra due pixel sul bordo del set, quindi tracciare il contorno: da qualsiasi pixel del set, andare in qualsiasi direzione fino a raggiungere il bordo del set. Quindi spostare (couter) in senso orario lungo il bordo. Fallo con qualsiasi pixel come punto di partenza e sarai in grado di trovare la distanza maggiore. È ancora piuttosto avido, ma ho pensato che potrebbe darti un punto di partenza alternativo su cui migliorare.

Modifica: cosa mi è appena venuto in mente: quando hai un pixel iniziale s e il pixel finale e. Nella prima iterazione utilizzando s il corrispondente e sarà adiacente (il prossimo lungo il bordo in senso orario).Durante l'iterazione lungo il bordo del caso potrebbe verificarsi che non vi è alcuna linea retta attraverso il set tra s e e. In tal caso, la linea colpirà un'altra parte del limite (il pixel p). È possibile continuare iterazione del bordo in quel pixel (e = p)

Edit2: E se si colpisce un p saprete che non ci può essere maggiore distanza tra il s e e così nella prossima iterazione del s si può saltare tutta la parte del bordo (tra s e p) e iniziare di nuovo allo p.

Modifica3: utilizzare il metodo sopra riportato per trovare il primo p. Prendi quello p come il prossimo s e continua. Ripeti fino a quando non raggiungi il tuo primo p di nuovo. La distanza massima sarà tra due di quelli p a meno che il bordo del set non sia convesso, nel qual caso non troverai uno p.

responsabilità: questo non è testato e sono solo le idee dalla parte superiore della mia testa, disegni sono stati fatti per dimostrare le mie affermazioni e tutto potrebbe essere sbagliato (cioè pensare a voi stessi prima di implementare; D)

Answer 4

Utilizzare una doppia struttura dati:

• uno che contiene i pixel filtrate per angolazione.
• Il secondo ordinato per distanza (per l'accesso rapido, questo dovrebbe contenere anche "puntatori" per la prima struttura dati).

Camminare attraverso l'angolo ordinato uno e controllare per ogni pixel che la linea è all'interno della regione. Alcuni pixel avranno lo stesso angolo, quindi puoi camminare dall'origine lungo la linea e andare fino a quando non esci dalla regione. Puoi eliminare tutti i pixel che si trovano oltre quel punto. Inoltre, se la distanza massima è aumentata, rimuovere tutti i pixel che hanno una distanza più breve.

Answer 5

Tratta la tua regione come un poligono anziché una raccolta di pixel. Da questo è possibile ottenere un elenco di segmenti di linea (i bordi del poligono).

Disegna una linea dal tuo pixel iniziale a ogni pixel che stai controllando. La linea più lunga che non interseca nessuno dei segmenti di linea del tuo poligono indica il tuo pixel più distante raggiungibile da una linea retta dal tuo pixel.

Ci sono varie ottimizzazioni che puoi fare a questo e alcuni casi di spigoli da controllare, ma fammi sapere se hai capito l'idea prima di pubblicarle ... in particolare, capisci cosa intendo trattando come un poligono al posto di una raccolta di pixel?

Per aggiungere, questo approccio sarà significativamente più veloce di qualsiasi approccio o approccio basato sull'angolo che richiede "camminare" per tutte le raccolte di pixel, tranne le più piccole. Puoi ottimizzare ulteriormente perché il tuo problema equivale a trovare il punto finale più distante di un bordo poligonale raggiungibile tramite una linea retta non controllata dal punto iniziale. Questo può essere fatto in O (N^2), dove N è il numero di spigoli. Nota che N sarà molto più piccolo del numero di pixel, e molti degli algoritmi proposti che usano gli angoli e/o l'iterazione dei pixel dipendono invece dal numero di pixel.