極座標のみを使って近くの点を見つけるアルゴリズムはありますか？

Question

極座標としての点のベクトルがあるとします。

これらのポイントの1つが、ある距離内の他のすべてのポイントを検索するためのプローブとして機能するとします。

カルテス形式に変換せずにこれを行うアルゴリズムはありますか？

Answer 1

極座標の距離を探しています。あなたはこのlinkの数式を見つけることができます。

ポイント（R1、A1）との間の距離（R2、a2）は次のとおりです。

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

Answer 2

あなたは、多くの点にごアルゴリズムをスケールアップすることを計画している場合、近くのポイントをプロービング良く行われ、注意してください空間インデックスを使用します。私は極座標を使用した空間インデックスの存在を認識していませんし、実装/使用するには少し複雑かもしれません。だから、持っている場合：

• ポイントがたくさん、
• プローブよりも頻繁に移動するポイント、

が自分で使用すると、直交座標と空間インデックスを使用する必要があるかどうか質問をします。極座標と並んデカルト使用

1. ：デカルトに極性変換

   • 場合にのみポイントが移動して行われ、2つの三角を伴う

     あなたの典型的なユースケースに応じて数学を自分で行います機能;

   • O（1）時間内に特定の距離に最も近い点を見つけることができます（平均距離、空間インデックスのサイズ、点の数などによる）加算/乗算以外（平方根でさえも、距離の二乗を比較します）。

2. 使用極座標のみ：すべての点に対して

   • スキャンW /空間インデックスは、O（N）であり、Oであり;
   • これには、比較ごとに1つの三角関数が含まれます（したがって、1プローブにつきn trig呼び出し）。

トリグは、計算時間に高価流血していることに注意してください。