javaのTreeMapを使用して最小スパニングツリーを構築する

Question

私は2次元平面上の点の数を追跡する必要があるプロジェクトに取り組んでいます。特定のポイントが他のポイントの近接を検出できるようにする機能を追加する必要があります。私は直ちに最も近いペアの問題を考え、おそらく私は最小スパニングツリーを構築する必要があると思った。

最初の問題は、これらの点は常に座標を更新することであり、これを実行するのが妥当かどうかは疑問でした。

他の問題は、私はこれのためにサードパーティのライブラリを使用することはできませんので、jgraphやjungはありません。私は与えられたライブラリだけを使って最小スパニングを構築する方法があるのだろうかと思っていました。 TreeMapを使用できますか？これを最初から行う必要がありますか？

Answer 1

あなたがやっているように聞こえます最近隣のクエリです。それはあなたが別のポイントに最も近いポイント（またはポイント）を見つけようとする場所です。素朴な解法では、点のリストを保存し、距離式を使ってそれらの点を繰り返して、どれが最も近いかを調べることができます。しかし、クエリーをより迅速に実行するには、これらの種類のクエリーを可能にする空間データ構造を使用することが必要です。私はKDツリーを提案します。 Javaには標準ライブラリにKDツリー実装が付属していませんので、実装する必要があります。

TreeMapは、Mapインターフェイスの実装で、値をキーで入力したり取得したりすることができます。最小限のスパンニングツリーを生成するために何かを書く場合は、それを自分で行う必要があります。位置は、彼らが変更されたすべてのオブザーバーを更新することができます変更点とPointオブジェクトを持つことになり、これを行うのは非常にオブジェクト指向の方法で

Answer 2

はその後、Observer Pattern使用し、他のすべての点のオブザーバーとして自身を登録します。通知がObserversに送信される前に、変更が発生した頻度や変更の必要性のしきい値を制御できます。あなたは「ある種の」ポイントは近接性を追跡する必要があると言って以来、これはうまくいくでしょう。