La conversión de las regiones por vectores contorneado (fronteras) a un mapa raster (cuadrícula de píxeles)

Question

Tengo un mapa que se corta en una serie de regiones por las fronteras (contornos) como países en un mapamundi. Cada región tiene una cierta clase de superficie de la cubierta S (por ejemplo, 0 para el agua, 0,03 para la hierba ...). Los bordes se definen por:

• qué valor de S está en cualquier lado de él (0,03 en un lado, 0.0 en el otro, en el ejemplo a continuación)
• cuántos puntos de la frontera está hecho de ( n = 7 en el ejemplo a continuación), y
• n pares de coordenadas ( x , y ).

Este es un ejemplo.

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

Quiero hacer un mapa de la trama en la que cada píxel tiene el valor de S que corresponde a la región en la que el centro del píxel cae.

Tenga en cuenta que las fronteras representan paso cambios en S . Los diversos valores de S representan clases discretas (por ejemplo, hierba o agua), y no son valores que se pueden promediar (es decir, no hierba mojada!).

También tenga en cuenta que no todas las fronteras son bucles cerrados como el ejemplo anterior. Esto es un poco como las fronteras del país: por ejemplo, la frontera entre Estados Unidos y Canadá no es un bucle cerrado, sino más bien una línea que une arriba en cada extremo con otras dos fronteras: Canadá-océano y los EE.UU.-océano "fronteras". (Fronteras de bucle cerrado existen sin embargo!)

Puede alguien me punto a un algoritmo que puede hacer esto? No quiero reinventar la rueda!

Answer 1

La forma en que he resuelto este es el siguiente:

1. Marzo a lo largo de cada segmento; detener a intervalos regulares L .
2. En cada parada, colocar un punto trazador inmediatamente a la izquierda y a la derecha del segmento (a una cierta distancia pequeña d en el segmento). Los puntos trazadores se atribuyen el valor S izquierda y derecha, respectivamente.
3. Haga una interpolación del vecino más próximo. Cada punto de la cuadrícula de trama se atribuye la S del punto trazador más cercano.

Esto funciona incluso cuando hay líneas no cerrados, por ejemplo en el borde del mapa.

Esto no es un algoritmo de análisis "perfecta". Hay dos parámetros: L y d . El algoritmo funciona muy bien, siempre y cuando d << L . De lo contrario se puede obtener inexactitudes (por lo general solo píxel) cerca de las uniones de segmento, especialmente aquellos con ángulos agudos.

Answer 2

El caso general para el procesamiento de este tipo de geometría en forma vectorial puede ser bastante difícil, sobre todo porque nada acerca de la estructura que describe la geometría requiere ser consistente. Sin embargo, dado que lo que desea es rasterizar, a continuación, tratar el problema como un diagrama de Voronoi de segmentos de línea puede ser más robusto.

Aproximando el diagrama Voronoi puede hacerse gráficamente en OpenGL dibujando cada segmento de línea como un par de quads haciendo una forma de tienda de campaña. La memoria intermedia z se utiliza para hacer el quad más cercano tienen prioridad, y por lo tanto el color del pixel basado en la línea que esté más cerca. La diferencia aquí es que tendrá que dar color a los polígonos basado en qué lado de la línea que se encuentran, en lugar de la línea que ellos representan. Un buen documento que analiza un algoritmo similar es rápida de Generalizado Voronoi Diagrams el uso de gráficos Hardware

El 3d geometría se verá algo como esto boceto con 3 segmentos rojo / amarillo y 1 azul / verde segmento:

Este procedimiento no requiere que usted para convertir cualquier cosa en un circuito cerrado, y no requiere de ninguna biblioteca de geometría de lujo. Todo se maneja por el Z-buffer, y debe ser lo suficientemente rápido para ejecutar en tiempo real en cualquier tarjeta gráfica moderna. Un refinamiento sería el uso de coordenadas homogéneas para que el proyecto de bases hasta el infinito.

he implementado este algoritmo en un script Python en http://www.pasteall.org/9062/ pitón. Una advertencia interesante es que el uso de conos para coronar los extremos de las líneas no funcionaba sin distorsionar la forma del cono, ya que los conos que representan los puntos extremos de los segmentos eran z-lucha. Para la geometría de la muestra que ya ha proporcionado, la salida es el siguiente:

Answer 3

Me gustaría recomendar que utilice una biblioteca de algoritmos de geometría como CGAL . Especialmente el segundo ejemplo en los "polígonos 2D" la página del manual de referencia que debe proporcionar lo que necesita. Se pueden definir cada uno "frontera" como un polígono y comprobar si ciertos puntos están dentro de los polígonos. Así que, básicamente, sería algo así como

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]

No, no estoy tan seguro de qué hacer con el outside_color debido a que las regiones exteriores se superponen, lo harán? De todos modos, mirando a su ejemplo, cada región exterior podría ser agua, por lo que sólo podría hacer una final

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

(o como alternativa, establecer pixel [X] [Y] para water_value antes de iteración a través de la lista de polígonos)

Answer 4

• En primer lugar, convertir todos sus fronteras en bucles cerrados (posiblemente incluyendo los bordes de su mapa), e identificar el color interior. esto tiene que ser posible, de lo contrario usted tiene una inconsistencia en los datos
• algoritmo de uso de Bresenham a sacar todas las líneas de borde en el mapa, en un solo color sin usar
  • almacenar una lista de todos los píxeles del borde "" como lo hace
• a continuación, para cada frontera
  • triangular que (delaunay)
  • iterar a través de los triángulos hasta que encuentre uno cuyo centro está en el interior de su frontera (prueba de punto en el polígono)
  • floodFill su mapa en ese punto en el color del interior de la frontera
• Una vez que haya rellenado todas las regiones del interior, recorrer la lista de los píxeles del borde, al ver que el color de cada uno debe ser

Answer 5

• elegir dos colores no utilizados como marcadores "vacío" y "frontera"
• rellena toda la zona con "vacío" de color
• atraer a todos fronteras de la región de "frontera" de color
• iterar a través de puntos para encontrar primero con "vacío" de color
• determinar qué región pertenece a (google "punto dentro del polígono", probablemente tendrá que hacer sus fronteras cerradas como se sugiere Martin DeMello)
• realizar algoritmo de inundación de relleno en este punto con el color de la región
• ir al siguiente punto de "vacío" (sin necesidad de reiniciar la búsqueda - sólo sigue)
• y así sucesivamente hasta que no hay puntos "vacías" permanecerán