Как эффективно найти ближайшую точку на линии?

10

У меня есть таблица PostgreSQL 9.1 с сотнями тысяч точек PostGIS. Для каждого из них я бы хотел найти ближайшую точку в другой таблице ТОЧЕК. Точки во второй таблице представляют сетку по всему миру, поэтому я знаю, что всегда будет совпадение в пределах 1 градуса. Этот запрос я использую до сих пор, который использует индексы GIST, поэтому он достаточно быстрый (всего около 30 секунд).

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)

Единственная проблема - дата. Точки сетки имеют широту 180, а не -180. При использовании геометрической версии ST_Distance это не возвращает точек на другой стороне линии даты. Например. если p.pos - POINT(-179.88056 -16.68833)это ближайшая точка сетки POINT(180 -16.25), но приведенный выше запрос не возвращает ее. Какой лучший способ это исправить?

Я действительно не хочу иметь две координаты для одной точки сетки (-180 и +180). Я попытался добавить свою собственную функцию, которая проверяет этот конкретный случай, но затем запрос не возвращается через 5 минут, возможно, потому что он больше не может использовать индекс. Я также попытался использовать географическую версию ST_DWithin, и этот запрос также не вернулся через 5 минут.

postgis nearest-neighbor EM0
источник
Хороший вопрос (и умный взлом в вашем ответе!). Однако следует задаться вопросом: если программное обеспечение не может распознать, что -180 = 180 для долготы, то, вероятно, притворяется, что это проекционные координаты, и использует евклидовы алгоритмы для нахождения ближайших точек, что приведет к ошибкам (едва различимые экватор, огромный возле полюсов и меридианов + -180). Я не знаю, приводит ли это к значительным проблемам в вашем приложении, но во многих других это будет, и этот обходной путь не вылечит ошибки.
whuber
Хороший вопрос, но в этом случае клиентское приложение не будет выполнять другие «самые близкие» вычисления - оно просто получит некоторые данные, связанные с точкой сетки, возвращенной из моего запроса.
EM0

Ответы:

6

Хорошо, я наконец-то нашел способ взломать его, который не только работает вокруг проблемы с датой, но и быстрее.

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

Я был очень удивлен, увидев, что эта функция, которая вызывается для каждой строки, работает быстрее, чем исходная оконная функция, но в 10 раз быстрее. Производительность PostgreSQL - это черное искусство!

EM0
источник