martes, 7 de marzo de 2017

Suma de distancias en matriz triangular de distancias con Python

La suma de distancias entre rasgos es un elemento que puede ser usado para establecer el rasgo central de una capa porque es la que presenta el valor mínimo. En los SIGs estas distancias generalmente se determinan, por defecto, para capas tipo punto; aunque cualquier geometría es admisible. Sin embargo, cuando el número de features es muy elevado, el tiempo de computo de las distancias se incrementa considerablemente.



Una forma de soslayar este problema es determinando aproximadamente sólo la mitad de los valores porque las distancias(i, j) son cero cuando i = j y las distancias(i, j) son idénticas a las distancias(j, i). Por tanto, se requieren sólo los elementos por encima de la diagonal principal y para ello contamos con el módulo 'itertools' de Python. Sin embargo, esto trae como consecuencia cierta complejidad en la determinación de las sumas de distancias que, en la matrix completa, era fácilmente realizable sumando filas o columnas. No obstante, la sistematización es posible a través de un algoritmo que se detalla en el código siguiente.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import numpy as np

s = [[25430.519729128635, 70347.69965443434, 51468.51998696665, 27904.775139871315, 10285.909880035046, 8205.078998979825, 79514.20519607572], 
     [23376.860147920117, 9822.746403386427, 12334.51610111128, 42590.28757803573, 6840.184176032323, 36250.827663119846], 
     [8710.987612903535, 33584.94923461142, 82871.18619999362, 48414.05621708637, 6998.9462354153775], 
     [6472.34076087506, 56826.726302831055, 27227.56231937672, 10499.78285279113], 
     [22558.65545285636, 12931.192105203158, 34874.19507216667], 
     [22339.18821617218, 87324.31184979565], 
     [55650.687415378845]]

index = [ [] for i in range(len(s)) ]
values = [ [] for i in range(len(s)) ]
sums1 = [0]

for i in range(len(s)):
    k = i
    for j in range(i+1):
        index[i].append([j, k])
        k -= 1
    for item in index[i]:
        values[i].append(s[item[0]][item[1]])

    sums1.append(np.sum(values[i]))

sums2 = [ np.sum(item) for item in s ]

sums2.append(0)

for i in range(len(s) + 1):
    print sums1[i] + sums2[i]

La matrix s de python que se encuentra al comienzo del código, aunque poco convencional, es admisible en este lenguaje y representan valores verdaderos de distancia para un shapefile tipo polígono con 8 features no solapados. Cuando se ejecuta elcodigo anterior en la Python Console de QGIS se obtienen los valores siguientes:

1
2
3
4
5
6
7
8
273156.708585
156645.941799
274304.685302
171028.666239
150660.623867
324796.26548
181607.949448
311112.956285

que son precisamente los esperados.

No hay comentarios: