K-vecinos más cercanos consulta en PostGIS

Question

estoy usando el siguiente vecino más cercano consulta en PostGIS:

SELECT g1.gid g2.gid FROM points as g1, polygons g2 
WHERE g1.gid <> g2.gid 
ORDER BY g1.gid, ST_Distance(g1.the_geom,g2.the_geom) 
LIMIT k; 

Ahora, que he creado índices en the_geom, así como la columna GID en ambas tablas, esta consulta es Tomando mucho más tiempo que otras consultas espaciales que involucran uniones espaciales b/w dos tablas.

¿Hay alguna forma mejor de encontrar a los vecinos más cercanos? Estoy usando PostGIS.

Y, otra consulta que está tomando un tiempo inusualmente largo a pesar de crear índices en la columna de geometría es:

select g1.gid , g2.gid from polygons as g1 , polygons as g2 
where st_area(g1.the_geom) > st_area(g2.the_geom) ; 

creo, estas consultas enviaban beneficiados por los índices del esencial, pero ¿por qué?

Considerando que la presente consulta:

select a.polyid , sum(length(b.the_geom)) from polygon as a , roads as b 
where st_intersects(a.the_geom , b.the_geom); 

devuelve un resultado después de algún tiempo a pesar de la participación de "caminos" de mesa que es mucho más grande que los polígonos o puntos de mesa y también están implicados conductores espaciales más complejas.

Answer 1

A pocos pensamientos sobre su problema:

ST_Distance, así como ST_Area no son capaces de utilizar índices. Esto se debe a que ambas funciones no pueden reducirse a preguntas como "¿Está dentro de b?" o "¿se superponen ayb?". Aún más concreto: los índices GIST solo pueden operar en los cuadros delimitadores de dos objetos.

Para obtener más información al respecto, simplemente puede buscar en el postgis manual, que indica un ejemplo con st_distance y cómo la consulta podría mejorarse para obtener un mejor rendimiento.

Sin embargo, esto no resuelve su problema de vecino k-más cercano. Por eso, en este momento no tengo una buena idea de cómo mejorar el rendimiento de la consulta. La única posibilidad que veo es suponer que los k vecinos más cercanos están siempre a una distancia inferior a x metros. Entonces podría usar un enfoque similar al que se hace en el manual de Postgis.

Su segunda consulta podría acelerarse un poco. Actualmente, calcula el área para cada objeto en la tabla 1 tan a menudo como la tabla tiene filas: la estrategia es primero unir los datos y luego seleccionar en función de esa función. Se podría reducir el número de cálculos zona verse significativamente precomputación de la zona:

WITH polygonareas AS (
    SELECT gid, the_geom, st_area(the_geom) AS area 
    FROM polygons 
) 
SELECT g1.gid, g2.gid 
FROM polygonareas as g1 , polygonareas as g2 
WHERE g1.area > g2.area; 

Su tercera consulta se puede optimizar de manera significativa el uso de cuadros delimitadores: Cuando los cuadros delimitadores de dos objetos no se superponen, no hay forma de los objetos hacen . Esto permite el uso de un índice dado y, por lo tanto, una gran ganancia de rendimiento.

Answer 2

Lo que puede necesitar es el índice KNN que es de esperar que pronto disponibles en PostGIS 2.x y PostgreSQL 9.1: Ver http://blog.opengeo.org/tag/knn/

Answer 3

Desde late September 2011, PostGIS ha apoyado indexados consultas de vecinos más cercanos a través de un operador especial (s), utilizables en la cláusula ORDER BY:

SELECT name, gid 
FROM geonames 
ORDER BY geom <-> st_setsrid(st_makepoint(-90,40),4326) 
LIMIT 10; 

... volverán los 10 objetos cuya geom es más cercana -90,40 de una manera escalable.Algunos detalles más (opciones y advertencias) están en ese anuncio post y use of the <-> y the <#> operators ahora también están documentados en la referencia oficial de PostGIS 2.0. (La principal diferencia entre los dos es que <-> compara los centroides de forma y <#> compara sus límites - no hay diferencia para los puntos, otras formas eligen lo que es apropiado para sus consultas.)

Answer 4

Suponiendo que tiene p punto yg polígonos, su consulta original:

SELECT g1.gid, g2.gid FROM points as g1, polygons g2 
WHERE g1.gid <> g2.gid 
ORDER BY g1.gid, ST_Distance(g1.the_geom,g2.the_geom) 
LIMIT k; 

Devuelve los k vecinos más cercanos en el conjunto pxg. La consulta puede estar usando índices, pero todavía tiene que ordenar todo el conjunto p x g para encontrar las k filas con la distancia más pequeña. Lo que desea en cambio es lo siguiente:

SELECT g1.gid, 
     (SELECT g2.gid FROM polygons g2 
     --prevents you from finding every nearest neighbour twice 
     WHERE g1.gid < g2.gid 
     --ORDER BY gid is erroneous if you want to limit by the distance 
     ORDER BY ST_Distance(g1.the_geom,g2.the_geom) 
     LIMIT k) 
FROM points as g1;