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

23

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 funciones de entrada de puntos usando la triangulación de Delaunay, pero si hay un proceso similar para hacerlo con las funciones de línea no he podido encontrarlo.

ETA: Se me ocurrió la solución de Geogeek, pero en 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.

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 los vértices de la línea solamente), generar polígonos de Thiessen a partir de ellos, y luego disolverlos en función de la línea de origen. ID.

    
pregunta Dan C 04.03.2013 - 16:54

2 respuestas

10

Para ilustrar una solución de procesamiento de imágenes / ráster, comencé con la imagen publicada. Es de una calidad mucho más baja 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 celdas 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 usó 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[[email protected]@DistanceTransform[ColorNegate[string]]]

(TodoelcódigoquesemuestraaquíesMathematica8.)

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

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

Labandarojarepresentaloquepodríaguardardelalíneaylabandacianmuestralascrestasenlatransformadadedistancia.(Todavíahayunagrancantidaddebasuradebidoaloscortesenlalíneaoriginal).Estascrestasdebenlimpiarseycerrarseconunadilataciónadicional(dospíxeles)yluegopodemosidentificarlasregionesconectadasdeterminadasporlaslíneasoriginalesylascrestasentreellas(algunasdelascualesnecesitanserrecombinadasexplícitamente):

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

Loqueestohalogrado,enefecto,esidentificarcincocaracterísticaslinealesorientadas.Podemosvertrescaracterísticaslinealesseparadasqueemanandeunpuntodeconfluencia.Cadaunotienedoslados.Heconsideradoqueelladoderechodelasdosfuncionesdeladerechaeselmismo,perodeotramanerahedistinguidotodolodemás,dandolascincofunciones.LasáreascoloreadasmuestraneldiagramadeVoronoiapartirdeestascincocaracterísticas.

Un comando de Asignación Euclidiana basado en una capa que distingue las tres características lineales (que no tenía disponible para esta ilustración) no distinguiría los diferentes lados de cada característica lineal, y así lo haría combina las regiones verde y naranja que flanquean la línea de la izquierda; dividiría la característica del trullo más a la derecha en dos; y combinaría esas piezas divididas con las correspondientes características beige y magenta en sus otros lados.

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

    
respondido por el whuber 04.03.2013 - 19:59
4

Creo que puedes:

  • Convierta los vértices de línea en puntos (puntos de línea).
  • haz polígonos voronoi usando los puntos (puntos de línea).
  • 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.

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

    
respondido por el geogeek 04.03.2013 - 17:38

Lea otras preguntas en las etiquetas