Calcolo del rettangolo con un angolo di un poligono

Question

ho la necessità di determinare il rettangolo di delimitazione di un poligono con un angolo arbitrario. Questa immagine illustra ciò che devo fare:

alt text http://kevlar.net/RotatedBoundingRectangle.png

Il rettangolo rosa è quello che mi serve per determinare a vari angoli di semplici poligoni 2D.

Tutte le soluzioni sono molto apprezzati!

Edit:

Grazie per le risposte, ho ottenuto che funziona una volta ho avuto i punti centrali corretta. Voi ragazzi siete fantastici!

Answer 1

Per avere un rettangolo con un certo angolo, ruotare il poligono viceversa da tale angolo. Quindi puoi utilizzare le coordinate min/max x/y per ottenere un semplice riquadro di delimitazione e ruotarlo dell'angolo per ottenere il risultato finale.

Dal tuo commento sembra avere problemi con ottenere il punto centrale del poligono. Il centro di un poligono dovrebbe essere la media delle somme delle coordinate di ciascun punto. Quindi, per i punti P1, ..., PN, calcolare:

xsum = p1.x + ... + pn.x; 
ysum = p1.y + ... + pn.y; 
xcenter = xsum/n; 
ycenter = ysum/n; 

per rendere questo completo, ho anche aggiungere alcune formule per la rotazione coinvolti. Per ruotare un punto (x, y) intorno ad un punto centrale (cx, cy), effettuare le seguenti operazioni:

// Translate center to (0,0) 
xt = x - cx; 
yt = y - cy; 
// Rotate by angle alpha (make sure to convert alpha to radians if needed) 
xr = xt * cos(alpha) - yt * sin(alpha); 
yr = xt * sin(alpha) + yt * cos(alpha); 
// Translate back to (cx, cy) 
result.x = xr + cx; 
result.y = yr + cx; 

Answer 2

sto interpretando la tua domanda per significare "Per un dato poligono 2D, come si fa a calcolare il posizione di un rettangolo di delimitazione per il quale l'angolo di orientamento è predeterminato? "

E lo farei ruotando il poligono contro l'angolo di orientamento, quindi utilizzare una ricerca semplice per i suoi punti massimi e minimi nelle due direzioni cardinali utilizzando qualsiasi algoritmo di ricerca appropriato per la struttura i punti del poligono sono memorizzato in. (In parole semplici, devi trovare i valori X più alti e più bassi e i valori Y più alti e più bassi.)

Quindi i minimi e i massimi definiscono il tuo rettangolo.

È possibile fare la stessa cosa senza ruotare il poligono prima, ma la ricerca di punti di minimo e massimo deve essere più sofisticato.

Answer 3

Per ottenere il rettangolo più piccolo si dovrebbe ottenere la giusta angolazione. Ciò può essere risolto da un algoritmo utilizzato nel rilevamento delle collisioni: caselle di delimitazione orientate. I passi fondamentali:

ottenere tutti i vertici cordinate
Costruire una matrice di covarianza
Trova gli autovalori
progetto tutti i vertici del autovalore spazio
Trova max e min in ogni spazio autovalore.

Per ulteriori informazioni basta google OBB "rilevamento colision"

Ps: Se hai appena proiettate tutti i vertici e trovare massimo e minimo si sta facendo AABB (asse allineato riquadro). È più facile e richiede meno sforzi computazionali, ma non garantisce la scatola minima.

Answer 4

Per ottenere un rettangolo con un'area minima che racchiude un poligono, è possibile utilizzare l'algoritmo a rotating calipers.

L'intuizione chiave è che (diversamente dall'immagine di esempio, quindi presumo che in realtà non richieda un'area minima?), Qualsiasi rettangolo minimo è collineare con almeno un bordo (il guscio convesso di) il poligono .