在六边形内生成程序游戏内容的随机点

如果是正六边形,最简单的方法就是把它分成三个菱形。这样,(a)它们有相同的面积,(b)你可以在任意一个菱形中选取一个随机点,其中有两个随机变量,从0到1。下面是一个可以工作的python代码。

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()

在讨论中,有两个人提出了一个问题,那就是对六边形的离散形式进行均匀抽样。最自然的离散化是一个三角形网格,上面的解决方案有一个版本仍然有效。你可以稍微修剪菱形,使它们各自包含相同数量的点。它们只会错过原点,这必须作为特殊情况单独允许。这是一个代码:

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()

这是一张照片。

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

如果你能为你的六边形找到一个好的矩形边界框,产生均匀随机点的最简单方法就是拒绝抽样。( http://en.wikipedia.org/wiki/Rejection_sampling )

也就是说,找到一个完全包含六边形的矩形,然后在矩形内生成均匀随机的点(这很容易,只需为右范围内的每个坐标单独生成随机值)。检查随机点是否在六边形内。如果是,请保留。如果没有,再画一个点。

只要你能找到一个好的边界框(矩形的面积不应该大于它所包围的六边形的面积的一个常数因子),这将是非常快的。

一个可能简单的方法是:

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

考虑平行四边形adco(中心是o)和aobf。

其中的任何点都可以写成两个向量ao和af的线性组合。

这两个平行四边形中的点p满足

P=X*AO+Y*AF或X AO+Y 广告。

其中0<=x<1和0<=y<=1(我们对与BECO共享的边进行折扣)。

类似地,平行四边形Beco中的任何点q都可以写成矢量Bo的线性组合,并且

q=x B+Y 其中0<=x<=1和0<=y<=1。

从而选择一个随机点

我们选择

A的概率为2/3,B的概率为1/3。

如果选择了a,则选择x in[0,1)(注意,半开间隔[0,1))和y in[-1,1]并选择点p=x AO+Y 如果是Y>0,则选择P=X*AO+Y*AD。

如果选择b,选择x in[0,1]和y in[0,1]并选择点q=x B+Y 是。

所以需要三个随机号码来选择一个点,这可能足够好,取决于你的情况。

传统的方法(适用于任何多边形的区域)是对原始六边形执行梯形分解。完成后,您可以通过以下两个步骤选择随机点:

1)从分解中选择一个随机梯形。每个梯形的选择概率与其面积成比例。

2)在步骤1选择的梯形中均匀选择一个随机点。

如果您愿意,可以使用三角剖分而不是梯形分解。

把它分成六个三角形(因此这适用于任何正多边形),随机选择一个三角形,然后 randomly choose a point in the selected triangle .

在三角形中选择随机点是 well-documented problem .

当然,这是相当快的,你只需要生成3个随机数每点-没有拒绝,等等。

更新:

因为你必须生成两个随机数, 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;
}

你可以查阅我2009年的论文,在那里我推导了一种“精确”的方法来生成不同格子形状中的“随机点”:“六角形”、“菱形”和“三角形”。据我所知,这是“最优化的方法”,因为对于每个二维位置,您只需要两个随机样本。其他先前推导的作品要求每个二维位置有3个样本!

希望这能回答这个问题!

http://arxiv.org/abs/1306.0162

1)从一个点到另一个点(只需枚举它们),得到随机数->得到点。

另一个解决方案。

2)如果n——六边形边的长度,从[1..n]中随机取3个数字,从某个角开始,用这个数字向3个方向移动3次。

上面的拒绝抽样解决方案是直观和简单的,但使用的是一个矩形,和(可能)欧几里德,X/Y坐标。你可以通过使用半径为r的圆来稍微提高效率(尽管仍然是次优的),然后使用中心的极坐标生成随机点,其中距离为r and()*r,θ(以弧度表示)为r and()*2*pi。