Generating random points within a hexagon for procedural game content

I'm using procedural techniques to generate graphics for a game I am writing.

To generate some woods I would like to scatter t开发者_JAVA技巧rees randomly within a regular hexagonal area centred at <0,0>.

What is the best way to generate these points in a uniform way?

If you can find a good rectangular bounding box for your hexagon, the easiest way to generate uniformly random points is by rejection sampling (http://en.wikipedia.org/wiki/Rejection_sampling)

That is, find a rectangle that entirely contains your hexagon, and then generate uniformly random points within the rectangle (this is easy, just independently generate random values for each coordinate in the right range). Check if the random point falls within the hexagon. If yes, keep it. If no, draw another point.

So long as you can find a good bounding box (the area of the rectangle should not be more than a constant factor larger than the area of the hexagon it encloses), this will be extremely fast.

A possibly simple way is the following:

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

Consider the parallelograms ADCO (center is O) and AOBF.

Any point in this can be written as a linear combination of two vectors AO and AF.

An point P in those two parallelograms satisfies

P = x* AO + y * AF or 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.

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

The traditional approach (applicable to regions of any polygonal shape) is to perform trapezoidal decomposition of your original hexagon. Once that is done, you can select your random points through the following two-step process:

1) Select a random trapezoid from the decomposition. Each trapezoid is selected with probability proportional to its area.

2) Select a random point uniformly in the trapezoid chosen on step 1.

You can use triangulation instead of trapezoidal decomposition, if you prefer to do so.

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;
}

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

1) make biection from points to numbers (just enumerate them), get random number -> get point.

Another solution.

2) if N - length of hexagon's side, get 3 random numbers from [1..N], start from some corner and move 3 times with this numbers for 3 directions.

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.