Disegnare una mappa topografica

Question

Ho lavorato a un progetto di visualizzazione per dati continui bidimensionali. È il tipo di cosa che potresti usare per studiare i dati di elevazione o i modelli di temperatura su una mappa 2D. Alla base, è davvero un modo per appiattire le 3 dimensioni in due dimensioni più il colore. Nel mio particolare campo di studio, in realtà non sto lavorando con i dati di elevazione geografica, ma è una buona metafora, quindi continuerò a seguirlo in questo post.

Ad ogni modo, a questo punto, ho un "colore continuo" renderer di cui sono molto soddisfatto:

Il gradiente è la ruota dei colori standard, in cui i pixel rossi indicano le coordinate con valori alti e i pixel viola indicano i valori bassi.

La struttura di dati sottostante utilizza alcuni algoritmi di interpolazione molto intelligenti (se lo dico io) per consentire uno zoom arbitrariamente profondo nei dettagli della mappa.

A questo punto, voglio disegnare alcune linee di contorno topografiche (usando curve di Bezier quadratiche), ma non sono stato in grado di trovare alcuna buona letteratura che descriva algoritmi efficienti per trovare quelle curve.

Per darti un'idea di ciò a cui sto pensando, ecco un'implementazione di un uomo povero (in cui il renderer usa solo un valore RGB nero ogni volta che incontra un pixel che interseca una linea di contorno):

Esistono diversi problemi con questo approccio:

• Le aree del grafico con una pendenza più ripida producono linee di topo più sottili (e spesso spezzate). Idealmente, tutte le linee top dovrebbero essere continue.

• Le aree del grafico con una pendenza più piatta producono linee di topo più ampie (e spesso intere regioni di nero, in particolare sul perimetro esterno della regione di rendering).

Quindi sto cercando un approccio di disegno vettoriale per ottenere quelle curve perfette di 1 pixel di spessore. La struttura di base dell'algoritmo dovrà includere questi passaggi:

1. Ad ogni elevazione discreta in cui desidero tracciare una linea topografica, trovare un insieme di coordinate in cui l'elevazione in corrispondenza di quella coordinata è estremamente vicina (dato un valore epsilon arbitrario) all'elevazione desiderata.

2. Elimina i punti ridondanti. Ad esempio, se tre punti si trovano in una linea perfettamente dritta, il punto centrale è ridondante, poiché può essere eliminato senza modificare la forma della curva. Allo stesso modo, con curve di Bezier, è spesso possibile eliminare alcuni punti di ancoraggio regolando la posizione dei punti di controllo adiacenti.

3. Riunisci i punti rimanenti in una sequenza, in modo tale che ogni segmento tra due punti si avvicini a una traiettoria neutrale rispetto all'altezza e tale che nessun segmento di linea attraversi mai i percorsi. Ogni sequenza di punti deve creare un poligono chiuso o intersecare il rettangolo di selezione dell'area di rendering.

4. Per ogni vertice, trovare una coppia di punti di controllo in modo tale che la curva risultante presenti un errore minimo, rispetto ai punti ridondanti eliminati nel passaggio # 2.

5. Assicurati che tutte le funzioni della topografia visibili nella scala di rendering corrente siano rappresentate da linee topografiche appropriate. Ad esempio, se i dati contengono un picco con altitudine elevata, ma con diametro estremamente piccolo, le linee di topo dovrebbero comunque essere disegnate. Le funzioni verticali dovrebbero essere ignorate solo se il loro diametro delle caratteristiche è inferiore alla granularità di rendering complessiva dell'immagine.

Ma anche sotto questi vincoli, posso ancora pensare a diverse euristiche per trovare le linee:

• Trova il punto più alto all'interno del riquadro di delimitazione del rendering. Da quel punto più alto, viaggiare in discesa lungo diverse traiettorie. Ogni volta che la linea di attraversamento attraversa una soglia di elevazione, aggiungi quel punto a un bucket specifico di elevazione. Quando la traversata raggiunge un minimo locale, cambia rotta e prosegui in salita.

• Esegue un attraversamento ad alta risoluzione lungo il rettangolo di selezione dell'area di rendering. Ad ogni soglia di elevazione (e nei punti di flesso, ovunque la pendenza inverti la direzione), aggiungere quei punti a una benna specifica per l'elevazione. Dopo aver terminato l'attraversamento del confine, inizia a tracciare verso l'interno dai punti di confine in quei secchi.

• Effettua la scansione dell'intera regione di rendering, eseguendo una misurazione di elevazione a intervalli regolari sparsi. Per ogni misurazione, utilizzare la sua vicinanza a una soglia di elevazione come meccanismo per decidere se effettuare o meno una misurazione interpolata dei suoi vicini. L'uso di questa tecnica fornirebbe migliori garanzie di copertura nell'intera area di rendering, ma sarebbe difficile riunire i punti risultanti in un ordine ragionevole per costruire percorsi.

Quindi, questi sono alcuni dei miei pensieri ...

