Disegno incrementale e parziale dei grandi grafici

Question

Disegno incrementale e parziale dei grandi grafici

#1 da (2 voti)
#2 da (0 voti)

4

Ho il seguente problema: sto sviluppando un software per la visualizzazione dei dati in cui ottengo una struttura grafica e la rappresento nello spazio 3D. Finora, ho utilizzato algoritmi basati sulla forza per disegnare grafici e ha funzionato bene, fino a quando non ho avuto la necessità che il mio software rappresentasse un numero molto elevato di vertici e spigoli (pochi milioni). Sarebbe molto poco pratico tenere tutti quelli in memoria, quindi sto cercando un algoritmo che mi consenta di trasmettere piccole porzioni di grafico mentre "cammino" nello spazio.

Tuttavia, il problema principale è mostrare e riposizionare dinamicamente i vertici, poiché non ho posizioni già predefinite e devo calcolarli.

Puoi indicarmi alcuni algoritmi per il disegno incrementale e lo streaming del grafico?

Grazie in anticipo!

data-structures graphics

posta Leon Wickliff 08.08.2011 - 15:59

fonte

2 risposte

Leggi altre domande sui tag data-structures graphics

Quale applicazione di Q & A adatta può integrarsi con un portale Java? Organizzazione di classi con molte proprietà che devono essere ripetute

score 2 · Answer 1

Vorrei fare alcuni calcoli per mostrare effettivamente che è impossibile tenere il grafico nella memoria che hai. Come stima rapida, se si dispone di 25 milioni di vertici e ognuno contiene 12 pollici (32 byte), si parla di circa 1 GB di memoria. Quello che stai facendo dovrebbe essere fattibile su un tipico desktop da 4 GB.

Ciò che sarà più problematico è il tempo di esecuzione. Se stai cercando di calcolare una forza tra ogni coppia di vertici, questo è un algoritmo N ^ 2. Quindi se si aumenta il numero di vertici da mille a un milione (un fattore di 1000), il tempo di esecuzione aumenta di un fattore di un milione. Questo potrebbe rendere la soluzione attuale non fattibile. Esistono altri algoritmi di calcolo delle forze ottimizzati per un numero elevato di vertici che potresti prendere in considerazione.

score 0 · Answer 2

li stai tenendo in memoria o calcolandoli mentre vai? In quest'ultimo caso, basta eliminare i vecchi vertici in quanto sono necessari nuovi.

L'algoritmo tradizionale per disegnare un sottoinsieme di un grafico è un grafico di scena, usato molto nella grafica del computer per visualizzare solo le parti visibili di un modello 3d, fondamentalmente ritaglia parti del modello che non sono visibili area e li ignora.

Non riesco a pensare a nient'altro che potrebbe essere rilevante senza ulteriori dettagli.