Trovare un rettangolo allineato agli assi all'interno di un poligono

Question

Sto cercando un buon algoritmo per trovare un rettangolo allineato agli assi all'interno di un poligono (non necessariamente convesso). Un rettangolo massimale sarebbe bello, ma non è necessario - qualsiasi algoritmo in grado di trovare un rettangolo "abbastanza buono" andrebbe bene.

Il poligono può anche presentare fori, ma qualsiasi suggerimento per algoritmi che funzionano solo per poligoni convessi o semplici potrebbe essere utile.

Nella mia implementazione, il test di intersezione dei lati è abbastanza economico, ma i test "punto in poligono" sono costosi, quindi idealmente dovrebbe essere ridotto al minimo.

Answer 1

Solo per riferimento, finora tutto ciò che ho è forza bruta: crea una griglia, e per i punti sulla griglia, se sono all'interno del poligono, crea una serie di rettangoli espandendo ogni angolo o lato a turno fino a quando colpisce un lato Quindi scegli il più grande.

L'ottimizzazione più semplice (e molto efficace) consiste nel verificare se un punto di griglia si trova nel poligono dopo aver verificato che non è contenuto in uno dei rettangoli già costruiti, poiché il controllo del punto nel rettangolo è sfolgorante veloce.

Per ovvie ragioni, questo è abbastanza lento e impreciso, per non parlare poco elegante :)

Answer 2

http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/
ha un algoritmo per convessa, i riferimenti potrebbero essere la pena dare un'occhiata.
non so se potrebbe essere esteso a non convesso però.

Answer 3

Una soluzione è dividere il poligono concavo in segmenti convessi, quindi utilizzare il collegamento cobbal.

Dal momento che in realtà hai due diversi problemi fondamentali, hai considerato altre alternative al problema del hit test, ad esempio l'utilizzo di un albero BSP? Puoi accelerare ulteriormente posizionando una griglia sul poligono e costruendo un albero BSP per ogni quadrato della griglia. O un albero kd con al massimo un bordo in ogni foglia?

Edit: io ellaborate sul kd-tree (per noia, anche se potrebbe essere di qualche utilità a nessuno):

kd-alberi hanno le seguenti proprietà:

1. Sono binari
2. Ogni nodo non fogliare divide lo spazio lungo un piano perpendicolare a un asse, un lato per bambino. Per esempio. la radice divide lo spazio in x < x0 e x> = x0
3. I livelli degli alberi, a turno, si dividono lungo diversi assi, ad es. livello 0 (root) divide perpendicolare a X, Livello 1 -> Y, ecc

Per utilizzare questo per il poligono hit rilevamento, costruire l'albero come segue:

1. selezionamento un vertice per dividere lungo. (Preferibilmente da qualche parte vicino al centro per un albero equilibrato).
2. Dividi altri vertici in due gruppi, uno per ciascun lato della divisione. Il vertice sopra non va in nessuno dei due set.
3. Posizionare i bordi anche nei set. Qualsiasi arco che interseca la linea divisa va in entrambi i gruppi.
4. Costruire i bambini in modo ricorsivo dai gruppi precedenti.

Se il vertice diviso viene scelto in modo appropriato, l'albero deve avere profondità vicino al log (N), dove N è il numero di vertici. Ogni nodo foglia avrà al massimo un bordo che lo attraversa. Per eseguire il rilevamento dei colpi:

1. Trova la foglia in cui cade il punto.
2. Se c'è un bordo nella foglia, confrontare il punto ad esso. In caso contrario, dovrebbe essere ovvio se il punto è all'interno o all'esterno (conservare queste informazioni in tali foglie quando si costruisce l'albero).

Answer 4

E il ritaglio dell'orecchio? È possibile trovare il rettangolo allineato agli assi massimo in ciascun triangolo. Quindi potresti provare ad unire triangoli e ricalcolare i tuoi rettangoli.