algoritmo heightmap generazione?

Question

Stavo guardando in giro per internet e non sono riuscito a trovare un algoritmo perfetto per questo particolare problema:

Il nostro cliente ha un insieme di punti e dati di peso insieme ad ogni punto come può essere dimostrato da questa immagine:

punti ponderati http://chakrit.net/files/stackoverflow/so_heightmap_points.png

Di cui, abbiamo un programma GIS che potrebbe generare un "heightmap" o una sorta di dati del terreno da questi punti ed i loro valori di peso, ma come abbiamo vicino a un migliaio di punti di dati e che questi cambierà nel corso del tempo, abbiamo vorrebbe creare i nostri propri strumenti per auto-generare questi heightmaps.

Finora, ho cercato di calcolare il peso per ogni pixel dalla sua distanza al punto dati più vicino con Sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2) e applicando il peso e il fattore distanza per il colore del punto di dati per produrre la sfumatura di colore risultante per quel particolare pixel:

heightmap risultato http://chakrit.net/files/stackoverflow/so_heightmap_result.png

Si può vedere che ci sono ancora problemi con certa configurazione di punti dati e l'algoritmo a volte produrre un'immagine piuttosto poligonale quando c'è un sacco di punti di dati. Il risultato ideale dovrebbe apparire più come puntini di sospensione e meno come un poligono.

Ecco un immagine di esempio da voci di Wikipedia salita pendenza che dimostra il risultato che voglio:

montagne http://chakrit.net/files/stackoverflow/so_gradient_descent.png

L'algoritmo di salita pendenza non è di mio interesse. Quello che mi interessa; è l'algoritmo per calcolare la funzione originale in quella foto, in primo luogo, a condizione punti di dati con i pesi.

Non ho preso nessuna classe in matematica topologici, ma posso fare qualche calcolo. Credo di mancare qualcosa e sto piuttosto perso in che cosa devo scrivere dentro quella scatola di ricerca di Google.

Ho bisogno di alcune indicazioni.

Grazie!

Answer 1

Quello che state cercando è l'interpolazione di superficie.

Alcuni prodotti esistono per fare questo (ecco uno )

Il risultante funzione / spline / altro costrutto matematico può essere interrogato con la risoluzione necessaria ad alimentare la mappa delle altezze.

Il tuo funzione di interpolazione

Sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2) 

E 'simile a Inverse Distance Weighted metodi tranne te si applica un filtro arbitrario e scartando molti altri punti di dati.

La maggior parte di queste tecniche si basano su un numero ragionevole di campioni e 'terrain-like' comportamento alla base i valori.

Io suggerisco di usare il peso del campione in altezza e cercando il metodo semplice di Shepard nel secondo collegamento (Non filtrare i pixel per cominciare) moltiplicando la quota di un contributo punti di esempio per il valore complessivo di altezza in un punto di interpolazione si può mescolare i colori dei campioni in quei rapporti per colorare anche il punto. Utilizzare l'intensità (grosso modo la scala di grigi a semplice spazio RGB) per visualizzare l'altezza o aggiungere linee di contorno di nero come l'immagine di esempio fa.

Answer 2

Il problema non è così facile come sembra sulla superficie. Il tuo problema è che entrambe le parti del confine di due regioni devono avere la stessa altezza, vale a dire, l'altezza in un dato pixel è determinata da più di un vicino più prossimo.

Se ho ben capito, è necessario almeno due algoritmi (e un terzo pezzo di gergo).

Per farlo correttamente, è necessario rompere l'aereo in una Voronoi tesselation .

Probabilmente si sta andando a voler utilizzare un kd-tree per aiutarti trovare il vicino più prossimo. Invece di prendere O (n ^ 2), questo porterà verso il basso per O (n log (n)) (il vantaggio è che la vostra fase di generazione regione di Voronoi sarà abbastanza veloce in fase di sviluppo per lavorare sulla fase di calcolo altezza).

Ora che avete una mappa 2-D indicizzare ogni punto al suo vicino più prossimo io, è necessario attraversare ogni x, y punto sulla mappa e calcolare la sua altezza.

Per fare che per un dato punto x, y, prima afferrare suo vicino più prossimo ie bastone che in un elenco, quindi raccogliere tutte le regioni contigue sul diagramma di Voronoi. Un modo semplice è quello di utilizzare per trovare tutti i punti della regione, poi guardarsi intorno il confine e raccogliere le altre identità.

Con questo elenco di tutti i vicini più prossimi, ora avete un colpo a interpolare correttamente! (Vedi altre risposte relative ai regimi di interpolazione).

Answer 3

