10

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

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

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

4

8 回答 8

13

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

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

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

于 2010-07-13T17:20:56.263 回答
8

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

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

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

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

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

P = x* AO + y * AF 或 x AO + y AD。

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

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

Q = x BO + y BE 其中 0 <=x <=1 和 0 <=y <= 1。

因此选择一个随机点

我们选择

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

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

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

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

于 2010-07-13T17:38:11.927 回答
6

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

于 2010-07-13T21:47:40.520 回答
2

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

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

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

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

于 2010-07-13T17:21:15.177 回答
1

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

希望这能回答问题！

http://arxiv.org/abs/1306.0162

于 2013-10-03T12:52:45.313 回答
1

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

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

当然，这非常快，您只需在每个点生成 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;
}
于 2010-07-13T17:43:28.430 回答
0

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

于 2013-03-04T04:57:59.690 回答
0

1）从点到数字（只需枚举它们），获取随机数->获取点。

另一种解决方案。

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

于 2010-07-13T17:21:30.213 回答