私は、ランダムな州の地図を作成するゲーム (Risk や Diplomacy 風) に取り組んでいます。その地図を作成するには、まず一連の半ランダムなポイントを生成し、次にそれらのポイントの Delaunay 三角形分割を計算します。
それが終わったら、今度は州境の出発点となる点のボロノイ図を作成しようとしています。この時点での私のデータは (しゃれではありません)、元の点の系列とドロネー三角形の集合で構成されています。
ウェブ上でこれを行う方法はいくつか見てきましたが、そのほとんどは Delaunay の導出方法に関係しています。Delaunay に統合する必要がなく、データのみに基づいて機能するものを見つけたいと思っています。それができない場合は、最適な速度ではなく、相対幾何学の初心者でも理解できるものを探しています。よろしくお願いします。
ベストアンサー1
ボロノイ図は、ドロネー三角形分割の双対グラフです。
- したがって、ボロノイ図の辺はドロネー三角形分割の辺の垂直二等分線に沿っているので、それらの線を計算します。
- 次に、隣接するエッジの交点を見つけることで、ボロノイ図の頂点を計算します。
- 最後に、エッジは、対応する頂点の間にある計算された線のサブセットになります。
正確なコードは、2 つの図に使用している内部表現によって異なることに注意してください。