Come rilevare le estrusioni sottili da un poligono?

Question

Come rilevare le estrusioni sottili da un poligono?

#1 da (1 voti)
#2 da (0 voti)

1

Voglio creare un poligono minimale che si avvicini al limite di una forma arbitraria (semi-casuale).

Per "minimo" intendo, "il minor numero possibile di punti".

La forma originale (da limitare) è in formato bitmap, con una colorazione semplice.

La complicazione è che la forma può avere linee (cioè lunghe aree / forme sottili) che escono da essa. Quale algoritmo puoi suggerire di utilizzare per rilevare queste righe?

Ad esempio, voglio rilevare linee che non siano più larghe di cinque pixel; le linee potrebbero essere in diagonale o curve.

Preferirei un algoritmo, che posso implementare, piuttosto che uno strumento o una libreria di terze parti preinstallati.

Ad esempio, ecco una semplice forma di esempio (disegnata a mano con Paint):

Notarechehaunalineasemi-casualecheescedaesso.

Eccoilrisultatodell'elaborazionedellaformachehoimplementatofinora:

Ipixelrossimostranouncontornotracciatointornoallaforma
Ipixelverdisulbordorossomostranounpoligonoabbastanzaminimale,incuiilcontornocambiaforma.

Unaversioneestesaperrendereognipixelpiùvisibile:

Ipixelverdirappresentanoilpoligonochevoglio,trannechemipiacerebbetagliarelaformadellacodanellaparteinferiore(inmodocheinfondorimanesolounquadrato),perchélasualarghezzamassimalorendetropposottileperessereinteressante.

Dati questi dati, quale algoritmo rileva che c'è una forma sottile che esce dal fondo?

Re. i requisiti di prestazione, la bitmap è probabilmente dire 1000 pixel quadrati; il poligono delimitante potrebbe avere un paio di centinaia di punti in totale; e l'algoritmo viene eseguito su un PC.

algorithms geometry

posta ChrisW 15.12.2016 - 01:27

fonte

2 risposte

Leggi altre domande sui tag algorithms geometry

Generazione di un'espressione lambda ridotta in Java Devo utilizzare l'inversione di dipendenza in questo caso?

score 1 · Answer 1

Che ne pensi di questo approccio generale? (Supponendo che il punto di partenza sia il contorno nero come mostrato)

Crea una maschera con:

Riempiendo il contorno con il nero. (memorizza come scala di grigi a 8 bit)
Mettere la forma piena attraverso un filtro passa-basso (sfocatura). (Convoluzione)
Creazione di una bitmap di ogni pixel inferiore a un valore di soglia in forma sfocata.
Probabilmente la crescita del contorno viene eseguita con un margine di pochi pixel.
Mantenimento del contorno originale solo dove rientra nella maschera bitmap.

score 0 · Answer 2

L'algoritmo più semplice sta probabilmente confrontando le distanze tra i punti nella figura. Quelli che sono vicini possono essere uniti, cancellando i vettori intermedi.

Tuttavia, si corre il rischio di eliminare un'intera figura, che si potrebbe voler conservare, come oggetto separato. In questo caso, mantieni i "bastoncini sottili" come una figura separata e misura la larghezza massima in ogni riga di pixel per determinare se vuoi mantenerla. Si potrebbe dire che se la larghezza o l'altezza è inferiore al minimo, scartare la figura.