Tôi muốn xây dựng một ứng dụng sẽ cung cấp cho bạn nhà hàng gần nhất tùy thuộc vào vị trí của bạn. Chúng tôi sẽ có cơ sở dữ liệu với tất cả POI tương ứng với nhà hàng và chúng tôi sẽ nhận vị trí của bạn bằng GPS của điện thoại của bạn ...Thuật toán tốt cho vấn đề hàng xóm gần nhất trong hai chiều là gì?
Thuật toán nào sẽ phù hợp? Tôi có thể tìm tài liệu hay về nó ở đâu?
Cảm ơn
Dưới đây là một bài thuyết trình thông tin: http://dimacs.rutgers.edu/Workshops/MiningTutorial/pindyk-slides.ppt
tôi sẽ thể sử dụng một Quadtree hoặc một Kd-tree.
Xem một số điểm chuẩn tại đây: http://www.flegg.net/brett/pubs/spatial/index.html. Nó thực sự tất cả phụ thuộc vào kích thước và phạm vi dữ liệu của bạn.
Vấn đề chính là cách bạn lưu trữ và tìm kiếm dữ liệu. Nếu bạn đang sử dụng một cơ sở dữ liệu SQL không hỗ trợ các chỉ mục không gian (hãy nói SQLite trên Android), hãy xem xét chuyển đổi dữ liệu không gian thành một đường cong tuyến tính Z-order. Các thuật toán rất đơn giản, tôi biết về (tốt, đã viết) this thực hiện.
Đó là mã tuyệt vời Thomas, chapeau! –
Thực hiện các truy vấn lân cận gần nhất trên một cơ sở dữ liệu lớn dường như không phải là điều tốt để làm trực tiếp trên android. Các máy chủ cơ sở dữ liệu là có để làm nâng nặng như thế này ở nơi đầu tiên. –
@Tim Tôi đồng ý Z-trật tự không phải là tất cả những gì tuyệt vời cho một cơ sở dữ liệu lớn. Nhân tiện, kể từ khi tôi trả lời vào năm 2010, tôi đã triển khai [R-Tree] (http://h2database.com/html/mvstore.html#r_tree), cho phép các truy vấn lân cận gần nhất hiệu quả (một khi được thực hiện) và cũng nên hoạt động trên Android. Nhưng nó không sử dụng SQLite. –