Tôi đã hai ArrayList, kiểu dữ liệu Double, 1.latitudes 2. kinh độ, từng đã hơn 200 yếu tốTìm tọa độ gần nhất trong một mảng?
nói tôi cung cấp một tọa độ kiểm tra ngẫu nhiên, nói (1.33, 103,4), định dạng là [vĩ độ , kinh độ]
có thuật toán nào để dễ dàng tìm điểm gần nhất, hoặc tôi phải tính toán lực lượng vũ phu mọi điểm có thể, tìm cạnh huyền, và sau đó so sánh hơn 200 hypotenuses để trả lại điểm gần nhất? thanks
Nếu mảng của bạn được sắp xếp, bạn có thể sử dụng tìm kiếm nhị phân để tìm vị trí của một điểm được yêu cầu trong mảng. Sau khi bạn tìm thấy chỉ số, bạn nên kiểm tra bốn gần bằng điểm để tìm gần nhất.
1) Giả sử bạn có hai mảng được sắp xếp kinh độ khôn ngoan và vĩ độ khôn ngoan
2) Bạn tìm kiếm một đầu tiên và tìm thấy hai điểm lân cận
3) Sau đó bạn tìm kiếm một thứ hai và tìm thấy hai điểm nhiều hơn
4) Bây giờ bạn có từ hai đến bốn điểm (kết quả có thể giao nhau)
5) Những điểm này sẽ tạo thành một hình vuông xung quanh điểm đích
6) Tìm điểm gần nhất
Sắp xếp mảng điểm dọc theo một trục. Sau đó, xác định vị trí điểm trong mảng gần nhất với điểm cần thiết dọc theo trục này và tính toán khoảng cách (sử dụng bất kỳ số liệu nào phù hợp với cấu trúc liên kết và tỷ lệ sự cố).
Sau đó, tìm kiếm dọc theo mảng theo cả hai hướng cho đến khi khoảng cách đến các điểm này lớn hơn kết quả tốt nhất từ trước đến nay. Điểm khoảng cách ngắn nhất là câu trả lời.
Điều này có thể dẫn đến việc phải tìm kiếm toàn bộ mảng và là một dạng của Branch and bound bị ràng buộc bởi hình dạng của sự cố. Nếu các điểm được phân phối hợp lý xung quanh điểm bạn đang tìm kiếm, thì quá trình quét sẽ không yêu cầu nhiều thử nghiệm.
Chỉ số không gian thay thế (như quad-tree) sẽ cho kết quả tốt hơn, nhưng số điểm nhỏ của bạn sẽ làm cho chi phí thiết lập trong việc chuẩn bị chỉ mục lớn hơn nhiều so với một loại đơn giản. Bạn sẽ cần phải theo dõi các thay đổi vị trí gây ra bởi các loại như mảng khác của bạn sẽ không được sắp xếp theo cùng một cách. Nếu bạn thay đổi dữ liệu thành một dãy điểm, thì sắp xếp sẽ sắp xếp lại toàn bộ các điểm cùng một lúc.
không đúng giá trị lat (hoặc dài) gần nhất nên được chọn để tìm kiếm trên trục dài (hoặc lat), trên thực tế bạn có thể ở trên một dòng (hoặc dài) dài nhưng cách xa dọc (hoặc lat) giá trị
cách vì vậy tốt nhất là để tính toán tất cả khoảng cách và sắp xếp chúng
Cách tiếp cận để chọn điểm gần nhất dọc theo một trục là điểm bắt đầu cho tìm kiếm. Nó ít nhất là giảm thiểu khoảng cách dọc theo một trục. Các đầu dò tiếp theo xa hơn (theo cả hai hướng) sẽ xác định điểm gần nhất. Việc lựa chọn chỉ số khoảng cách phụ thuộc vào độ cong của khu vực đang được xem xét. – Pekka
Nếu bạn làm tính toán tất cả hypotenuses, bạn có thể tính toán khoảng cách và thực hiện min (khoảng cách) logic tất cả trong một vòng lặp. Ngoài ra, tất cả các điểm của bạn nên có vị trí địa lý gần nhau để bạn có thể coi khu vực này là đồng bằng, nếu không bạn cần tính đến độ cong của Trái đất. –
định nghĩa của bạn về khoảng cách là gì?"hypothenuse" là một thuật ngữ từ hình học phẳng, nhưng việc bạn sử dụng "kinh độ" và "vĩ độ" dường như chỉ ra các điểm nằm trên bề mặt của một hình cầu ... – meriton
Bạn đã xem R-trees chưa (https: // vi .wikipedia.org/wiki/R-tree)? Hoặc thuật toán lập chỉ mục không gian nói chung (https://en.wikipedia.org/wiki/Spatial_index#Spatial_index)? –