このような点のプロットがあります。
これらの点が形成するトラックは、円または楕円になります。上の 2 つの画像の円形トラックの中心が明らかに異なっています。
これらのトラック (円形/楕円形) の中心点を見つけるにはどうすればよいですか? 中心である (x,y) 座標を見つけたいのですが、プロットされたデータ セット内の点である必要はありません。つまり、medoid は必要ありません。
編集:また、これらの点の大部分を包む円/楕円の方程式を見つけることができる方法はありますか? 楕円トラックでは、トラック上のポイントを囲む楕円を追加しました。値は試行錯誤によって計算されました。中心も、プロットを目で見て計算されました。プログラムでこれを行うにはどうすればよいですか?
最小円問題と最小楕円問題に関する論文 (PDF ダウンロード可能) はこちらです。どちらにも O(N) アルゴリズムがあり、中心を取得できる円と面積の式を提供できるはずです。ただし、すべてのポイントを囲むことに重点を置いています。この問題を解決するには、いくつかの境界点を削除する必要があります。これもアルゴリズムから取得する必要があります。残念ながら、何が十分な解決策であるかは、ほとんどあなた次第です。
高速でシンプルなランダム化ソリューションは次のとおりです。
このアルゴリズムは、パスごとに k ～ mk の境界点を O(N) のコストで削除します。あなたの目的のために、おそらく境界点のいくつかの割合を削除したいと思うでしょう.1-25%は良い出発点のようです. このソリューションは、k が N に比べて非常に小さいことを前提としています。そうでない場合、削除するポイントが多すぎます。
最小の楕円から 1 つまたはすべての境界点を削除し、最小の楕円を再計算してから、境界点を再度削除することを繰り返したい場合は、低速ですが、おそらくより優れたアルゴリズムが役立ちます。
これを行うには、親ノードを、その子を囲む最小の楕円の境界ポイント (簡単にすばやく削除できるようにセットとして保存されるポイント) にします。境界点の最大数は k 以下にする必要があります (これは、円の場合は 3 であるのに対し、楕円の場合は 9 であると考えています)。したがって、O(k log N) のデータ構造からポイントを削除するには、影響を受ける各親 (O(log N)) に対して最小の円 (O(k)) を再計算する必要があるためです。したがって、データ構造から m ポイントを削除すると、O(mk log N) になります。また、削除されたポイントごとに楕円の面積を計算し、残りのポイントが 3 つになるまで O(Nk log N) のコストですべてのポイントを削除することを検討することもできます。その後、エリア データを分析して、どの楕円を使用する必要があるかを判断できます。簡単な結果は、作成されたすべての楕円の平均面積に最も近い面積を持つ楕円を単純に使用することですが、正確に求めるものではない場合があります。また、遅すぎる可能性もあります。その場合は、より高速なアルゴリズムのシングル パスをお勧めします。