Trova tutti i punti entro una certa distanza l'uno dall'altro?

Ecco cosa farei:

1. Dividi lo spazio in un reticolo regolare di cubi. La lunghezza del lato di ogni cubo dovrebbe essere la metà della distanza minima tra i punti.
2. Per il primo punto, vedi in quale cubo si trova. Aggiungi un flag al cubo che contiene il punto per indicare che quel cubo contiene un punto di quel colore.
3. Per il prossimo punto, vedi in quale cubo si trova. Se nessuno dei cubi adiacenti è contrassegnato con un punto di quel colore, contrassegna il cubo con il colore del punto come in (2). Altrimenti, butta via il punto.
4. Se hai ancora punti non elaborati, vai al 3.

Vantaggi

I vantaggi di questo approccio sono:

1. È veloce
2. È facile da capire e implementare

Limiti

Questo algoritmo ha diverse limitazioni:

Uso di cubi

L'algoritmo eliminerà troppi punti perché utilizza cubi anziché sfere. La domanda suggerisce che questo è OK.

È un problema, tuttavia, questa limitazione può essere superata.

Un modo è quello di aggiungere le coordinate del punto alle bandiere. Quindi, quando provi i punti nel passaggio (3) e trovi che c'è già un punto in un cubo adiacente, controlla la distanza fino a quel punto prima di decidere se buttare via il punto.

Naturalmente, questo rallenterà le cose / aggiungerà complessità / aumenterà i requisiti di memoria dell'algoritmo.

Ordine dei punti di prova

Il numero di punti che ottieni dipenderà dall'ordine in cui testerai i punti. Per provarlo, immagina la situazione in cui hai solo 3 punti rossi e che i cubi in cui cadono si trovano in fila:

+-----+-----+-----+
|     |   . |     |
|.    |     |     |
|     |     |   . |
+-----+-----+-----+

In questo caso, puoi buttare via il punto nel cubo centrale o i due punti nei cubi adiacenti.

Per migliorare l'algoritmo originale, puoi usare i cubi come base per contare i punti di un dato colore che sono troppo vicini l'uno all'altro, quindi gettare via i punti che hanno il maggior numero di punti troppo vicino. Non l'ho approfondito in modo approfondito: avrei dovuto lavorare su una serie di scenari sulla carta per capire il modo migliore per farlo.

Utilizzo memoria

Un altro potenziale problema è che l'algoritmo potrebbe consumare un bel po 'di memoria.

Un primo passo sensato sarebbe quello di limitare il numero di cubi creati al minimo calcolando il cubo delimitante per tutti i punti e quindi usando solo cubi sufficienti per contenere il cubo delimitante.

Un altro miglioramento sarebbe quello di dividere il problema in regioni cubiche più grandi che contengono sottoinsiemi dell'insieme completo di punti e elaborare ciascuna di queste regioni separatamente. Naturalmente, sarà necessario prestare particolare attenzione ai confini di queste regioni.

Non so molto sugli algoritmi 3D ma poco fa mi sono imbattuto in un Ottobre . Basato su alcune letture che ho fatto, è ampiamente utilizzato nelle applicazioni 3D perché essenzialmente ti dà un modo di ordinare in ordine binario tutti i tuoi punti dati (o superfici) in 3 diverse dimensioni.

Se conosci il centro nello spazio 3D e i tuoi 50k punti sono tutti ordinati usando questa struttura dati, sembra che sia molto facile trovare tutti i cubi contenenti solo i punti che si troveranno entro un raggio.

L'approccio più semplice sarebbe un ciclo annidato, controllando la distanza per ogni coppia di punti. Questo è ovviamente il metodo meno efficiente, che probabilmente non stai cercando.

Un approccio non raro nella dinamica delle particelle, è quello di dividere il tuo dominio in scatole. Si esegue il ciclo una volta su tutte le particelle per ottenere un identificatore di particelle per la connettività della scatola. In questo modo, puoi ridurre considerevolmente il ciclo interno, se hai scelto la dimensione della casella piccola.

