Conversione regioni vettori sagomato (confini) a una mappa raster (griglia di pixel)

Question

mi hanno una mappa che è tagliato in un certo numero di regioni confini (contorni) come paesi su una mappa del mondo. Ogni regione ha una certa classe di copertura di superficie S (ad esempio 0 per acqua, 0,03 per erba ...). I confini sono definiti da:

• quale valore di S è su entrambi i lati di esso (0,03 su un lato, 0,0 dall'altro, nell'esempio qui sotto)
• quanti punti confine è fatta di (n = 7 nell'esempio qui sotto), e
• n coppie di coordinate (x , y).

Questo è un esempio.

0.0300  0.0000   7 
2660607.5 6332685.5 2660565.0 6332690.5 2660541.5 6332794.5 
2660621.7 6332860.5 2660673.8 6332770.5 2660669.0 6332709.5 
2660607.5 6332685.5 

voglio creare una mappa raster in cui ogni pixel ha il valore di S corrispondente alla regione in cui il centro del pixel cade.

Si noti che i bordi rappresentano passaggio modifiche in S. I vari valori di S rappresentano classi discrete (ad esempio erba o acqua) e non sono valori che possono essere mediati (cioè senza erba bagnata!).

Si noti inoltre che non tutti i bordi sono loop chiusi come nell'esempio precedente. Questo è un po 'come i confini nazionali: ad es. il confine USA-Canada non è un circuito chiuso, ma piuttosto una linea che si congiunge a ciascuna estremità con due altri confini: il Canada-oceano e il "confine" oceano-Stati Uniti. (Bordi ad anello chiuso do exist tuttavia!)

Qualcuno può indicarmi un algoritmo in grado di farlo? Non voglio reinventare la ruota!

Answer 1

Il modo in cui ho risolto questo è il seguente:

1. marzo lungo ciascun segmento; fermarsi a intervalli regolari L.
2. Ad ogni fermata, posizionare un punto di tracciamento immediatamente a sinistra e a destra del segmento (a una certa piccola distanza d dal segmento). I punti di tracciamento sono attribuiti rispettivamente al valore S sinistro e destro.
3. Esegue un'interpolazione vicino più vicino. Ad ogni punto della griglia raster viene attribuita la S del punto di tracciamento più vicino.

Questo funziona anche quando ci sono linee non chiuse, ad es. sul bordo della mappa.

Questo non è un algoritmo analitico "perfetto". Esistono due parametri: L e d. L'algoritmo funziona magnificamente purché d < < L. In caso contrario è possibile ottenere imprecisioni (in genere pixel singolo) vicino alle giunzioni dei segmenti, in particolare quelle con angoli acuti.

Answer 2

Si consiglia di utilizzare una libreria di algoritmi geometrici come CGAL. Soprattutto lo the second example nella pagina "2D poligoni" del manuale di riferimento dovrebbe fornire quello che ti serve. È possibile definire ciascun "bordo" come un poligono e verificare se alcuni punti si trovano all'interno dei poligoni. Quindi, in pratica, sarebbe qualcosa di simile

for every y in raster grid 
    for every x in raster grid 
    for each defined polygon p 
     if point(x,y) is inside polygon p 
     pixel[X][Y] = inside_color[p] 

io non sono così sicuro su cosa fare con l'outside_color perché le regioni al di fuori si sovrapporranno, no? In ogni caso, guardando il tuo esempio, ogni regione al di fuori potrebbe essere l'acqua, in modo che solo potrebbe fare un finale

if pixel[X][Y] still undefined then pixel[X][Y] = water_value 

(o in alternativa, impostare pixel [X] [Y] per water_value prima che scorrendo l'elenco poligono)

Answer 3

• innanzitutto, converti tutti i bordi in cicli chiusi (possibilmente compresi i bordi della mappa) e identifica il colore interno.questo deve essere possibile, altrimenti si dispone di un'incongruenza nei dati
algoritmo
• utilizzo Bresenham trarre tutte le linee di confine sulla mappa, in un unico colore non utilizzato
  • memorizzare un elenco di tutti i "pixel di confine" come si esegue questa
• poi per ciascuna frontiera
  • triangulate esso (Delaunay)
  • scorrere l'triangoli fino a trovare uno il cui centro è dentro il bordo (point-in-poligono di prova)
  • floodFill vostra mappa a quel punto nel colore degli interni del confine
• una volta che avete compilato in tutte le regioni interne, scorrere l'elenco dei pixel di confine, vedendo quale colore ciascuno dovrebbe essere

Answer 4

• scegliere due colori non utilizzati come marcatori "vuoto" e "di confine"
• riempire tutta l'area con il colore "vuoto"
• disegnare tutti i confini regionali per "confine" colorare
• iterare attraverso i punti di trovare prima con il colore "vuoto"
• determinare quale regione a cui appartiene (google "punto all'interno del poligono", probabilmente è necessario per rendere il vostro confini chiusi come suggerito Martin DeMello)
• eseguire l'algoritmo flood-fill da questo punto con il colore della regione
• andare al punto successivo "vuoto" (non è necessario riavviare la ricerca - basta continuare)
• e così via fino senza punti "vuoti" rimarrà

Answer 5

Il ge Il caso generale per elaborare questo tipo di geometria in forma vettoriale può essere piuttosto difficile, specialmente dal momento che nulla sulla struttura che descrivi richiede che la geometria sia coerente. Tuttavia, dal momento che si desidera rasterizzarlo, trattare il problema come un diagramma Voronoi di segmenti di linea può essere più robusto.

L'approssimazione del diagramma di Voronoi può essere eseguita graficamente in OpenGL disegnando ogni segmento di linea come una coppia di quad che formano una forma di tenda. Il buffer z è usato per fare in modo che la quad più vicina abbia la precedenza, e quindi colorare il pixel in base a qualsiasi linea sia la più vicina. La differenza qui è che vorrete colorare i poligoni in base al lato della linea su cui si trovano, invece della linea che rappresentano. Una buona carta discutendo di un algoritmo simile è di Hoff et al Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware

Il 3d geometria avrà un aspetto simile a questo disegno con 3 rossi/segmenti gialli e 1 blu/segmento verde:

Questa procedura doesn Ti chiediamo di convertire qualsiasi cosa in un circuito chiuso e non richiede alcuna fantasia di librerie geometriche. Tutto è gestito dallo z-buffer e dovrebbe essere abbastanza veloce da funzionare in tempo reale su qualsiasi scheda grafica moderna. Una raffinatezza sarebbe di usare coordinate omogenee per rendere le basi proiettate all'infinito.

Ho implementato questo algoritmo in uno script Python a http://www.pasteall.org/9062/python.Un avvertimento interessante è che l'uso dei coni per tappare le estremità delle linee non ha funzionato senza distorcere la forma del cono, perché i coni che rappresentano i punti finali dei segmenti erano a z-fighting. Per la geometria del campione che hai fornito, l'output è simile al seguente: