algoritmo di partizionamento Spazio

Question

Ho un insieme di punti che sono contenuti all'interno del rettangolo. Mi piacerebbe dividere i rettangoli in sottorettangoli basati su densità di punti (per un certo numero di sottorettangoli o densità desiderata, a seconda di quale è più facile).

Il partizionamento non deve essere esatto (quasi ogni approssimazione meglio di griglia regolare farebbe), ma l'algoritmo deve far fronte al gran numero di punti - ca. 200 milioni di persone. Il numero desiderato di sottorettangoli tuttavia è notevolmente inferiore (circa 1000).

Qualcuno sa qualsiasi algoritmo che mi può aiutare con questo compito particolare?

Answer 1

Proprio per capire il problema. Di seguito è cruda ed eseguire male, ma voglio sapere se il risultato è quello che si vuole>

Assunzione> Numero di rettangoli è ancora
Assunzione> Distribuzione Point è marcatamente 2D (non un grosso accumulo in una riga)

Procedura>
Bisett n / 2 volte in entrambi gli assi, loop da un'estremità all'altra di ogni conteggio precedentemente determinato rettangolo "passate" punti e memorizzare il numero di punti passati ad ogni iterazione. Una volta contati, bisect la selezione rettangolo dai punti contati in ciascun ciclo.

E 'questo che si vuole raggiungere?

Answer 2

Sei dopo una Kd-albero standard o albero binario spazio partizionamento, credo. (È possibile cercare su Wikipedia.)

Dal momento che si dispone di molti punti, si potrebbe desiderare di partizionare solo approssimativamente i primi livelli. In questo caso, si dovrebbe prendere un campione casuale di 200M punti - forse 200k di loro - e dividere il set di dati completo a metà del sottocampione (insieme a seconda di quale asse è più lungo). Se effettivamente scegliere i punti a caso, la probabilità che vi perderete un enorme grappolo di punti che devono essere suddiviso sarà di circa pari a zero.

Ora avete due problemi di circa 100M punti ciascuno. Dividere ogni lungo l'asse maggiore. Ripetere fino a quando non interrompere l'assunzione di sottocampioni e divisa lungo l'intero insieme di dati. Dopo dieci iterazioni ampiezza-prima ti verrà fatto.

Se hai un problema diverso - è necessario fornire segni di graduazione lungo l'asse Y e X e compilare una griglia lungo quelli nel miglior modo possibile, piuttosto che avere la decomposizione irregolare di un Kd-albero - prendere il vostro sottocampione di punti e trovare il 0/32, 1/32, ..., 32/32 percentili lungo ogni asse. Disegnare le linee della griglia lì, poi riempire la griglia risultante 1024 elemento con i punti.

Answer 3

R-tree

Answer 4

Credo che mi piacerebbe iniziare con la seguente, che è vicino a quello che @belisarius già proposto. Per eventuali ulteriori requisiti, come ad esempio preferendo rettangoli 'quasi quadrata' a 'a lungo e sottile' quelli avrete bisogno di modificare questo approccio ingenuo. Si assume, per semplicità, che i punti sono di circa distribuiti in modo casuale.

1. Dividere il rettangolo iniziale 2 con una linea parallela al lato corto del rettangolo e l'esecuzione proprio attraverso il punto mediano.
2. Contare il numero di punti in entrambe le mezze rettangoli. Se sono uguali (abbastanza) quindi passare al punto 4. In caso contrario, passare al punto 3.
3. In base alla distribuzione dei punti fra le mezze rettangoli, spostare la linea alle cose anche di nuovo. Quindi, se, per caso, il primo taglio dividere i punti 1/3, 2/3, spostare la linea di metà campo nella pesante la metà del rettangolo. Passare al punto 2. (Fare attenzione a non rimanere intrappolati qui, spostando la linea a passi sempre meno prima in una direzione, poi l'altro.)
4. Ora, passano ciascuno dei semi-rettangoli per una chiamata ricorsiva a questa funzione, nella fase 1.

Mi auguro che la proposta contorni abbastanza bene. Essa ha delle limitazioni: esso produrrà una serie di rettangoli uguali a qualche potenza di 2, in modo da regolare, se questo non è abbastanza buono. Ho si espresse in modo ricorsivo, ma è ideale per la parallelizzazione. Ogni divisa crea due compiti, ognuno dei quali si divide un rettangolo e crea più due compiti.

Se non ti piace questo approccio, forse si potrebbe iniziare con una griglia regolare con un po 'di più (10-100 forse) del numero di rettangoli che si desidera. Contare il numero di punti in ciascuno di questi piccoli rettangoli. Quindi avviare l'incollaggio i minuscoli rettangoli insieme fino alla meno-tiny rettangolo contiene (circa) il giusto numero di punti. Oppure, se soddisfa le vostre esigenze abbastanza bene, si potrebbe usare questo come un metodo di discretizzazione e integrarlo con il mio primo approccio, ma mettere solo le linee di taglio lungo i confini dei piccoli rettangoli. Questo sarebbe probabilmente molto più veloce come ci si deve solo contare i punti in ogni piccolo rettangolo di una volta.

Non ho davvero pensato al tempo di esecuzione di uno di questi; Ho una preferenza per il primo approccio 'cos I fare una buona dose di programmazione parallela e hanno una gran quantità di processori.

Answer 5

Buona domanda.

Credo che la zona è necessario indagare è "geometria computazionale" e il problema "k-partizionamento". C'è un legame che potrebbe aiutare ad iniziare qui

Si potrebbe scoprire che il problema stesso è NP-hard che significa un algoritmo buona approssimazione è il meglio che si vuole ottenere.

Answer 6

K-means o un Voronoi schema essere una buona misura per il problema che si sta tentando di risolvere?

Answer 7

Ecco assomiglia Cluster analisi .

Answer 8

quadtree lavoro?

Un quadtree è una struttura di dati ad albero in cui ogni nodo interno ha esattamente quattro bambini. Quadtree sono più spesso utilizzati per partizionare uno spazio bidimensionale suddividendolo ricorsivamente in quattro quadranti o regioni. Le regioni possono essere quadrata o rettangolare, o possono avere forme arbitrarie. Questa struttura di dati è stato nominato un quadtree da Raphael Finkel e J.L. Bentley nel 1974. Un partizionamento simile è anche conosciuto come un Q-albero. Tutte le forme di quadtree condividono alcune caratteristiche comuni:

• si decompongono spazio in cellule adattabili
• Ogni cella (o secchio) ha una capacità massima. Quando si raggiunge la capacità massima, le spaccature benna
• La struttura di directory segue la decomposizione spaziale del Quadtree