Bagaimana cara efisien mencari semua tengara dalam rentang tengara tertentu?

Saya mencoba memulai dengan proyek pencarian geo yang akan menemukan semua landmark di 10 km / mil (tidak penting untuk cerita ini) dari landmark tertentu.

Jadi misalnya, katakanlah saya memiliki database 1.000.000 landmark. Untuk menemukan semua landmark dalam jarak 10 mil dari tengara dengan koordinat tertentu, saya harus menghitung jarak antara tengara dari pencarian saya dan 1.000.000 tengara.

Apakah ada cara yang lebih baik untuk melakukan itu?

Alternatif yang saya pikirkan adalah mengkategorikan landmark seperti negara, wilayah, kota, lingkungan, bisnis, sejarah, dll. Sedemikian rupa sehingga bisnis dapat menjadi bagian dari lingkungan atau kota. Kota adalah bagian dari suatu daerah, negara, dll. Ini dapat mempersempit daftar perhitungan, tetapi masih banyak pekerjaan yang harus dilakukan agar pencarian menjadi cepat dan akurat.

Bisakah Google Maps API membantu?

Sejak SQL Server 2008, ada tipe data geografi yang menyimpan lokasi (pasangan lat / lon) dan membuatnya mudah bagi Anda untuk menulis kueri terkait lokasi.

Ada jawaban StackOverflow yang ada yang membahas ini secara mendalam.

Permintaan dasar untuk menemukan 7 item terdekat :

USE AdventureWorks2012  
GO  
DECLARE @g geography = 'POINT(-121.626 47.8315)';  
SELECT TOP(7) SpatialLocation.ToString(), City FROM Person.Address  
WHERE SpatialLocation.STDistance(@g) IS NOT NULL  
ORDER BY SpatialLocation.STDistance(@g);  

Permintaan dasar untuk menemukan semuanya dalam jarak 100 m (jawaban kedua untuk pertanyaan)

-- Get the center point
DECLARE @g geography
SELECT @g = geo FROM yourTable WHERE PointId = something

-- Get the results, radius 100m
SELECT * FROM yourTable WHERE @g.STDistance(geo) <= 100

Gunakan database dengan dukungan untuk kueri GIS (sistem informasi geografis) . Sebagian besar basis data mendukung ini secara langsung atau memiliki ekstensi, tetapi perinciannya akan khusus untuk basis data (dalam jawaban mereka , Flater menunjukkan sintaks untuk SQL server).

Jika Anda perlu mengimplementasikan kueri tersebut di dalam aplikasi Anda, Anda bisa menerapkan struktur data yang memungkinkan kueri spasial, misalnya Pohon kd . Ini seperti pohon pencarian biner, kecuali bahwa setiap tingkat partisi pohon pada dimensi koordinat yang berbeda. Ini memungkinkan Anda untuk membatasi pencarian ke kandidat yang layak yang lebih kecil. Secara efektif, Anda menerjemahkan pencarian Anda "radius 10 km" menjadi batas untuk setiap dimensi koordinat, dan kencangkan batas saat Anda berulang ke pohon.

Ya, ada cara yang lebih baik. Anda perlu menggunakan indeks spasial . Indeks ini mengatur metadata tentang geometri untuk menyaring geometri jauh dengan sangat cepat, menghemat banyak siklus CPU dengan menghindari perhitungan yang Anda gambarkan. Anda tidak perlu repot menerapkannya sendiri karena semua basis data relasional utama menyediakan tipe geometri spasial dan indeks untuk digunakan.

• PostGIS (ekstensi GIS untuk PostgreSQL) menggunakan R-Trees: http://postgis.net/docs/using_postgis_dbmanagement.html#idm2246 (Jenis GiST)
• SQL Server menggunakan indeks kotak: https://docs.microsoft.com/en-us/sql/relational-databases/spatial/spatial-indexes-overview?view=sql-server-2017
• Oracle menggunakan R-Trees: https://docs.oracle.com/database/121/SPATL/creating-spatial-index.htm
• MySQL menggunakan R-Trees: https://dev.mysql.com/doc/refman/8.0/en/optimizing-spatial-analysis.html

Yang ingin Anda lihat adalah kueri "dalam jarak" (kueri untuk geometri dalam jarak tertentu dari beberapa geometri lain). Ini sangat standar dan sangat banyak masalah yang dipecahkan dan dimungkinkan di semua database di atas (dan dibangun menjadi beberapa):

