Bagaimana cara efisien menemukan titik terdekat di atas garis data?

10

Saya punya tabel PostgreSQL 9.1 dengan ratusan ribu TITIK PostGIS. Untuk masing-masing ini saya ingin mencari titik terdekat di tabel POINT lain. Poin di tabel kedua mewakili grid di seluruh dunia, jadi saya tahu akan selalu ada kecocokan dalam 1 derajat. Ini adalah permintaan yang saya gunakan sejauh ini, yang menggunakan indeks GIST, jadi cukup cepat (sekitar total 30 detik).

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)

Satu-satunya masalah adalah dateline. Poin grid hanya memiliki garis lintang 180, bukan -180. Saat menggunakan versi geometri dari ST_Distance, ini tidak mengembalikan poin di sisi lain dateline. Misalnya. jika p.pos adalah POINT(-179.88056 -16.68833)titik kisi terdekat mungkin POINT(180 -16.25), tetapi kueri di atas tidak mengembalikannya. Apa cara terbaik untuk memperbaikinya?

Saya tidak benar-benar ingin memiliki dua koordinat untuk satu titik grid (-180 dan +180). Saya mencoba menambahkan fungsi saya sendiri yang memeriksa kasus khusus ini, tetapi kemudian permintaan tidak kembali dalam 5 menit, mungkin karena tidak dapat lagi menggunakan indeks. Saya juga mencoba menggunakan versi geografi ST_DWithin dan permintaan itu juga tidak kembali setelah 5 menit.

postgis nearest-neighbor EM0
sumber
Pertanyaan bagus (dan retas cerdas dalam balasan Anda!). Kita harus bertanya-tanya: jika perangkat lunak tidak dapat mengenali bahwa -180 = 180 untuk bujur, maka mungkin berpura-pura ini adalah koordinat yang diproyeksikan dan menggunakan algoritma Euclidean untuk menemukan titik terdekat, yang akan menghasilkan kesalahan (hampir halus) khatulistiwa, besar di dekat kutub dan + -180 meridian). Saya tidak tahu apakah itu mengarah ke masalah signifikan dalam aplikasi Anda, tetapi dalam banyak hal lain itu akan terjadi, dan bahwa penyelesaian masalah tidak akan menyembuhkan kesalahan.
whuber
Poin bagus, tetapi dalam hal ini aplikasi klien tidak akan melakukan perhitungan "terdekat" lainnya - itu hanya akan mendapatkan beberapa data yang terkait dengan titik kisi yang dikembalikan dari kueri saya.
EM0

Jawaban:

6

OK, saya akhirnya menemukan cara untuk meretasnya yang tidak hanya bekerja di sekitar masalah dateline, tetapi juga lebih cepat.

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

Saya sangat terkejut melihat bahwa fungsi ini, yang dipanggil untuk setiap baris, lebih cepat dari fungsi jendela asli, tetapi - lebih dari 10 kali lebih cepat. Kinerja PostgreSQL benar-benar seni hitam!

EM0
sumber