Sto lottando con il calcolo del rettangolo di chiusura più piccolo (arbitrariamente allineato) di un insieme di punti.Qualcuno può spiegarmi le pinze rotanti?
Sono stato in grado di calcolare lo scafo convesso utilizzando l'algoritmo di Graham.
Dove sono bloccato è il passaggio successivo. Ho pensato di usare il metodo dei calibri rotanti, ma non riesco a trovare una spiegazione adeguata dell'algoritmo.
Se si dispone dello scafo convesso, è quindi semplice un algoritmo di base. Basta attraversare ciascun bordo dello scafo convesso e ruotare i punti in modo che il bordo si trovi lungo un asse maggiore, ad esempio l'asse X. Quindi trovi un riquadro di delimitazione allineato all'asse di quei punti. Scegli quale rettangolo di selezione è il più piccolo.
Un rettangolo di allineamento allineato all'asse può essere trovato ottenendo il minimo e il massimo in ciascuna dimensione.
Se si ruota il riquadro di delimitazione della quantità opposta, ora racchiuderà i punti originali.
Per rendere questo più efficiente, si noti che gli unici punti che possono influenzare il riquadro di delimitazione sono sullo scafo convesso.
Per renderlo veramente efficiente, nota che ci sono solo quattro punti attorno allo scafo convesso che stanno toccando il riquadro di delimitazione in qualsiasi momento (questo non è strettamente vero, ma ignoralo per ora). Se si ruotano i punti quel tanto che il bordo successivo è allineato con il riquadro di delimitazione, tre di questi punti sono gli stessi e uno dei punti viene sostituito con il prossimo punto attorno allo scafo convesso. Ciò consente di creare un algoritmo lineare nel numero di punti sullo scafo convesso.
Ora ci sono casi speciali in cui due bordi sono paralleli o perpendicolari. Ciò causerà più di quattro punti per toccare il riquadro di delimitazione in qualsiasi momento, ma in realtà non ha importanza. Se hai una scelta tra quale dei due lati paralleli da usare successivamente, puoi sceglierne uno arbitrariamente.
L'unico problema con questo metodo è che è O (n^2), che potrebbe non essere adatto quando ci sono molti vertici nello scafo convesso. – mbeckish
@mbeckish: true - Ho esteso la mia risposta con un paio di ottimizzazioni. Forse pensarlo come un semplice algoritmo con ottimizzazioni renderà più facile la comprensione. –
Non è vero che ci sono solo quattro punti attorno allo scafo convesso che stanno toccando il riquadro di delimitazione in qualsiasi momento. Supponendo che i punti collineari non si verificano nello scafo convesso, il riquadro di delimitazione può toccare fino a 8 punti. Considerare lo scafo convesso '(2,0), (3,0), (4,1), (4,2), (3,3), (2,3), (1,2), (1, 1) 'con un riquadro di delimitazione allineato all'asse (o uno inclinato di 45 gradi) toccando tutti i punti. –
Controllare [questa spiegazione] (http://cgm.cs.mcgill.ca/~orm/maer.html). – mbeckish
Hai visto [il documento originale di Toussaint] (http://cgm.cs.mcgill.ca/~godfried/publications/calipers.pdf)? Le pagine 1 e 2 spiegano l'algoritmo in modo abbastanza chiaro (IMO). Notare che la numerazione delle pagine è invertita ... –