• PostGIS: ST_DWithin
• SQL Server: STDistance(Tidak jelas bahwa penggunaan indeks pada versi geografi 3D dari fungsi ini didukung)
• Oracle: SDO_WITHIN_DISTANCE(Ini tidak mengatakan secara eksplisit bahwa itu akan memicu penggunaan indeks. Saya akan memeriksa rencana permintaan. Anda mungkin perlu menerapkan suatu SDO_FILTERuntuk mendapatkannya untuk menggunakan indeks.)
• MySQL: Masih mencari tahu ini.

Solusi untuk memicu penggunaan indeks

Dalam kasus terburuk di mana Anda memiliki masalah dalam mendapatkan sistem untuk menggunakan indeks spasial dengan pertanyaan ini, Anda bisa menambahkan filter tambahan. Anda akan membuat kotak pembatas persegi dengan sisi panjang 2 * (jarak pencarian) berpusat di titik pencarian Anda dan membandingkan kotak pembatas kotak geometri dengan yang sebelum memeriksa jarak yang sebenarnya. Itulah yang dilakukan PostGIS di ST_DWithinatas secara internal.

Jarak dalam GIS

Meskipun indeks spasial sangat fantastis dan benar-benar solusi tepat untuk masalah Anda, perhitungan jarak bisa menjadi rumit secara logis. Khususnya, Anda perlu khawatir tentang proyeksi apa (pada dasarnya semua parameter untuk sistem koordinat) data Anda disimpan. Sebagian besar proyeksi 2D (hal-hal selain sistem koordinat sudut seperti berbagai proyeksi lat / long) mendistorsi panjang secara signifikan. Sebagai contoh, proyeksi Web Mercator (yang digunakan oleh Google, Bing, dan setiap penyedia peta dasar utama lainnya) memperluas area dan jarak yang semakin jauh seiring lokasi semakin jauh dari garis khatulistiwa . Saya mungkin salah karena saya tidak dididik secara resmi dalam GIS, tetapi yang terbaik yang pernah saya lihat untuk proyeksi 2D adalah beberapa yang spesifik yang menjanjikan jarak yang benar dari suatusatu, titik konstan di seluruh dunia. (Tidak, tidak praktis menggunakan proyeksi berbeda untuk setiap permintaan; itu akan membuat indeks Anda tidak berguna.)

Intinya adalah Anda harus memastikan matematika Anda akurat. Cara paling sederhana untuk melakukannya dari perspektif pengembangan adalah dengan menggunakan proyeksi sudut (Ini sering disebut sebagai "geografis.") Dan fungsi yang mendukung melakukan matematika menggunakan model spheroid, tetapi perhitungan ini sedikit lebih mahal daripada rekan-rekan 2D. dan beberapa DB mungkin tidak mendukung pengindeksan mereka. Jika Anda bisa mendapatkan kinerja yang dapat diterima menggunakannya, mungkin itulah cara yang harus dilakukan. Pilihan umum lainnya adalah proyeksi regional (seperti zona UTM) yang mendapatkan jarak dan area yang cukup dekat untuk dikoreksi jika data Anda terbatas pada bagian tertentu dunia. Apa yang terbaik untuk aplikasi Anda akan tergantung pada kebutuhan spesifik Anda,

Ini berlaku bahkan jika Anda tidak menggunakan indeks spasial bawaan. Data Anda memiliki beberapa proyeksi terlepas dari teknologi atau teknik apa yang saat ini Anda gunakan atau gunakan di masa depan, dan saat ini sudah memengaruhi setiap pertanyaan dan perhitungan yang Anda buat.

Saya setuju bahwa jika mungkin menggunakan dukungan khusus dalam database akan menjadi cara yang paling masuk akal untuk melakukan ini.

Namun jika saya harus melakukan ini pada database tanpa dukungan spesifik, saya akan mulai dengan meminta kuadrat yang melingkupi misalnya lingkaran (y> (y1 - rad)) DAN (y <(y1 + rad)) DAN (x> ( x1 - rad)) AND (x <(x1 + rad)). Dengan asumsi poin Anda memiliki kueri distribusi yang hampir merata untuk sebuah bujur sangkar akan memberi Anda kecocokan sejati Anda plus sekitar 30% kecocokan salah tambahan. Anda kemudian dapat menyisihkan kecocokan palsu.