Prima di approfondire un'implementazione, volevo vedere se qualcun altro su StackOverflow ha esperienza con questo tipo di problema e potrebbe fornire indicazioni per un'implementazione accurata ed efficiente.

Modifica

Sono particolarmente interessato al " Gradient " suggerimento di ellisbben. E la mia struttura di dati di base (ignorando alcune delle scorciatoie di ottimizzazione dell'interpolazione) può essere rappresentata come la somma di un insieme di funzioni gaussiane 2D, che è totalmente differenziabile.

Suppongo che avrò bisogno di una struttura di dati per rappresentare una pendenza tridimensionale e una funzione per calcolare quel vettore di pendenza per un punto arbitrario. Fuori dalla mia testa, non so come farlo (anche se sembra che dovrebbe essere facile), ma se hai un link che spiega la matematica, sarei molto obbligato!

UPDATE:

Grazie agli eccellenti contributi di ellisbben e Azim, ora posso calcolare l'angolo del contorno per qualsiasi punto arbitrario nel campo. A breve seguiranno le linee del topo reale!

Ecco i rendering aggiornati, con e senza il topo-renderer basato su ghetto raster che ho usato. Ogni immagine include un migliaio di punti campione casuali, rappresentati da punti rossi. L'angolo di contorno in quel punto è rappresentato da una linea bianca. In alcuni casi, nessuna pendenza potrebbe essere misurata in un determinato punto (in base alla granularità dell'interpolazione), quindi il punto rosso si presenta senza una corrispondente linea di angolo del contorno.

Enjoy!

