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

Question

我正在使用程序技术为我正在编写的游戏生成图形。

为了生成一些树林，我想将树木随机散布在以 <0,0> 为中心的正六边形区域内。

以统一的方式生成这些点的最佳方法是什么？

Answer 1

如果您能为六边形找到一个好的矩形边界框，则生成均匀随机点的最简单方法是通过拒绝采样（http://en.wikipedia.org/wiki/Rejection_sampling）

即找到一个完全包含你的六边形的矩形，然后在矩形内生成均匀的随机点（这很简单，只需独立生成随机点即可）正确范围内每个坐标的值）。检查随机点是否落在六边形内。如果是，请保留。如果不是，则再画一个点。

只要你能找到一个好的边界框（矩形的面积不应超过它所包围的六边形面积的常数因子），这将非常快。

Answer 2

一种可能简单的方法如下：

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

考虑平行四边形 ADCO（中心为 O）和 AOBF。

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

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

P = x* AO + y * AF 或 xAO + yAD。

其中 0 <= x < 1 和 0 <= y <= 1 （我们折扣与 BECO 共享的边）。

类似地，平行四边形 BECO 中的任何点 Q 都可以写成向量 BO 和 BE 的线性组合，使得

Q = xBO + yBE，其中 0 <=x <=1 且 0 <=1。 =y <= 1。

因此，为了选择随机点，

我们

以 2/3 的概率选择 A，以 1/3 的概率选择 B。

如果选择 A，则在 [0,1) 中选择 x（注意，半开区间 [0,1)），在 [-1,1] 中选择 y，并选择点 P = xAO+yAF如果y> 0 否则选择 P = x*AO + |y|*AD。

如果选择 B，则在 [0,1] 中选择 x，在 [0,1] 中选择 y，然后选择点 Q = xBO + yBE。

因此，需要三次随机数调用才能选择一个点，这可能足够好，具体取决于您的情况。

Answer 3

如果是正六边形，想到的最简单的方法就是将其分成三个菱形。这样，(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()

这是一张图片。

替代文本 http://www.freeimagehosting.net/uploads/0f80ad5d9a.png

Answer 4

传统方法（适用于任何多边形形状的区域）是对原始六边形进行梯形分解。完成后，您可以通过以下两步过程选择随机点：

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

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

如果您愿意，可以使用三角剖分代替梯形分解。

Answer 5

将其切成六个三角形（因此这适用于任何正多边形），随机选择一个三角形，然后 随机选择所选三角形中的一个点。

在三角形中选择随机点是一个有据可查的问题。

当然，这非常快，您只需为每个点生成 3 个随机数 --- 无需拒绝等。

更新：

由于您必须生成两个随机数，这就是你的做法：

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

您可以查看我 2009 年的论文，其中我导出了一种“精确”方法来在不同的晶格形状（“六边形”、“菱形”和“三角形”）内生成“随机点”。据我所知，这是“最优化的方法”，因为对于每个 2D 位置，您只需要两个随机样本。之前导出的其他作品需要每个 2D 位置 3 个样本！

希望这能回答这个问题！

http://arxiv.org/abs/1306.0162

Answer 7

1）从点到数字进行二分（只需枚举它们），得到随机数->明白了。

另一个解决方案。

2）如果N - 六边形边长，则从[1..N]中获取3个随机数，从某个角开始，用这些数字向3个方向移动3次。

Answer 8

上面的拒绝采样解决方案直观且简单，但使用矩形和（大概）欧几里德 X/Y 坐标。您可以通过使用半径为 r 的圆来稍微提高效率（尽管仍然不是最佳），并使用从中心开始的极坐标生成随机点，其中距离为 rand()*r，theta（以弧度为单位）为兰特（）* 2 * PI。