[Algorithm] Trova se un punto si trova all'interno di uno scafo convesso per un insieme di punti senza calcolare lo scafo stesso



Answers

Il punto si trova all'esterno dello scafo convesso degli altri punti se e solo se la direzione di tutti i vettori da esso a quegli altri punti si trova su meno della metà di un cerchio / sfera / ipersfera attorno ad esso.

Question

Qual è il modo più semplice per verificare se un punto P si trova all'interno di uno scafo convesso formato da un insieme di punti X?

Mi piacerebbe un algoritmo che funzioni in uno spazio ad alta dimensione (ad esempio, fino a 40 dimensioni) che non calcoli esplicitamente lo scafo convesso stesso. Qualche idea?




Ho avuto lo stesso problema con 16 dimensioni. Dal momento che anche qhull non ha funzionato correttamente poiché sono stati generati troppi visi, ho sviluppato il mio approccio testando se è possibile trovare un iperpiano di separazione tra il nuovo punto ei dati di riferimento (lo chiamo "HyperHull";)) .

Il problema di trovare un iperpiano di separazione può essere trasformato in un problema di programmazione quadratica convesso (vedi: SVM ). L'ho fatto in Python usando cvxopt con meno di 170 righe di codice (incluso I / O). L'algoritmo funziona senza modifiche in nessuna dimensione, anche se esiste il problema, che quanto più alta è la dimensione tanto maggiore è il numero di punti sullo scafo (vedi: sullo scafo convesso di punti casuali in un politopo ). Poiché lo scafo non è costruito in modo esplicito ma solo controllato, sia che un punto sia all'interno o meno, l'algoritmo presenta vantaggi molto grandi in dimensioni maggiori rispetto ad esempio nello scafo veloce.

Questo algoritmo può essere "naturalmente" parallelizzato e l'accelerazione dovrebbe essere uguale al numero di processori.




Anche se il post originale era tre anni fa, forse questa risposta sarà comunque di aiuto. L'algoritmo Gilbert-Johnson-Keerthi (GJK) trova la distanza più breve tra due politopi convessi, ognuno dei quali è definito come lo scafo convesso di un insieme di generatori --- in particolare, lo stesso scafo convesso non deve essere calcolato. In un caso particolare, come viene richiesto, uno dei politopi è solo un punto. Perché non provare a utilizzare l'algoritmo GJK per calcolare la distanza tra P e lo scafo convesso dei punti X? Se quella distanza è 0, allora P è dentro X (o almeno sul suo confine). Un'implementazione GJK in Octave / Matlab, denominata ClosestPointInConvexPolytopeGJK.m, insieme al codice di supporto, è disponibile all'indirizzo http://www.99main.com/~centore/MunsellAndKubelkaMunkToolbox/MunsellAndKubelkaMunkToolbox.html . Una semplice descrizione dell'algoritmo GJK è disponibile in Sect. 2 di un articolo, all'indirizzo http://www.99main.com/~centore/ColourSciencePapers/GJKinConstrainedLeastSquares.pdf . Ho usato l'algoritmo GJK per alcuni set X molto piccoli nello spazio tridimensionale e ho avuto buoni risultati. Il modo in cui le prestazioni di GJK sono paragonabili ai metodi di programmazione lineare che altri raccomandano è incerto (anche se qualsiasi confronto sarebbe interessante). Il metodo GJK evita di calcolare lo scafo convesso, o di esprimere lo scafo in termini di disuguaglianze lineari, che potrebbero richiedere molto tempo. Spero che questa risposta aiuti.




Links