Saya ditanyai dalam tes wawancara. Saya baik-baik saja dalam ujian tetapi tidak cukup tahu untuk menjawab pertanyaan ini. Saya ingin tahu struktur data apa yang dapat saya gunakan untuk meminta data dengan cepat.
Pada dasarnya idenya adalah akan ada bagian jalan (garis, terdiri dari titik) yang disimpan dalam beberapa jenis struktur data. Harus cepat menanyakan bagian jalan (atau titik) mana yang berada dalam jarak tertentu dari satu titik (radius).
Jawaban:
Cara khas untuk menyimpan data geografis adalah dengan struktur data spasial seperti R-tree (atau beberapa varian, seperti R + tree, R * tree, dll.) Ini adalah bagaimana tipe data geografis biasanya diimplementasikan dalam GIS-mampu RDBMS. (Saya tahu Microsoft SQL Server 2008 dan PostGIS menggunakan R-tree untuk tipe geografis.) Mereka memenuhi semua persyaratan dasar yang telah Anda jelaskan, dan secara sepintas mendukung persimpangan, lokasi, jarak, dan tipe kueri lainnya.
Bergantung pada tipe data, Anda juga dapat menemukan hal-hal seperti kD-tree, quad-tree, octrees, hierarki volume terikat (termasuk tree box bounded aligned axis), dll. Yang umum digunakan. Ini sebenarnya jauh lebih umum di game 3D, karena ukuran dan bentuk objek lebih relevan dengan kueri persimpangan. Mereka lebih jarang digunakan untuk GIS daripada pohon-R.
sumber
Berbagai jenis operasi pada data peta akan memerlukan format penyimpanan yang berbeda untuk hasil yang optimal. Pertimbangkan, misalnya, tiga tugas berikut:
Perbedaan persyaratan cukup besar sehingga kecuali seseorang perlu mengakomodasi perubahan "langsung" pada peta, ia kemungkinan akan lebih baik dengan menyimpan tiga salinan data yang terpisah - masing-masing dioptimalkan untuk salah satu tugas di atas - daripada mencoba untuk datang dengan format yang dapat menangani ketiga tugas dengan baik.
sumber