¿Qué puedo usar para generar un gráfico interconectado a partir de una serie de coordenadas?

Question

Tengo una tabla que contiene coordenadas de latitud y longitud, y me gustaría poder construir un gráfico interconectado a partir de ella para usarlo con pgRouting.

¿Existe alguna característica existente de postGIS o pgRouting que pueda usar para hacer esto?

Answer 1

Para hacer esto, su tabla debe contener dos coordenadas, una para cada extremo de la conexión. Si tiene esto, puede hacer un join en las coordenadas para emparejar los extremos y asignarles ids coincidentes. Por ejemplo, imagina que tienes una tabla con la siguiente definición:

create table foo (from_x float, from_y float, to_x float, to_y float);

Luego, agregue algunas columnas de id:

alter table foo add column from_id int;
alter table foo add column to_id int;

Luego, asigne un id único inicial a cada extremo utilizando una secuencia:

create sequence id_seq;
update foo set from_id = nextval('id_seq'), to_id = nextval('id_seq');

Ahora la parte divertida, empareje todos los valores de X e Y y elija el id más bajo de todos los emparejamientos:

update foo f1 set from_id = (select min(id) from  
    (select from_id as id from foo f2 
      where f2.from_x= f1.from_x 
        and f2.from_y=f1.from_y 
    UNION 
     select from_id as id from foo f3 
      where f3.to_x= f1.from_x 
        and f3.to_y=f1.from_y) as bar)

update foo f1 set to_id = (select min(id) from 
    (select from_id as id from foo f2 
      where f2.from_x= f1.to_x 
        and f2.from_y=f1.to_y
    UNION
     select from_id as id from foo f3 
      where f3.to_x= f1.to_x 
        and f3.to_y=f1.to_y) as bar);

Probablemente hay una forma más eficiente de escribir esas dos últimas declaraciones de actualización, pero esas deberían funcionar, a menos que tenga una cantidad muy grande de datos, en cuyo caso, un índice en las columnas X e Y es esencial:

create index on foo(x,y);

Si quisiera, podría crear puntos postgis de todas las coordenadas x e y, pero eso no es realmente necesario para construir el gráfico. Sin embargo, si sus coordenadas no son perfectamente iguales/ajustadas, entonces tendrá que cambiar la consulta para usar algo como:

@(f2.from_x - f3.from_x) < {tolerancia}

lo cual probablemente no será indexable, por lo que en ese caso, hacer los puntos, construir un índice espacial en ellos y usar st_dwithin() probablemente será el mejor enfoque.