Hai chiesto informazioni su algoritmi per 2-D interpolazione dei dati irregolari, che è una zona abbastanza complessa. Dal momento che si dice di avere ArcGIS, I caldamente di interpolare automaticamente in ArcGIS utilizzando la sua built-in caratteristiche per calcoli automatici. Sono sicuro che sarà molto più facile di scrivere il proprio algoritmo di interpolazione. Ho fatto qualche automatismo di ArcGIS, è abbastanza semplice.

Se si scrive il proprio codice di interpolazione - vi consiglio di non - la prima cosa è scegliere l'algoritmo appropriato in quanto vi sono diversi ognuno con le proprie vantaggi e svantaggi. Ecco alcuni consigli cribbed dalla Guida per l'ottimo strumento di interpolazione Surfer (che BTW possono essere automatizzati anche abbastanza facilmente). Ci sono più algoritmi, questi sono solo quelli che ho provato.

• Kriging è uno dei metodi più flessibili ed è utile per gridding quasi qualsiasi tipo di set di dati. Con la maggior parte insiemi di dati, Kriging con il variogramma lineare di default è molto efficace. In generale, ci sarebbe il più delle volte consigliare questo metodo. Kriging è il metodo predefinito gridding perché genera una buona mappa per la maggior parte insiemi di dati. Per i set di dati più grandi, Kriging può essere piuttosto lento. Kriging può estrapolare i valori della griglia al di là di gamma Z dei vostri dati.
• Inversa distanza ponderazione è veloce, ma ha la tendenza a generare "occhio di bue" modelli di profili concentrici intorno i punti dati. Inverse distanza di una potenza non estrapolare valori Z al di là della gamma di dati. Un semplice algoritmo distanza ponderazione inversa è facile da implementare, ma sarà slowish.
• Triangolazione con interpolazione lineare è veloce. Quando si utilizzano insiemi di dati di piccole dimensioni, Triangolazione con interpolazione lineare genera facce triangolari distinti tra punti di dati. Triangolazione con interpolazione lineare non estrapolare valori Z al di là della gamma di dati.
• Metodo di Shephard è simile a Inverse Distance ad un potere, ma non tende a generare "occhio di bue" modelli, soprattutto quando viene utilizzato un fattore di livellamento. Metodo di Shepard può estrapolare i valori oltre la portata Z dei vostri dati.

Per implementare gli algoritmi: si può provare Googling, o seguire i collegamenti in alcune delle altre risposte. Ci sono alcuni pacchetti GIS open-source che includono l'interpolazione, quindi forse è possibile estrarre gli algoritmi da loro se ti piace speleologia attraverso C ++. O questo libro da David Watson è apparentemente considerato un classico, anche se è una lettura difficile e il codice di esempio sono gli spaghetti di base !! Ma, da quello che ho sentito, è il migliore disponibile. Se qualcun altro su Stack Overflow conosce meglio, si prega di fare correggetemi come non riesco a credere che sia.

Answer 4

Kriging è uno dei metodi pesante per fare questo, in particolare nel campo del GIS . Ha diverse belle proprietà matematiche - il rovescio della medaglia è che può essere lento a seconda della variogramma .

Se si desidera qualcosa di più semplice, ci sono molte routine di interpolazione, che gestiscono questo abbastanza bene. Se è possibile ottenere ahold di una copia di Numerical Recipes , capitolo 3 è dedicato a spiegare molte varianti per interpolazione, e comprende esempi di codice e descrizioni delle loro proprietà funzionali.

Answer 5

  

è l'algoritmo per calcolare il   funzione originale in quella foto in   Innanzitutto, forniti punti dati   con i pesi.

E 'possibile. Se si inizia con i singoli punti si finisce sempre con i cerchi, ma se il peso datapoints e tenerne conto si può schiacciare i cerchi in ovali come nell'immagine ..

Il motivo per cui stai finendo con poligoni è che si sta utilizzando una funzione discreta nel calcolo -. Prima a trovare il colore più vicino, allora si determina il colore

Si dovrebbe invece esaminare algoritmi gradiente che assegnano un colore per un punto sulla base della distanza e del peso dalle tre datapoints che racchiudono quel punto in un triangolo.

algoritmo del gradiente

Dipende da quello che si sta cercando di visualizzare. Un algoritmo semplice potrebbe essere:

Per ogni pixel:

• Trova i tre punti che formano il più piccolo triangolo che circondano questo pixel

