¿Cómo encontrar eficientemente el punto más cercano en la línea de fecha?

10

Tengo una tabla PostgreSQL 9.1 con cientos de miles de PUNTOS PostGIS. Para cada uno de estos me gustaría encontrar el punto más cercano en otra tabla de PUNTOS. Los puntos en la segunda tabla representan una cuadrícula en todo el mundo, por lo que sé que siempre habrá una coincidencia dentro de 1 grado. Esta es la consulta que estoy usando hasta ahora, que hace uso de índices GIST, por lo que es razonablemente rápido (aproximadamente 30 segundos en total).

SELECT DISTINCT ON (p.id)
    p.id, ST_AsText(p.pos)
    , ST_AsText(first_value(g.location) OVER (PARTITION BY p.id ORDER BY ST_Distance(p.pos, g.location::geography)))
FROM point p
JOIN grid g ON ST_DWithin(p.pos::geometry, g.location, 1)

El único problema es la fecha. Los puntos de la cuadrícula solo tienen latitud 180, no -180. Cuando se utiliza la versión de geometría de ST_Distance, esto no devuelve puntos en el otro lado de la línea de fecha. P.ej. si p.pos es POINT(-179.88056 -16.68833)el punto de cuadrícula más cercano POINT(180 -16.25), pero la consulta anterior no lo devuelve. ¿Cuál es la mejor manera de arreglar esto?

Realmente no quiero tener dos coordenadas para un solo punto de cuadrícula (-180 y +180). Intenté agregar mi propia función que verifica este caso específico, pero luego la consulta no regresa en 5 minutos, probablemente porque ya no puede usar el índice. También intenté usar la versión de geografía de ST_DWithin y esa consulta tampoco regresó después de 5 minutos.

postgis nearest-neighbor EM0
fuente
Buena pregunta (¡y hack inteligente en tu respuesta!). Sin embargo, uno debe preguntarse: si el software no puede reconocer que -180 = 180 para la longitud, entonces probablemente está pretendiendo que estas son coordenadas proyectadas y está utilizando algoritmos euclidianos para encontrar puntos más cercanos, lo que va a producir errores (sutiles cerca el ecuador, enorme cerca de los polos y los meridianos + -180). No sé si eso conduce a problemas importantes en su aplicación, pero en muchos otros lo hará, y esa solución no solucionará los errores.
whuber
Buen punto, pero en este caso la aplicación cliente no hará otros cálculos "más cercanos", solo obtendrá algunos datos asociados con el punto de la cuadrícula devueltos por mi consulta.
EM0

Respuestas:

6

OK, finalmente descubrí una manera de hackearlo que no solo funciona alrededor del problema de la fecha, sino que también es más rápido.

CREATE OR REPLACE FUNCTION nearest_grid_point(point geography(Point))
RETURNS integer
AS $BODY$
    SELECT pointid
    FROM
    (
            -- The normal case
        SELECT pointid, location
        FROM grid
        WHERE ST_DWithin($1::geometry, location, 1)

        UNION ALL

            -- The dateline hack
        SELECT pointid, location
        FROM grid
        WHERE (ST_X($1::geometry) < -178.75 AND longitude = 180)
    ) sub
    ORDER BY ST_Distance($1, location::geography)
    LIMIT 1;
$BODY$ LANGUAGE SQL STABLE;

SELECT p.id, ST_AsText(p.pos), g.pointid, ST_AsText(g.location)
FROM point p
JOIN grid g ON nearest_grid_point(p.pos) = g.pointid

Me sorprendió mucho ver que esta función, que se llama para cada fila, es más rápida que la función de ventana original, pero es más de 10 veces más rápida. ¡El rendimiento de PostgreSQL realmente es un arte negro!

EM0
fuente