30

私は州のランダム マップを作成するゲームに取り組んでいます (リスクまたは外交)。そのマップを作成するには、まず一連の半ランダムな点を生成し、次にそれらの点の Delaunay 三角形分割を計算します。

これが完了したら、州境の開始点として機能するポイントのボロノイ図を作成しようとしています。この時点での私のデータ (しゃれは意図していません) は、元の一連の点と Delaunay 三角形のコレクションで構成されています。

ウェブ上でこれを行う方法をいくつか見てきましたが、そのほとんどは Delaunay がどのように導出されたかに関係しています。Delaunay に統合する必要はなく、データだけに基づいて機能するものを見つけたいと思っています。それに失敗すると、最適な速度とは対照的に、相対幾何学​​の初心者にわかりやすいものを探しています。ありがとう！

4

4 に答える 4

20

ボロノイ図は、ドロネー三角形分割の双対グラフです。

  • したがって、ボロノイ線図の辺はドローネ三角形分割の辺の垂直二等分線に沿っているので、それらの線を計算します。
  • 次に、隣接するエッジの交点を見つけて、ボロノイ図の頂点を計算します。
  • 最後に、エッジは、対応する頂点の間にある、計算した線のサブセットです。

正確なコードは、2 つの図で使用している内部表現によって異なることに注意してください。

于 2008-09-17T16:59:59.000 に答える
9

最適な速度が考慮されない場合、次の疑似コードは難しい方法でボロノイ図を生成します。

for yloop = 0 to height-1
  for xloop = 0 to width-1

    // Generate maximal value
    closest_distance = width * height

    for point = 0 to number_of_points-1
      // calls function to calc distance
      point_distance = distance(point, xloop, yloop)

      if point_distance < closest_distance
        closest_point = point
      end if
    next

  // place result in array of point types
  points[xloop, yloop] = point

  next
next

「ポイント」クラスまたは構造があると仮定して、それらにランダムな色を割り当てると、出力を表示するとおなじみのボロノイ パターンが表示されます。

于 2008-09-17T17:13:42.150 に答える
2

このスレッドを私自身の同様の質問への回答のソースとして使用しようとした後、Fortuneのアルゴリズムは、おそらく最も人気があり、したがって最も文書化されているため、最も理解しやすいことがわかりました。

Fortuneのアルゴリズムに関するウィキペディアの記事では、C、C＃、およびJavascriptのソースコードへの新しいリンクが保持されています。それらはすべて一流であり、美しい例が付属していました。

于 2012-10-02T14:58:15.200 に答える
0

各 Delaunay 三角形には、ボロノイ図の 1 つの点が含まれています。

この点は、各三角形の 3 つの垂直二等分線の交点を見つけることで計算できます。

ボロノイ図は、この一連の点を、それぞれが最も近い 3 つの隣接点と結び付けます。(各隣人はドローネ三角形の一辺を共有します)

エッジケースにどのようにアプローチする予定ですか?

于 2008-09-17T17:14:04.707 に答える