(NOTA: questi rendering utilizzano una topografia di superficie diversa rispetto ai rendering precedenti, poiché genero casualmente le strutture di dati su ciascuna iterazione, mentre sto prototipando, ma il metodo di rendering principale è lo stesso, quindi Sono sicuro che hai avuto l'idea.)

Ecco un fatto divertente: sul lato destro di questi rendering, vedrai un mucchio di strane linee di contorno con angoli orizzontali e verticali perfetti. Questi sono artefatti del processo di interpolazione, che utilizza una griglia di interpolatori per ridurre il numero di calcoli (di circa il 500%) necessari per eseguire le operazioni di rendering di base. Tutte quelle strane linee di contorno si trovano sul confine tra due celle della griglia dell'interpolatore.

Fortunatamente, quei manufatti non contano davvero. Sebbene gli artefatti siano rilevabili durante il calcolo dell'inclinazione, il renderer finale non li noterà, poiché opera a una profondità di bit diversa.

---

AGGIORNAMENTO NUOVAMENTE:

Aaaaaaa e, come ultima indulgenza prima di andare a dormire, ecco un'altra coppia di rendering, uno nella vecchia scuola "a colori continui"; stile e uno con 20.000 campioni di gradiente. In questo set di rendering, ho eliminato il punto rosso per i punti campione, poiché ingombra inutilmente l'immagine.

Qui puoi davvero vedere quegli artefatti di interpolazione a cui ho fatto riferimento in precedenza, grazie alla struttura a griglia della collezione di interpolatori. Dovrei sottolineare che questi artefatti saranno completamente invisibili sul rendering del contorno finale (poiché la differenza di grandezza tra due celle interpolatrici adiacenti è inferiore alla profondità in bit dell'immagine renderizzata).

Buon appetito !!

Answer 1

Il gradiente è un operatore matematico che può aiutarti.

Se puoi trasformare la tua interpolazione in una funzione differenziabile, il gradiente dell'altezza punterà sempre nella direzione della salita più ripida. Tutte le curve di uguale altezza sono perpendicolari al gradiente di altezza valutato in quel punto.

La tua idea di partire dal punto più alto è ragionevole, ma potrebbe mancare funzionalità se esiste più di un massimo locale.

Suggerirei

1. scegli i valori di altezza a cui traccerai le linee
2. crea un gruppo di punti su una griglia fine e regolarmente spaziata, quindi cammina ogni punto a piccoli passi nella direzione del gradiente verso l'altezza più vicina alla quale vuoi tracciare una linea
3. crea curve facendo un passo ogni punto perpendicolare al gradiente; eliminare i punti in eccesso uccidendo un punto quando un'altra curva si avvicina troppo ad essa - ma per evitare di distruggere il centro della clessidra come figure, potrebbe essere necessario controllare l'angolo tra il vettore orientato perpendicolare al gradiente per entrambi i punti. (Quando dico orientato, intendo assicurarmi che l'angolo tra il gradiente e il valore perpendicolare calcolato sia sempre di 90 gradi nella stessa direzione.)

Answer 2

In alternativa, esiste l'algoritmo marching square che sembra appropriato al tuo problema, sebbene tu potrebbe essere utile uniformare i risultati se si utilizza una griglia grossolana.

Le curve topografiche che si desidera disegnare sono isosurfaces di un campo scalare di 2 dimensioni. Per isosuperfici in 3 dimensioni, esiste l'algoritmo cubi in marcia .

Answer 3

In risposta al tuo commento a @erickson e per rispondere al punto sul calcolo del gradiente della tua funzione. Invece di calcolare le derivate della tua funzione di 300 termini potresti fare una differenziazione numerica come segue.

Dato un punto [x, y] nell'immagine, puoi calcolare il gradiente (direzione del più ripido decente)

g={  ( f(x+dx,y)-f(x-dx,y) )/(2*dx), 
  {  ( f(x,y+dy)-f(x,y-dy) )/(2*dy) 

dove dx e dy potrebbero essere la spaziatura nella griglia. La linea di contorno verrà perpendicolare al gradiente. Quindi, per ottenere la direzione del contorno, c, possiamo moltiplicare g = [v, w] per matrice, A = [0 -1, 1 0] dando

c = [-w,v]

Answer 4

Anch'io ho voluto qualcosa del genere, ma non ho trovato una soluzione vettoriale.

Una soluzione basata su raster non è poi così male, specialmente se i tuoi dati sono basati su raster. Se anche i tuoi dati sono basati su vettori (in altre parole, hai un modello 3D della tua superficie), dovresti essere in grado di fare un vero calcolo matematico per trovare le curve di intersezione con piani orizzontali a quote diverse.

Per un approccio basato su raster, guardo ogni coppia di pixel vicini. Se uno è al di sopra di un livello di contorno e uno al di sotto, ovviamente una linea di contorno scorre tra di essi. Il trucco che ho usato per anti-alias della linea di contorno è quello di mescolare il colore della linea di contorno in entrambi pixel, proporzionale alla loro vicinanza alla linea di contorno idealizzata.

Forse alcuni esempi aiuteranno. Supponiamo che il pixel corrente sia ad una "elevazione" di 12 piedi, un vicino si trova ad un'altezza di 8 piedi e le linee di contorno sono ogni 10 piedi. Quindi, c'è una linea di contorno a metà strada; dipingi il pixel corrente con il colore della linea di contorno con un'opacità del 50%. Un altro pixel è a 11 piedi e ha un vicino a 6 piedi. Colora il pixel corrente con un'opacità dell'80%.

alpha = (contour - neighbor) / (current - neighbor)

Sfortunatamente, non ho il codice a portata di mano, e potrebbe esserci stato qualcosa in più (ricordo vagamente di aver visto anche i vicini diagonali e di aver regolato con sqrt (2) / 2 ). Lo spero abbastanza per darti un'idea.

Answer 5

Mi è venuto in mente che ciò che stai cercando di fare sarebbe abbastanza facile da fare in MATLAB, usando la funzione di contorno. Fare cose come fare approssimazioni a bassa densità ai contorni può probabilmente essere fatto con una post-elaborazione dei contorni abbastanza semplice.

Fortunatamente, GNU Octave, un clone MATLAB, ha implementazioni delle varie funzioni di tracciamento dei contorni. Potresti guardare quel codice per un algoritmo e un'implementazione che sono quasi certamente matematicamente validi. In alternativa, potresti semplicemente essere in grado di scaricare l'elaborazione su Octave. Dai un'occhiata alla pagina interfacciarsi con altre lingue per vedere se sarebbe più facile.

Divulgazione: non ho usato Octave molto, e non ho ancora testato la trama del contorno. Tuttavia, dalla mia esperienza con MATLAB, posso dire che ti darà quasi tutto ciò che stai chiedendo in poche righe di codice, a condizione che tu trasferisca i tuoi dati in MATLAB.

Inoltre, congratulazioni per aver creato una trama molto inclinata per VanGough.

Answer 6

Controllo sempre luoghi come http://mathworld.wolfram.com prima di approfondire da solo :)

Forse la loro curve sarebbe d'aiuto? O forse la voce su maps .

Answer 7

confronta ciò che hai reso con una mappa topografica del mondo reale - mi sembrano identici! non cambierei nulla ...

Answer 8

Scrivi i dati come file HGT (molto semplice formato di dati di elevazione digitale utilizzato da USGS) e utilizzare lo strumento gratuito e open source gdal_contour contorni. Funziona molto bene per le mappe terrestri, il vincolo è che i punti dati sono firmati numeri a 16 bit, che si adatta molto bene alla gamma terrestre di altezze in metri, ma potrebbe non essere sufficiente per i tuoi dati, che presumo non sia un mappa del terreno reale, anche se menzioni le mappe del terreno.

Answer 9

Raccomando il CONREC :

• Crea un elenco di segmenti di linea vuota
• Dividi i tuoi dati in normali quadrati della griglia
• Per ogni quadrato della griglia, dividi il quadrato in 4 triangoli componenti:
  • Per ogni triangolo, gestisci i casi (da a a j):
    • Se un segmento di linea attraversa uno dei casi:
      • Calcola i suoi endpoint
      • Memorizza il segmento di linea nell'elenco
• Disegna ogni segmento di linea nell'elenco dei segmenti di linea

Se le linee sono troppo frastagliate, utilizzare una griglia più piccola. Se le linee sono abbastanza lisce e l'algoritmo impiega troppo tempo, usa una griglia più grande.