SRS mana yang digunakan untuk kueri jarak global?

Saya memiliki database dengan banyak poin di WGS84. Sekarang saya sedang membangun cache yang melakukan NN dan menunjuk dalam rentang pertanyaan menggunakan KDtree. Intinya [sic] adalah bahwa jari-jari pencarian akan disediakan dalam meter dan bahwa lat / lon bukan SRS yang bagus untuk kueri geometris ini.

Saya mencari SRS geometris yang berlaku untuk seluruh dunia dan yang menjaga jarak. Saya tidak peduli dengan kesalahan beberapa 10 meter.

coordinate-system distance nearest-neighbor RickyA
sumber

Mengapa tidak mengonversi semua poin ke koordinat 3D xyz (geosentris) dan membangun pohon KD Anda di situ? Meskipun tidak mempertahankan jarak, jarak pada bola mudah dikonversi menjadi jarak dalam 3D untuk keperluan kueri. Sebenarnya sangat mudah untuk mengkonversi lat-lon ke xyz dengan model ellipsoidal sehingga Anda tidak perlu mengorbankan akurasi sama sekali, tetapi bahkan jika Anda menggunakan model bola, semua jarak harus akurat hingga sekitar 0,3% (paling buruk ).

whuber

Jawaban:

Saya melakukan beberapa googling untuk "Indeks Spasial Spheris". Ada banyak metode yang mungkin menggunakan dekomposisi segitiga bola, atau voronoi tilings. Salah satu metode yang terlihat mudah diimplementasikan, adalah dengan mempertimbangkan data Anda dalam 3d, seperti pada bagian "3D Bounding Box" di sini:

http://lin-ear-th-inking.blogspot.co.uk/2007/09/geodetic-data-in-postgis-spherical.html

Maka Anda memerlukan indeks spasial 3d dari beberapa jenis, maka Anda dapat dengan cepat menemukan semua titik dalam 1 km Anda. Ini akan menjadi radius pencarian 1km 3D , jadi sedikit berbeda dengan radius 1km di sepanjang permukaan bumi, tetapi untuk jari-jari pencarian kecil, itu akan secara efektif identik (lakukan matematika untuk mengerjakan koreksi).

Jika Anda ingin presisi absolut, gunakan ini sebagai langkah pertama dan kemudian hitung jarak melalui lingkaran besar untuk menghilangkan jarak yang lebih jauh (jarak di sepanjang bola selalu lebih besar daripada jarak melalui bola).

Spacedman
sumber

Hei, itu ide! Saya bisa menekan dimensi lain di KDTree saya dan bekerja dengannya. Akan membutuhkan beberapa pengerjaan ulang :)

RickyA

Dengan proyeksi SRS / Peta, selalu ada trade off. Sebenarnya tidak ada satu yang cocok untuk semua tempat di dunia. Mungkin juga berasumsi bahwa bumi adalah bola.

Daripada mencari SRS yang sesuai dengan seluruh dunia, saya pikir Anda lebih baik mencari algoritma perhitungan jarak . Contohnya adalah Great Circle Distanc e yang didasarkan pada trigonometri bola. Itu memang membuat asumsi seperti:

1 menit busur adalah 1 mil laut
1 mil laut adalah 1,852 km.

Rumusnya adalah:

D = 1.852 * 60 * ARCOS ( SIN(L1) * SIN(L2) + COS(L1) * COS(L2) * COS(DG)

Dimana:

L1  =   latitude at the first point (degrees)
L2  =   latitude at the second point (degrees)
G1  =   longitude at the first point (degrees)
G2  =   longitude at the second point (degrees)
DG  =   longitude of the second point minus longitude of the first point (degrees)
DL  =   latitude of the second point minus latitude of the first point (degrees)
D   =   computed distance (km)

Anda mungkin ingin mengujinya dengan data Anda terlebih dahulu dan lihat hasilnya. Btw, apakah Anda menggunakan basis data spasial seperti PostGIS?

RK
sumber

Nah, itu intinya. Postgis tidak cukup cepat untukku. Apa yang saya lakukan sekarang adalah meletakkan semua poin di redis dan membuat indeks KDtree di atasnya. TETAPI KDtree adalah solusi geometris. Jika saya mengajukan pertanyaan seperti "berikan semua titik dalam radius 1k" itu akan menginjak jarak secara geometris. Saya tidak bisa melakukan haversine di sana. Saya perlu mengubahnya terlebih dahulu ke SRS yang kurang lebih sama. Tapi yang mana?

RickyA

Memperbarui jawaban saya dengan rumus. Itulah masalahnya, tidak ada proyeksi (geometris) SRS / CRS yang berlaku untuk seluruh dunia.

Dan kira-kira yang terbaik? Saya tidak terlalu peduli dengan kutub, hanya penguin di sana, tetapi sesuatu yang berkinerja geometris lebih baik daripada WGS84?

RickyA

Postgis mendukung bidang bola ketika menggunakan tipe geografi alih-alih geometri. postgis.refractions.net/docs/…

nickves

@nickves ya saya melihat itu, tetapi postgis benar-benar tidak cukup cepat untuk saya. Saya membutuhkan latensi kurang dari 2 ms dan harus dapat menangani 1000 permintaan per detik. Saya bisa membalikkan solusi postgis insinyur :)

RickyA