grande triangolo da un insieme di punti

Question

Eventuali duplicati:
How to find largest triangle in convex hull aside from brute force search

Ho una serie di punti casuali da cui voglio trovare il più grande triangolo per area che di verticies sono ciascuno su uno di questi punti.

Finora ho capito che le vertici del triangolo più grande si trovano solo sui punti esterni della nuvola di punti (o sullo scafo convesso), quindi ho programmato una funzione per fare proprio questo (usando la scansione Graham in tempo nlogn).

Tuttavia, è lì che sono bloccato. L'unico modo per capire come trovare il triangolo più grande da questi punti è usare la forza bruta in tempo n^3, che è comunque accettabile in un caso medio, dato che l'algoritmo dello scafo convesso di solito tira fuori la maggior parte dei punti. Tuttavia, nel peggiore dei casi in cui i punti sono su un cerchio, questo metodo fallirebbe miseramente.

Dose qualcuno conosce un algoritmo per farlo in modo più efficiente?

Nota: so che CGAL ha questo algoritmo ma non ci sono dettagli su come è stato eseguito. Non voglio usare le librerie, voglio imparare questo e programmarlo da solo (e anche permettermi di modificarlo esattamente come voglio che funzioni, proprio come la Graham Scan in cui altre implementazioni raccolgono punti collineari che non voglio).

Answer 1

In cima alla mia testa, forse si potrebbe fare qualcosa che coinvolge la griglia/suddivisione della raccolta di punti in gruppi? Forse ... separando i punti in tre gruppi (non è sicuro quale sia il modo migliore per farlo in questo caso, però), facendo qualcosa per scartare quei punti in ciascun gruppo che sono più vicini agli altri due gruppi rispetto ad altri punti in lo stesso gruppo, e quindi usando i punti rimanenti per trovare il triangolo più grande che può essere realizzato con un vertice in ciascun gruppo? Ciò renderebbe molto più semplice il caso in cui tutti i punti si trovino su un cerchio, poiché concentreresti solo sui punti che si trovano vicino al centro degli archi contenuti all'interno di ciascun gruppo, poiché sarebbero quelli in ciascun gruppo più lontano da gli altri due gruppi.

Non sono sicuro se questo ti darebbe il risultato corretto per certi triangoli/distribuzioni di punti, comunque. Potrebbero esserci situazioni in cui il triangolo risultante non è di area ottimale, perché il raggruppamento e/o la scelta del vertice non sono/non sono ottimali. Qualcosa del genere.

Ad ogni modo, quelli sono i miei pensieri sul problema. Spero di essere stato almeno in grado di darti idee su come lavorarci.

Answer 2

Ecco un pensiero su come ottenere il basso a O (n log n). Non so davvero nulla sulla geometria computazionale, quindi la contrassegnerò come wiki della comunità; sentiti libero di migliorare su questo.

Preprocesso dello scafo convesso trovando per ogni punto l'intervallo di pendenze delle linee attraverso quel punto in modo tale che l'insieme si trovi completamente su un lato della linea. Quindi inverti questa relazione: costruisci un albero ad intervalli per pendenze con punti nei nodi foglia, in modo tale che quando esegui una query con una pendenza trovi i punti in modo tale che vi sia una tangente attraverso quei punti.

Se non ci sono gruppi di tre o più punti collineari sullo scafo convesso, ci sono al massimo quattro punti per ogni pendenza (due su ciascun lato), ma in caso di punti collineari possiamo semplicemente ignorare i punti intermedi.

Ora, scorrere tutte le coppie di punti (P, Q) sullo scafo convesso. Vogliamo trovare il punto R tale che il triangolo PQR abbia l'area massima. Prendendo PQ come base del triangolo, vogliamo massimizzare l'altezza trovando R il più lontano possibile dalla linea PQ. La linea che passa per R parallela a PQ deve essere tale che tutti i punti si trovino su un lato della linea, quindi possiamo trovare un numero limitato di candidati nel tempo O (log n) usando l'albero ad intervalli precostruiti.

Per migliorare ulteriormente in pratica, esegui il branch-and-bound nell'insieme di coppie di punti: trova un limite superiore per l'altezza di qualsiasi triangolo (ad esempio la distanza massima tra due punti) e scarta qualsiasi coppia di punti la cui distanza moltiplicata per questo limite superiore è inferiore al triangolo più grande trovato finora.

Answer 3

Penso che il metodo rotating calipers possa essere applicato qui.

Answer 4

Che ne dici di eliminare un punto alla volta dallo scafo convesso? Partendo dallo scafo convesso, calcola l'area del triangolo formato da ciascuna tripla di punti adiacenti (p1p2p3, p2p3p4, ecc.). Trova il triangolo con l'area minima, quindi rilascia il centro dei tre punti che formano quel triangolo. (In altre parole, se il triangolo dell'area più piccolo è p3p4p5, rilascia P4.) Ora hai un poligono convesso con punti N-1. Ripeti la stessa procedura finché non ti rimangono tre punti. Questo dovrebbe richiedere O (N^2) tempo.

Non sarei affatto sorpreso se c'è qualche caso patologico in cui questo non funziona, ma mi aspetto che funzioni per la maggior parte dei casi. (In altre parole, non l'ho dimostrato, e non ho alcuna fonte da citare.)

Answer 5

Non so se questo aiuto, ma se si sceglie due punti dallo scafo convesso e ruotare tutti i punti dello scafo in modo che la linea di collegamento dei due punti sia parallela all'asse x, o il punto con il massimo o quello con la coordinata y minima forma il triangolo con l'area più grande insieme ai due punti scelti per primi.

Ovviamente dopo aver testato un punto per tutte le possibili linee di base, è possibile rimuoverlo dall'elenco.