grande prefisso matrice di vertici che forma un poligono convesso

Question

In relazione al: Poligono di decomposizione - Rimozione Punti concavi a modulo Convex poligoni

Sto cercando un algoritmo per effettuare le seguenti operazioni:

L'input è una matrice di punti 2D (P ₀ ... P _N-1 ). La lunghezza N della matrice varia (3 = N <8)
Per qualsiasi M = N ci può o non può essere un poligono convesso cui vertici sono P ₀ ... P _M-1 in un certo ordine.

Nota i bordi sono coppie non necessariamente adiacenti nella matrice.

Qual è l'algoritmo più efficace per trovare il massimo M tale che esiste questo poligono convesso?

Il mio algoritmo attuale è molto inefficiente. I test con M = 3 allora M = 4, M = 5, ecc, calcolare lo scafo quindi verificare che tutti p ₀ ... P _M-1 sono vertici dello scafo , se poi non mi rompere fuori dal giro e torno M-1.

Esempio # 1: [(-2,2), (2,2), (-2,-2), (-1,1)]

comportare: 3 (perché i primi tre punti formano un triangolo ma aggiungendo P ₃ = (-1,1) renderebbe il poligono non convesso)

Esempio # 2: [(-2,2), (2,2), (-2,-2), (1,-1)]

comportare: 4 (perché un quadrilatero convesso può essere costruito da tutti i 4 punti nella matrice)

Aggiorna Esempio # 3: [(-3,3), (3,3), (2,-1), (-3,-3), (3,-3), (-2,1)]
risultato: 4.

Questo esempio dimostra il motivo per cui non è sufficiente per prendere il guscio convesso di tutti i punti forniti e trovare un prefisso che è un sottoinsieme di esso. (3,-3) non può essere parte di un poligono convesso che consiste dei primi cinque punti perché allora il precedente punto (2,-1) avrebbe più giacciono sullo scafo. Ma è (3,-3) che deve essere respinto, anche se si trova sullo scafo di tutti i sei punti e (2,-1) non lo fa.

Esempi di input non validi:

• [(-1,-1), (0,0)] (troppo pochi punti)
• [(-1,-1), (0,0), (1,1), (1, -1)] (primi tre punti sono colinear: Non mi aspetto che l'algoritmo di essere in grado di gestire questo.)

Answer 1

C'è un molto semplice O (m log m) soluzione a questo.

Dato che ci sono almeno 3 punti e il primo 3 non sono allineati:

1. Trovare un punto, P, nel triangolo delle prime 3 punti.

2. ordina i 3 punti per il loro angolo rispetto P (in senso antiorario). (Questo elenco ordinato sarà convesso)

3. Anche se non siamo alla fine della lista, trovare la posizione del punto successivo nella lista ordinata.

4. Se si inserisce il punto sarà rendere concava poligono, Goto 6. (verificabile semplicemente controllando la nuova vicina due giri e il turno corrente)

5. Inserisci il punto e goto 3.

6. Fatto.

Il caso limite principale che si deve gestire ecco quando l'inserimento è ad una delle estremità della lista, in quanto l'elenco è in realtà circolare. Un modo semplice per gestire questa situazione è per ogni punto inserirlo in suo angolo e al suo angolo + -. 2pi

Answer 2

Penso che si desidera un convesso incrementale. Ecco alcuni link:

• http://www.personal.kent.edu /~rmuhamma/Compgeometry/MyCG/ConvexHull/incrementCH.htm
• http://ww3.algorithmdesign.net/handouts/IncrementalHull.pdf
• http://www.fandm.edu/computer-science/professors-emeriti/anderson/jay-martin-anderson/research-and-development/ portale-algoritmo-visualizzazione-in-computazionale geometria / convesso-scafo-un-incrementale algoritmo

Answer 3

E 'possibile fare questo in tempo O (m lg m).

• Conservare il guscio superiore e inferiore dello scafo punti in alberi di ricerca digitati dalla coordinata X.
• Quando un nuovo punto di arrivo, trovare i segmenti di linea superiore e inferiore che coprono il suo valore X (cercare gli alberi).
• Se il nuovo punto si trova tra le due linee, allora non è sullo scafo. Rinunciare.
• In caso contrario, inserire il punto nello scafo superiore o inferiore (a seconda di quale ha il segmento di linea più vicino).
• Se inserendo la punta rivolta punti adiacenti in angoli interni, quindi non sono sullo scafo. Rinunciare.
• Deal con casi limite come nuovo più a sinistra point, punti verticali, ecc.
• Continuare fino al numero desiderato di punti vengono elaborati.

Answer 4

Che cosa succede se si tenta una sorta di ricerca binaria? Ogni volta l'intero forme prefisso un poligono convesso, raddoppiare la dimensione del prefisso. Ogni volta che non riesce, ridurre la dimensione del prefisso per metà strada tra la dimensione attuale e la dimensione precedente.