¿Crear polígonos de Thiessen ponderados?

Hay muchas formas de ponderar distancias para construir polígonos de Thiessen. La idea básica para construirlos se basa en comparar la distancia entre un punto arbitrario x y dos puntos fijos p y q ; debe decidir si x está "más cerca" de p que de q o no. Con este fin, al menos conceptualmente, consideramos las distancias dp = d ( x , p ) y dq = d ( x , q ). La ponderación generalmente se produce de dos maneras: a los puntos se les puede dar ponderaciones numéricas positivas wp y wq y las distancias se pueden transformar.

Para que tenga sentido, la transformación (que escribiré como f ) debería aumentar a medida que aumenten las distancias; es decir, f (d ') > f (d) siempre que d '> d > = 0. Los ejemplos de tales transformaciones son f (d) = d + 1, f (d) = d ^ 2 (Ley de Reilly de la Gravitación Minorista), f (d) = 1 - 1 / d (asumiendo todas las distancias son menores que 1), f (d) = log (d), f (d) = exp (d) -1.

Entonces diríamos que x está "más cerca" de p que de q exactamente cuando

f (d ( x , p )) / wp < f (d ( x , q )) / wq.

Observe la división por los pesos, en lugar de la multiplicación: esto significa que los pesos grandes tenderán a "tirar" los puntos a distancias más grandes. Verás esto en el siguiente ejemplo de ejecución.

Aquí está lo bello, y el punto central de esta exposición algo abstracta: aunque las regiones de Thiessen resultantes pueden tener límites complejos, extremadamente difíciles de calcular, son relativamente fáciles de calcular usando una representación basada en cuadrícula. Aquí está la receta:

1. Para cada punto de entrada p , calcula su cuadrícula de distancia euclidiana [d (p)].

2. Usa el Álgebra de mapas para aplicar f y los pesos, reexpresando cada cuadrícula de distancia como

   [fp] = f ([d (p)]) / wp.

   Aquí hay un ejemplo que usa f (d) = 100 + d ^ (3/2); La escala es de 400 por 600.

   

   Amedidaqueaumentaf(d),elvalorseoscurece.Evidentemente,ladistanciaenesteejemploesconrespectoalpuntorojocentral;losotroscuatropuntosobtienensuscálculosdedistanciaporseparado(nosemuestran).Lasáreasdelospuntossonproporcionalesasuspesos,queson2,10,3,4y5.

3. Calculeelmínimolocaldetodasestascuadrículas[fp].Llamaaesto[f].Aquíhayunejemplo.

4. Al comparar [f] con cada [fp], a cada celda de la cuadrícula asigne el identificador de la primera p para la cual [f] > = [fp]. (Esto se puede hacer en un solo paso con un posición más baja operación, por ejemplo.)

   

   (Dudoqueexistaunalgoritmoencualquierlugarquecalculeunasolucióndeformatovectorialparaestafuncióndeponderaciónf.)

Obviamente,sitienesmásdeunpuñadodepuntosp,escribirásesto,ysisunúmeroasciendeamiles,probablementeabandonaráselintentoporsercomputacionalmenteimpracticable(aunquehayformasdeacelerarlo).elcálculopormosaico).

Otroejemplo,quemuestralospolígonosdeThiessenenunelipsoide,apareceen enlace .

Lo que quieres es un diagrama Voronoi ponderado: enlace También se conoce como una teselación circular de Dirichlet cuando se realiza con pesos multiplicativos en un plano 2d. Alguien parece haber construido una extensión de arcgis 9 para construir estos: enlace Con una guía de usuario disponible aquí enlace y un artículo publicado en Dong, P., 2008. Generación y actualización de diagramas Voronoi de ponderación multiplicada para características de puntos, líneas y polígonos en SIG. Computadoras y amp; Geociencias, Volumen 34, Número 4, Páginas 411-421.

Hay un artículo reciente sobre un algoritmo basado en vectores (supongo que el algoritmo de P Dong se basa en ráster) para esto. enlace El resumen dice que el código c # está incluido.