Tôi nên sử dụng thuật toán lập chỉ mục không gian nào?

Question

Tôi muốn triển khai một số cấu trúc dữ liệu lập chỉ mục không gian cho số MKAnnotations của mình. Hiện tại nó rất chậm khi tôi cố gắng lọc chúng dựa trên tiêu chí khoảng cách (3-4 nghìn vị trí, hiện tại cực kỳ chậm với một đơn giản là đôi for ...).

Tôi muốn tạo các cụm MKAnnotations, để quyết định xem cụm này có gần với cụm khác không. Ngoài ra, các vị trí này nằm trong một trật tự phần nào (sáng tạo) và một chức năng "trước"/"tiếp theo" sẽ là cần thiết để "nhảy" giữa (đây không phải là điều bắt buộc). Tôi đã đọc về các cấu trúc kd-tree và r-tree và cả hai dường như đáp ứng tùy chọn lọc/phân cụm nhanh/khoảng cách lân cận để lọc/phân nhóm, nhưng tôi không chắc chắn lựa chọn nào tốt nhất cho tôi hoặc nếu có các tùy chọn khác. Tôi nên sử dụng thuật toán/cấu trúc dữ liệu nào?

Cập nhật: Tôi lưu trữ các vị trí này trong cơ sở dữ liệu lõi dữ liệu, chúng đại diện cho một đường dẫn. Khi bản đồ được mở, chúng được lấy vào một mảng và sau đó tôi chỉ sử dụng mảng đó để tính toán khoảng cách và tạo chú thích. Khi người dùng di chuyển/phóng to bản đồ, tôi lặp lại chúng và quyết định những gì cần phải được thay đổi trên bản đồ, vì vậy nó là kinda tĩnh toàn bộ công cụ. Như tôi đã hiểu, nếu tôi muốn sử dụng một cái cây, tôi có thể lưu trữ các vị trí đó và khi zoom/di chuyển xảy ra, tôi chỉ tìm kiếm thông qua nó và có được những cái ở khu vực mới. Điều này có đúng không?

Ngay cả trong trường hợp động, khi tôi có thể thêm vị trí mới vào mảng này, nó sẽ là một lần chèn và nó hiếm khi xảy ra.

Answer 1

Phụ thuộc rất nhiều vào mẫu cách sử dụng của bạn (cách viết, ví dụ, trong bộ nhớ hoặc trên đĩa) và cách dữ liệu của bạn trông như thế nào (đó là cách phân phối).

Cây R là tốt vì chúng là cân bằng và cho phép cập nhật. Các R * -tree trong kinh nghiệm của tôi rõ ràng là tốt hơn so với các biến thể khác vì chiến lược chia nó có. Lợi ích là nó tạo ra nhiều trang vuông hơn các chiến lược khác, do đó, đối với nhiều truy vấn, bạn sẽ cần phải quét ít trang hơn.

kd-cây rất tốt nếu bạn ở trong bộ nhớ và tĩnh. Cập nhật chúng rất xấu, bạn sẽ cần phải xây dựng lại chỉ mục khá thường xuyên.

Và nếu dữ liệu của bạn không thay đổi thường xuyên, việc tải hàng loạt cho R-tree hoạt động rất tốt. Bạn có thể làm Sắp xếp-Ngói-đệ quy tải hàng loạt, mà về cơ bản yêu cầu (một phần) sắp xếp dữ liệu của bạn trên X và Y luân phiên, vì vậy phải mất một mức thấp O(n log n) để xây dựng cây; rất giống với tải hàng loạt kd-tree, ngoại trừ việc bạn chia nhiều lần thay vì tách nhị phân. Điều này rất phổ biến.

Ngoài ra, bạn có thể theo dõi số đối tượng trong mỗi trang. Khi hiển thị mọi thứ trên bản đồ, bạn có thể muốn dừng sớm khi trang hiển thị quá nhỏ trên màn hình (tức là nhỏ hơn điểm đánh dấu). Tại thời điểm này, bạn sẽ không quét trang đó, nhưng chỉ lấy số lượng đối tượng và hiển thị dưới dạng điểm đánh dấu cụm cho đến khi người dùng phóng to.

Đối với dữ liệu 2D, với miền có giá trị giới hạn, không bỏ qua đơn giản nhiều thứ. Quadtrees cũng có thể hoạt động tốt! Đơn giản có thể làm cho nó dễ dàng hơn nhiều để tối ưu hóa mọi thứ. Hoặc một cách tiếp cận lưới điện cổ điển. Nếu người dùng của bạn có xu hướng truyền bá chú thích của họ trong một khu vực (và không đặt tất cả chúng vào một nơi), bạn có thể tính toán số nguyên x, y tọa độ lưới và sau đó băm chúng và tạo danh sách cho mỗi ô lưới.

Answer 2

Tôi không nhà phát triển iOS, nhưng tôi nhìn qua các tài liệu và các mặt hàng này:

MKMapView.annotationsInMapRect:

Trả về đối tượng chú thích nằm trong hình chữ nhật bản đồ xác định.

(NSSet *)annotationsInMapRect:(MKMapRect)mapRect

thông số

• mapRect: Các phần của bản đồ mà bạn muốn tìm kiếm chú thích.

Return Value Tập hợp các đối tượng chú thích nằm trong mapRect.

Thảo luận Phương pháp này cung cấp cách nhanh để truy xuất đối tượng chú thích trong một phần cụ thể của bản đồ. Phương pháp này nhanh hơn nhiều so với thực hiện tìm kiếm tuyến tính của các đối tượng trong thuộc tính chú thích.

Điều này cho thấy rằng NKMapView đã sắp xếp chú thích trong cấu trúc chỉ mục không gian. Phương pháp này có đáp ứng nhu cầu của bạn không?

Nếu không, tôi sẽ tìm các triển khai mã nguồn mở hiện có của bất kỳ cấu trúc chỉ mục không gian 2D nào và chọn cấu trúc có tài liệu tốt nhất, giao diện sạch nhất, v.v.Nếu bạn cần phải viết các mẫu mã đầu, tôi nghĩ rằng một quadtree sẽ là dễ nhất để thực hiện. Mặt khác, the Wikipedia article on R-tree dường như được nhắm mục tiêu cụ thể hơn để lập bản đồ so với cây K-D hoặc Quadtree.