2D 空間でランダムな点を生成したいのですが、この点は平面グラフのノードになります (ガブリエル グラフアルゴリズムまたは RNG を使用して構築されます)。
これを行うためにJavaコードを書きましたが、解決するのが難しい問題が2つあります。
1) グラフのすべてのエッジが特定のしきい値より長くないことが必要です
2）グラフの面を知りたい後、面はエッジで接続されたノードの集まりです。面には他のノードは含まれません。下の画像では、顔はラベル (F1、F2...) によって署名されています。
これら2つのことを行う方法は？いくつかのアルゴリズム？すでに知られている方法はありますか？
以下に、作成する必要があるグラフの例を示します
ポイント数の多少の変動を許容できる場合は、Gabriel グラフ アルゴリズムをインクリメンタルに変更し (ほとんどの労力は Delaunay アルゴリズムをインクリメンタルにすることです)、エッジが長すぎる場合はいつでもランダムなポイントを挿入できます。その辺を直径とする円。
平面グラフの最も便利なデータ構造はエッジ中心です。たとえば、二重接続エッジ リストと四角形の表現です。Delaunay ステップでこのタイプのデータ構造をまだ使用していない場合 (なぜ使用しないのか想像できません)、各頂点の外向き接続を角度で並べ替えることができます。そこから、ハーフエッジを受け取り、同じ面の次のハーフエッジを反時計回りの順序で返す関数を実装するのは簡単です。ここで、すべてのハーフエッジを反復し、まだ訪れていないハーフエッジごとに、開始した場所に戻るまで面の周りを反復します。内側の反復のすべてのハーフエッジに 1 つの面としてラベルを付けます。
