algorithm - 手続き型ゲームコンテンツの六角形内にランダムなポイントを生成する

Question

手続き型の手法を使用して、作成しているゲームのグラフィックを生成しています。

いくつかの森を生成するために、<0,0>を中心とする正六角形の領域内にランダムに木を分散させたいと思います。

これらのポイントを均一に生成するための最良の方法は何ですか？

Answer 1

六角形に適した長方形のバウンディングボックスが見つかった場合、均一にランダムなポイントを生成する最も簡単な方法は、棄却サンプリング（http://en.wikipedia.org/wiki/Rejection_sampling）です。

つまり、六角形を完全に含む長方形を見つけて、長方形内に均一にランダムな点を生成します（これは簡単で、適切な範囲の各座標に対して独立してランダムな値を生成するだけです）。ランダムな点が六角形の中にあるかどうかを確認します。はいの場合、それを保持します。いいえの場合は、別の点を描画します。

適切なバウンディングボックスを見つけることができる限り（長方形の面積は、それが囲む六角形の面積よりも一定の係数を超えてはなりません）、これは非常に高速です。

Answer 2

おそらく簡単な方法は次のとおりです。

    F ____ B
     /\  /\
  A /__\/__\ E
    \  /\  /
     \/__\/
     D     C

平行四辺形ADCO（中心はO）とAOBFを考えてみましょう。

この中の任意の点は、2つのベクトルAOとAFの線形結合として記述できます。

これらの2つの平行四辺形の点Pは

P = x * AO + y*AFまたはxAO+yAD。

where 0 <= x < 1 and 0 <= y <= 1 (we discount the edges shared with BECO).

Similarly any point Q in the parallelogram BECO can be written as the linear combination of vectors BO and BE such that

Q = xBO + yBE where 0 <=x <=1 and 0 <=y <= 1.

Thus to select a random point

we select

A with probability 2/3 and B with probability 1/3.

If you selected A, select x in [0,1) (note, half-open interval [0,1)) and y in [-1,1] and choose point P = xAO+yAF if y > 0 else choose P = x*AO + |y|*AD.

If you selected B, select x in [0,1] and y in [0,1] and choose point Q = xBO + yBE.

So it will take three random number calls to select one point, which might be good enough, depending on your situation.

Answer 3

If it's a regular hexagon, the simplest method that comes to mind is to divide it into three rhombuses. That way (a) they have the same area, and (b) you can pick a random point in any one rhombus with two random variables from 0 to 1. Here is a Python code that works.

from math import sqrt
from random import randrange, random
from matplotlib import pyplot

vectors = [(-1.,0),(.5,sqrt(3.)/2.),(.5,-sqrt(3.)/2.)]

def randinunithex():
    x = randrange(3);
    (v1,v2) = (vectors[x], vectors[(x+1)%3])
    (x,y) = (random(),random())
    return (x*v1[0]+y*v2[0],x*v1[1]+y*v2[1])

for n in xrange(500):
    v = randinunithex()
    pyplot.plot([v[0]],[v[1]],'ro')

pyplot.show()

---

A couple of people in the discussion raised the question of uniformly sampling a discrete version of the hexagon. The most natural discretization is with a triangular lattice, and there is a version of the above solution that still works. You can trim the rhombuses a little bit so that they each contain the same number of points. They only miss the origin, which has to be allowed separately as a special case. Here is a code for that:

from math import sqrt
from random import randrange, random
from matplotlib import pyplot

size = 10

vectors = [(-1.,0),(.5,sqrt(3.)/2.),(.5,-sqrt(3.)/2.)]

def randinunithex():
    if not randrange(3*size*size+1): return (0,0)
    t = randrange(3);
    (v1,v2) = (vectors[t], vectors[(t+1)%3])
    (x,y) = (randrange(0,size),randrange(1,size))
    return (x*v1[0]+y*v2[0],x*v1[1]+y*v2[1])

# Plot 500 random points in the hexagon
for n in xrange(500):
    v = randinunithex()
    pyplot.plot([v[0]],[v[1]],'ro')

# Show the trimmed rhombuses
for t in xrange(3):
    (v1,v2) = (vectors[t], vectors[(t+1)%3])
    corners = [(0,1),(0,size-1),(size-1,size-1),(size-1,1),(0,1)]
    corners = [(x*v1[0]+y*v2[0],x*v1[1]+y*v2[1]) for (x,y) in corners]
    pyplot.plot([x for (x,y) in corners],[y for (x,y) in corners],'b')

pyplot.show()

And here is a picture.

alt text http://www.freeimagehosting.net/uploads/0f80ad5d9a.png

Answer 4

従来のアプローチ（任意の多角形の領域に適用可能）は、元の六角形の台形分解を実行することです。それが完了したら、次の2段階のプロセスでランダムポイントを選択できます。

1）分解からランダムな台形を選択します。各台形は、その面積に比例する確率で選択されます。

2）手順1で選択した台形のランダムな点を均一に選択します。

必要に応じて、台形分解の代わりに三角測量を使用できます。

Answer 5

Chop it up into six triangles (hence this applies to any regular polygon), randomly choose one triangle, and randomly choose a point in the selected triangle.

Choosing random points in a triangle is a well-documented problem.

And of course, this is quite fast and you'll only have to generate 3 random numbers per point --- no rejection, etc.

Update:

Since you will have to generate two random numbers, this is how you do it:

R = random(); //Generate a random number called R between 0-1

S = random(); //Generate a random number called S between 0-1

if(R + S >=1)
{
R = 1 – R;
S = 1 – S;
}

Answer 6

You may check my 2009 paper, where I derived an "exact" approach to generate "random points" inside different lattice shapes: "hexagonal", "rhombus", and "triangular". As far as I know it is the "most optimized approach" because for every 2D position you only need two random samples. Other works derived earlier require 3 samples for each 2D position!

Hope this answers the question!

http://arxiv.org/abs/1306.0162

Answer 7

1）ポイントから数値への二分法を作成し（それらを列挙するだけ）、乱数を取得->ポイントを取得します。

別の解決策。

2）N-六角形の辺の長さの場合、[1..N]から3つの乱数を取得し、あるコーナーから開始して、この数値で3方向に3回移動します。

Answer 8

The rejection sampling solution above is intuitive and simple, but uses a rectangle, and (presumably) euclidean, X/Y coordinates. You could make this slightly more efficient (though still suboptimal) by using a circle with radius r, and generate random points using polar coordinates from the center instead, where distance would be rand()*r, and theta (in radians) would be rand()*2*PI.