Generating random points within a hexagon for procedural game content

Question

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

To generate some woods I would like to scatter trees randomly within a regular hexagonal area centred at <0,0>.

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

Answer 1

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.