ボロノイ図を作成するためのFortunes アルゴリズムを実装する必要があります。
アルゴリズムの重要な部分は、「Beach Line Data Structure」と呼ばれるデータ構造です。
これは、AVL に似たバイナリ バランス ツリーですが、データがリーフにのみ格納されるという点で異なります (他にも違いがありますが、質問には重要ではありません)。
実装方法がわかりません。明らかに、AVL を「そのまま」使用することは機能しません。これは、AVL ツリーのリーフ ノードをバランスさせると、内部ノードになり、その逆になる可能性があるためです。
ウィキペディアで他の既知のデータ構造も調べてみましたが、ニーズに合ったものはありませんでした。連結リストでこれを行ういくつかの実装を見てきましたが、連結リストの検索は O(n) であり、アルゴリズムを効率的にするには O(log n) である必要があるため、これは良くありません。
葉は確かに (単一の) ポイントを格納し、イベント構造の内部ノード ( 「ビーチ ライン ツリー」 ) は、放物線/円弧が隣り合っているポイントの順序付けられたタプルを格納します。点P a が形成する放物線が、 P bによって形成される放物線の左側にある場合(およびこれら 2 つの放物線が交差する場合)、内部ノードには順序付きタプル(P a , P b )が格納されます。
明らかに、AVL を「そのまま」使用することは機能しません。これは、AVL ツリーのリーフ ノードをバランスさせると、内部ノードになり、その逆になる可能性があるためです。
さまざまなタイプのオブジェクトを AVL ツリーに格納することに不安がある場合は、リーフもタプルとして格納するのが簡単な方法です。したがって、点P jを葉として保存するのではなく、タプル(P j , P j )を保存します。葉としてのP jがイベント ツリー (ビーチ ライン) から消え、その親が(P i , P j )である場合、単純に親を(P j , P j )に変更します。もちろん、その親も必要です。(P j , P ? )から(P私、P ？)など。通常の AVL ツリーと同様に、ツリーをたどり、変更および/または再調整が必要な内部ノードを変更します。
アルゴリズムの適切な実装は、SOの回答に簡単に書き留めることができないことに注意してください（少なくとも、私ではありません！）。アルゴリズムで使用されるデータ構造の説明を含む、アルゴリズム全体の適切な説明については、Mark de Berg らによる Computational geometry: algorithms and applications を参照してください。. 第 7 章は、ボロノイ図のみを扱います。