• Imposta questo punto per il colore (sistema di colore HSV) che risente sia il peso e la distanza ad ogni datapoint:

  pixel.color = datapoint[1].weight * distance(pixel, datapoint[1]) * datapoint[1].color + datapoint[2].weight * distance(pixel, datapoint[2]) * datapoint[2].color + datapoint[3].weight * distance(pixel, datapoint[3]) * datapoint[3].color

sto usando + qui, ma è necessario per determinare l'algoritmo di 'media' adatto per la vostra applicazione.

-Adam

Answer 6

interpolazione superficiale sembra essere un problema difficile e matematico. Un altro, il modo più economico per farlo è:

For each pixel:
For each point:
pixel.addWeight(weight(point, pixel))

def addWeight(w):
totalweight += w
numberofweights += 1
weight = totalweight / numberofweights

funzione peso Esempio:

def weight(point, pixel):
return point.weight * 1/(1 + sqrt((point.x - pixel.x)^2 + (point.y - pixel.y)^2))

E 'un bel approccio forza bruta, ma è semplice.

Answer 7

ho realizzato qualcosa di simile in Winamp AVS qualche tempo fa. Esso utilizza un "metaballs" approccio tipo di calcolare l'inverso distanza al quadrato (per evitare la sqrt velocità) di ciascun punto di dati, tappatura (ad esempio a 1,0), e prendendo una somma di tali distanze per ciascun punto della griglia 2D. Questo vi darà una mappa a colori / altezza senza problemi diversi.

Se si vuole guardare il codice, la sua nel preset "glowy" dal mio J10 AVS imballare .

EDIT: Basta guardarlo ho aggiunto qualche altro jazz per farlo sembrare più bella, la parte che è più importante è:

d1=s/(sqr(px1-rx)+sqr(py1-ry));
d2=s/(sqr(px2-rx)+sqr(py2-ry));
d3=s/(sqr(px3-rx)+sqr(py3-ry));
d4=s/(sqr(px4-rx)+sqr(py4-ry));
d5=s/(sqr(px5-rx)+sqr(py5-ry));
d6=s/(sqr(px6-rx)+sqr(py6-ry));
d=d1+d2+d3+d4+d5+d6;

Il che porta la somma per i 6 punti. Tutto il resto fatto per i valori di uscita rosso, verde e blu è quello di far sembrare più bella. 6 punti non è molto, ma tenere a mente che stavo cercando di fare questo percorso in tempo reale su una griglia 320x200 su una macchina 400MHz quando era nuovo (che lo fa a ~ 20fps). :)

Sostituire i = rosso, verde e blu = = ... le linee con rosso = d; ecc ... per capire cosa intendo. Tutta la grazia va via e si sono lasciati con un'immagine in scala di grigi di intoppi vari blob intorno ai punti di dati.

Un altro Edit: Ho dimenticato di dire "s" è il peso condivisa per tutti i punti, cambiandolo per ciascuno dà pesi individuale ad ogni punto, per esempio d1 = 2 / (...) e d2 = 1 / (...) darebbe D1 doppio di altezza al centro di D2. Si potrebbe anche voler coronare l'espressione in fondo con qualcosa di simile d1 = 2 / max (..., 1,0) per lisciare fuori le cime dei punti in modo che essi non picco all'infinito nel mezzo. :)

Ci scusiamo per la confusione della risposta ... ho pensato distacco l'esempio di codice sarebbe stato abbastanza buono, ma in materia di ispezione mio codice è confusa e difficile da leggere. : (

Answer 8

So che questo è piuttosto una vecchia questione, ma mi sono imbattuto in esso durante il tentativo di risolvere un problema simile.

C'è un progetto open source chiamato Surfit che implementa esattamente questo tipo di funzionalità.

Answer 9

Siete alla ricerca di qualcosa che chiamate Blender " metaballs " ( Wikipedia articolo con collegamenti , esempio ). Pensate in questo modo:

I tuoi oggetti sono coni, che sporgono dal terreno. Sono tutti parabole e il peso indica di quanto si attaccano fuori dalla terra. In alternativa, renderli tutti la stessa altezza e regolare la "piattezza" della parabola di conseguenza, quindi un grande peso rende il cono molto ampie mentre un basso peso rende tagliente. Magari tutti e due in una certa misura.

Vi suggerisco di implementare questo e vedere come appare.

Successivamente, è necessario per appendere un panno o un foglio di gomma sul risultato. Il panno si estenderà da una certa quantità e in genere pendere causa della gravità. I coni continuate così.

Finché si è vicino al centro di un cono, la coordinata Z è solo la posizione sulla superficie del cono. Come si lascia il centro del cono, la gravità inizia a tirare verso il basso e l'influenza di altri coni cresce.