Tuttavia mi chiedo cosa stai cercando di fare qui. Dal momento che stai per la prima volta generando punti casuali, e dopo questo li cancelli di nuovo, incluso un po 'di colore, è un po' strano. Se generi i punti in modo più intelligente, quindi con un colore diverso per definizione, esegui delle ricerche durante la generazione della posizione dei punti. Questo ti farà risparmiare un sacco di controllo in seguito.

Inizieremo ad affrontare il problema dal requisito "i punti sono vicini" e controlliamo i colori dopo.

Alberi KD sono probabilmente la scelta migliore per te. Puoi crearne uno in O (n log n) (O (n log ^ 2 n) usando un approccio più semplice) sui tuoi punti, dopo di che puoi rispondere alle domande "dammi i punti almeno a questa distanza da questo punto" ( una query "vicini più vicini") in O (k + log n) ora, dove k è il numero di punti restituiti. È quindi possibile scorrere questi punti e verificarne i colori in O (k ^ 2) (è possibile ottenere questo valore su O (k log k) se necessario). Questo dà un tempo di esecuzione totale di O (n k log k + n log n) tempo.

Se anche i tuoi punti dati si spostano (cambiano le loro posizioni), allora octrees sono probabilmente i migliori. Gli alberi KD sono piuttosto cattivi nel gestire un mix di modifiche dei dati e query del vicinato più prossimo. Assicurati però di non colpire il caso peggiore degli ocre: assicurati di capire come funzionano e quando si rompono, poiché potresti avere punti distribuiti male per gli ocre.

Se ti senti particolarmente algoritmico, potresti persino provare a utilizzare hashing sensibile alla località , ma quanto sopra è probabilmente più facile e migliore.

Potresti anche affrontare questo problema partendo dai colori. Se è raro che due punti condividano lo stesso colore, puoi anche utilizzare un algoritmo per trovare i punti con gli stessi colori e quindi controllare le distanze tra questi punti per vedere se devono essere rimossi.

Analisi: la ricerca di duplicati basata su ordinamento fornisce un primo passo O (n log n) (possibilmente migliorabile a O (n)), quindi un passo O (nk ^ 2) per confrontare le distanze tra tutti i nodi colorati.

Se k è molto piccolo, è molto efficiente. Per k moderatamente grandi (probabilmente k > 100) potresti migliorare le prestazioni dell'ultimo passo costruendo un albero KD per quei colori con valore uguale esattamente come descritto all'inizio, riducendo il tempo di esecuzione del secondo bit a O (n + k (l + log k)) (dove l è il numero di nodi restituiti per query adiacente più vicina).

Puoi anche adattare questo approccio ai punti in movimento: costruisci un albero binario (o una hashmap se ti piace) contenente degli ocrees di punti dello stesso colore: inserendo un nuovo punto poi O (log n + log k) atteso tempo.

Posso pensare immediatamente a un'ottimizzazione.

Se attraversi lo spazio, a partire dall'angolo in basso a sinistra, da sinistra a destra, quindi in basso verso l'alto, devi solo esaminare quei punti a destra e in alto.

C'è una possibilità (qualunque sia l'algoritmo che usi!) che otterrai risultati diversi se inizi da un punto diverso.

Sembra che la famiglia di algoritmi che stai cercando siano quelli usati per analisi del cluster .

La maggior parte degli algoritmi di questa famiglia non sono esatti, poiché l'analisi del cluster viene tradizionalmente eseguita su enormi set di dati, per i quali ottenere risultati esatti è irrealizzabile.

Il problema principale che si otterrà con un approccio di clustering, è che di solito questi algoritmi non si preoccupano di un piccolo numero di outliners.

Per il tuo problema, penso che una soluzione potrebbe essere simile a questa:

1. Raggruppa la tua nuvola di punti per ottenere gruppi di punti vicini. Ottimizza questo passaggio in base ai tuoi requisiti specifici per ottenere cluster utili.
2. Utilizza un algoritmo diverso per esaminare i punti all'interno di ciascun cluster e filtrarli in base alle tue esigenze. Questo algoritmo può essere uno che a) fornisce risultati esatti e b) non è probabilmente molto efficiente, poiché deve gestire un numero di punti molto inferiore.