Como encontrar com eficiência o ponto mais próximo da linha de dados?

10

Eu tenho uma tabela do PostgreSQL 9.1 com centenas de milhares de pontos do PostGIS. Para cada uma dessas opções, eu gostaria de encontrar o ponto mais próximo em outra tabela de PONTOS. Os pontos da segunda tabela representam uma grade em todo o mundo, então eu sei que sempre haverá uma correspondência dentro de 1 grau. Esta é a consulta que estou usando até agora, que faz uso de índices GIST, por isso é razoavelmente rápido (cerca de 30 segundos no 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)

O único problema é a linha de dados. Os pontos da grade têm apenas latitude 180, não -180. Ao usar a versão geométrica de ST_Distance, isso não retorna pontos do outro lado da linha de dados. Por exemplo. se p.pos for POINT(-179.88056 -16.68833)o ponto de grade mais próximo POINT(180 -16.25), mas a consulta acima não o retornará. Qual é a melhor maneira de corrigir isso?

Eu realmente não quero ter duas coordenadas para um único ponto de grade (-180 e +180). Tentei adicionar minha própria função que verifica esse caso específico, mas a consulta não retorna em 5 minutos, provavelmente porque não pode mais usar o índice. Eu também tentei usar a versão geográfica do ST_DWithin e essa consulta também não retornou após 5 minutos.

postgis nearest-neighbor EM0
fonte
Boa pergunta (e truque inteligente na sua resposta!). No entanto, é de se perguntar: se o software é incapaz de reconhecer -180 = 180 para longitude, provavelmente está fingindo que estas são coordenadas projetadas e está usando algoritmos euclidianos para encontrar pontos mais próximos, o que produzirá erros (sutis próximos o equador, enorme perto dos pólos e dos + -180 meridianos). Não sei se isso leva a problemas significativos em seu aplicativo, mas em muitos outros, e essa solução alternativa não solucionará os erros.
whuber
Bom ponto, mas neste caso o aplicativo cliente não fará outros cálculos "mais próximos" - apenas obterá alguns dados associados ao ponto de grade retornado da minha consulta.
EM0 02/12/11

Respostas:

6

OK, finalmente descobri uma maneira de hackear isso, que não apenas contorna o problema da linha de dados, mas também é mais 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

Fiquei muito surpreso ao ver que essa função, que é chamada para todas as linhas, é mais rápida que a função original da janela, mas é - mais de 10 vezes mais rápida. O desempenho do PostgreSQL é realmente uma arte negra!

EM0
fonte