¿Crear polígonos de Thiessen (Voronoi) usando líneas (en lugar de puntos) como características de entrada?

24

Tengo un conjunto de entidades de línea dentro de un límite poligonal particular. Para cada línea, me gustaría generar un polígono dentro del cual cada punto posible esté más cerca de la línea dada que de cualquier otra línea en la capa. He hecho esto en el pasado para las características de entrada de puntos usando la triangulación de Delaunay, pero si hay un proceso similar para hacerlo con características de línea, no he podido encontrarlo.

ETA: se me ocurrió la solución de Geogeek, pero en las secciones más rectas donde las líneas de entrada tienen menos vértices, los polígonos resultantes se acercan demasiado (incluso se superponen) a una línea que no deberían. Aquí, las líneas rojas son mis entradas, puedes ver los vértices y los polígonos de Thiessen generados a partir de ellos.

ingrese la descripción de la imagen aquí

Quizás una solución rápida y (muy) sucia podría ser convertir cada línea en un conjunto abundante de puntos espaciados uniformemente (en lugar de solo los vértices de la línea), generar polígonos de Thiessen a partir de ellos y luego disolverlos en función de la ID de la línea de origen.

Dan C
fuente
44
Los diagramas de Voronoi que incluyen segmentos de línea junto con puntos no están compuestos de "polígonos"; más bien, sus celdas tienen límites que pueden incluir porciones de parábolas. Por esta razón, una de las formas más eficientes y precisas de crear teselaciones de Voronoi es utilizar una representación ráster. ESRI llama a este procedimiento Asignación euclidiana .
whuber

Respuestas:

11

Para ilustrar una solución de procesamiento de trama / imagen, comencé con la imagen publicada. Es de una calidad mucho menor que los datos originales, debido a la superposición de puntos azules, líneas grises, regiones coloreadas y texto; y el engrosamiento de las líneas rojas originales. Como tal, presenta un desafío: sin embargo, todavía podemos obtener células Voronoi con alta precisión.

Extraje las partes visibles de las características lineales rojas restando el verde del canal rojo y luego dilatando y erosionando las partes más brillantes en tres píxeles. Esto se utilizó como base para un cálculo de distancia euclidiana:

i = Import["http://i.stack.imgur.com/y8xlS.png"];
{r, g, b} = ColorSeparate[i];
string = With[{n = 3}, Erosion[Dilation[Binarize[ImageSubtract[r, g]], n], n]];
ReliefPlot[Reverse@ImageData@DistanceTransform[ColorNegate[string]]]

Trama de socorro

(Todo el código que se muestra aquí es Mathematica 8.)

Identificar las "crestas" evidentes, que deben incluir todos los puntos que separan dos celdas de Voronoi adyacentes, y volver a combinarlas con la capa de línea proporciona la mayor parte de lo que necesitamos para proceder:

ridges = Binarize[ColorNegate[
   LaplacianGaussianFilter[DistanceTransform[ColorNegate[string]], 2] // ImageAdjust], .65];
ColorCombine[{ridges, string}]

Imágenes combinadas

La banda roja representa lo que pude salvar de la línea y la banda cian muestra las crestas en la transformación de distancia. (Todavía hay mucha basura debido a los cortes en la línea original). Estas crestas deben limpiarse y cerrarse mediante una dilatación adicional, dos píxeles funcionarán, y luego podemos identificar las regiones conectadas determinadas por Las líneas originales y las crestas entre ellas (algunas de las cuales necesitan ser recombinadas explícitamente):

Dilation[MorphologicalComponents[
  ColorNegate[ImageAdd[ridges, Dilation[string, 2]]]] /. {2 -> 5, 8 -> 0, 4 -> 3} // Colorize, 2]

Lo que esto ha logrado, en efecto, es identificar cinco características lineales orientadas . Podemos ver tres características lineales separadas que emanan de un punto de confluencia. Cada uno tiene dos lados. He considerado que el lado derecho de las dos características más a la derecha es el mismo, pero por lo demás he distinguido todo lo demás, dando las cinco características. Las áreas coloreadas muestran el diagrama de Voronoi de estas cinco características.

Resultado

Un comando de asignación euclidiana basado en una capa que distingue las tres entidades lineales (que no tenía disponibles para esta ilustración) no distinguiría los diferentes lados de cada entidad lineal y, por lo tanto, combinaría las regiones verde y naranja que flanquean la línea más a la izquierda ; dividiría la característica verde azulado más a la derecha en dos; y combinaría esas piezas divididas con las características beige y magenta correspondientes en sus otros lados.

Evidentemente, este enfoque de trama tiene el poder de construir teselaciones Voronoi de características arbitrarias (puntos, piezas lineales e incluso polígonos, independientemente de sus formas) y puede distinguir lados de características lineales.

whuber
fuente
1
Una solución similar se ilustra en Mathica.stackexchange.com/questions/20696/… .
whuber
5

Yo creo que puedes:

  • Convierta vértices de línea en puntos (line_points).
  • Haz polígonos voronoi usando los puntos (line_points).
  • Disuelva los polígonos resultantes utilizando un atributo id que se ha guardado de la capa de línea o mediante una unión espacial con la capa de línea.

Espero haber entendido realmente su pregunta, si no puede proporcionar un dibujo para explicar más sus necesidades.

geogeek
fuente
2
Creo que lo entendiste, y esa solución se me ocurrió, pero te encuentras con problemas donde las líneas tienen menos vértices. Actualizaré mi pregunta con una captura de pantalla.
Dan C
3
Esto funcionaría bien si hicieras los puntos más densos a lo largo de la línea. Aunque un enfoque basado en la trama (como menciona Whuber en los comentarios sobre la pregunta) sospecharía que sería mucho más eficiente que esto.
Andy W