R Tree 50.000 foot tổng quan?

Question

Tôi đang làm việc trên một dự án trường học liên quan đến việc tham gia một điểm lat/long và tìm năm điểm gần nhất trong danh sách địa điểm đã biết. Danh sách sẽ được lưu trữ trong bộ nhớ, với báo trước rằng chúng ta phải chọn một "cấu trúc dữ liệu thích hợp" - nghĩa là chúng ta không thể lưu trữ tất cả các vị trí trong một mảng và so sánh từng khoảng cách một theo kiểu tuyến tính. Giáo viên đề xuất nhóm dữ liệu địa điểm của Nhà nước Hoa Kỳ để ngăn tính toán khoảng cách cho các địa điểm rõ ràng là quá xa. Tôi nghĩ tôi có thể làm tốt hơn.

Từ nghiên cứu trực tuyến của tôi có vẻ như một R-Tree hoặc một trong các biến thể của nó có thể là một giải pháp gọn gàng. Thật không may, câu đó là như xa như tôi đã nhận được với sự hiểu biết kỹ thuật thực tế, như văn học chỉ đơn giản là quá dày đặc cho người đứng đầu không học thuật của tôi.

• ai đó có thể cho tôi một cái nhìn tổng quan thực sự cao những gì quá trình này là cho Populating một R-Tree với dữ liệu lat/dài, và sau đó đi qua cây để tìm những 5 láng giềng gần nhất của một điểm nhất định? Ngoài ra, dự án nằm trong C, và tôi không phải phát minh lại bánh xe về điều này, vì vậy nếu bạn đã sử dụng triển khai C nguồn mở hiện tại của R Tree, tôi sẽ quan tâm đến trải nghiệm của bạn.

UPDATE:This blog post mô tả một thuật toán tìm kiếm đơn giản cho một không gian khu vực phân (giống như một quadtree PR). Hy vọng rằng sẽ giúp một người đọc trong tương lai.

Answer 1

Bạn có cân nhắc cấu trúc dữ liệu thay thế không? Tôi tin rằng, thay vì R-tree, một điểm Quadtree sẽ hiệu quả hơn cho nhu cầu của bạn. Spatial Index Demos cung cấp một số bản trình diễn cho danh sách các cấu trúc dữ liệu có thể bao gồm R-tree và Point Quadtree. Hy vọng nó cung cấp cho một cái nhìn sâu sắc.

Answer 2

Quad Trees

Một cây quad mất một hình vuông của không gian và phân chia nó thành bốn trẻ em với một nửa kích thước dọc theo trục X và Y.

+---+---+ 
| | | Each square is a child 
| | | of the parent; when you 
+---+---+ get to leaves a node has 
| | | a single point or a list 
| | | of points. 
+---+---+ 

Cấu trúc dữ liệu này đệ quy và bạn tìm kiếm điểm bằng cách kiểm tra xem con nào giữ điểm cho đến khi bạn đến lá. Một lá hoặc có một thành viên (điểm với X, Y coords) hoặc một danh sách các thành viên, tùy thuộc vào việc thực hiện. Nếu bạn điền vào một nút bạn chia nó thành 4 và phân phối các trẻ em. Về cơ bản, cấu trúc dữ liệu là một khái quát hóa của một cây nhị phân, vì vậy nó không nhất thiết phải cân bằng.

Cân bằng một cây quad thể không cần thiết cho mục đích của bạn và là trái như một bài tập cho người đọc - Thử tìm kiếm trên web cho 'cây quad cân bằng'

Lưu ý rằng cấu trúc dữ liệu này không thể ghi chỉ số có thể chồng lên nhau, nhưng nếu bạn chỉ lưu trữ các điểm thì đây không phải là vấn đề.

Tìm hàng xóm gần nhất trong một cây quad

Off đỉnh đầu của tôi, đây là một thuật toán nhanh chóng và bẩn cho việc tìm kiếm các 'n' láng giềng khu vực gần điểm của bạn. Nó không nhất thiết phải hiệu quả tối ưu, nhưng nó sẽ khá đơn giản để thực hiện. Nếu ai đó có liên kết đến trang web tốt hơn, vui lòng đăng liên kết đó trong nhận xét hoặc câu trả lời.

• Xác định vị trí các nút cây quad chứa quan điểm của bạn, giữ một danh sách các cha mẹ của nó.

• Đẩy tất cả các điểm trong nút vào một hàng đợi ưu tiên dựa trên khoảng cách của họ từ thời điểm cơ sở của bạn (tức là bằng độ dài của cạnh huyền mỗi định lý Pythagoras'). Tùy thuộc vào về việc triển khai có thể có một hoặc nhiều nút trên mỗi nút. Để thực hiện thực hiện một hàng đợi ưu tiên cấu trúc dữ liệu, hãy tra cứu 'nhị phân đống'.

• Nếu bất kỳ điểm 'n' nào ở xa thì các cạnh của hộp giới hạn, thêm nội dung của các hàng xóm của nó. ví dụ: Nếu điểm cơ sở của bạn gần với cạnh của hộp giới hạn, có thể các nút cây lân cận có thể chứa các điểm gần với các điểm được tìm thấy trong hộp giới hạn của bạn. Bạn sẽ cần phải sao lưu cây để làm điều này, đó là lý do tại sao bạn cần phải theo dõi các nút cha của bạn.

• Khi tất cả các điểm gần nhất 'n' gần hơn các cạnh của hộp giới hạn của bạn, bạn biết rằng có thể không có thể là hàng xóm bạn đã bỏ lỡ. Do đó, các điểm gần nhất trong hộp này phải là 'n' hàng xóm gần nhất của bạn.