Có một thuật toán để tìm các điểm lân cận chỉ sử dụng tọa độ cực không?

Question

Giả sử tôi có vectơ các điểm là tọa độ cực.

Giả sử một trong những điểm đó hoạt động như một đầu dò mà tôi muốn tìm tất cả các điểm khác trong một khoảng cách nhất định.

Có một thuật toán để thực hiện việc này mà không chuyển đổi chúng sang dạng Descartes không?

Answer 1

Bạn đang tìm khoảng cách cho các tọa độ cực. Bạn có thể tìm công thức trong số này link.

Khoảng cách giữa các điểm (r1, a1) và (r2, a2) là:

D = sqrt(r1*r1 + r2*r2 - 2*r1*r2*cos(a1-a2)) 

Answer 2

Hãy cẩn thận, nếu bạn có kế hoạch mở rộng quy mô thuật toán của bạn đến nhiều điểm, thăm dò cho điểm lân cận là tốt hơn done sử dụng chỉ số không gian . Tôi không nhận thức được sự tồn tại của các chỉ mục không gian bằng cách sử dụng các tọa độ cực, và tôi chắc chắn rằng chúng sẽ có một chút phức tạp để thực hiện/sử dụng. Vì vậy, nếu bạn có:

• rất nhiều điểm,
• thăm dò thường xuyên hơn điểm di chuyển,

tự hỏi mình câu hỏi liệu bạn nên sử dụng tọa độ Descartes và một chỉ số không gian.

Làm toán cho mình theo trường hợp sử dụng điển hình của bạn:

1. Sử dụng Descartes cùng tọa độ cực:

   • Chuyển đổi cực đến Descartes được thực hiện chỉ khi một điểm di chuyển, và liên quan đến hai lượng giác chức năng;
   • Tìm điểm gần nhất với khoảng cách nhất định đến điểm khác có thể được thực hiện trong thời gian O (1) (tùy thuộc vào khoảng cách trung bình, kích thước của chỉ số không gian, số điểm ...) và không liên quan gì khác hơn cho biết thêm/nhân (không phải ngay cả căn bậc hai, bạn so sánh khoảng cách bình phương).

2. Chỉ sử dụng tọa độ cực:

   • Quét tất cả các điểm w/o chỉ số không gian là O (n);
   • Điều này liên quan đến một hàm lượng giác trên mỗi so sánh (do đó n các cuộc gọi trig trên mỗi đầu dò).

Hãy lưu ý rằng giàn có nhiều tốn kém trong thời gian tính toán.