Генерация случайных точек в шестиугольнике для процедурного игрового содержания
Я использую процедурные методы для генерации графики для игры, которую я пишу.
Для генерации некоторых лесов, я хотел бы рассеять деревья случайным образом в регулярной шестиугольной области, центрируемой в <0,0>.
Что лучший способ состоит в том, чтобы генерировать эти точки универсальным способом?
6 ответов
Если это обычный шестиугольник, то самый простой метод, который приходит на ум - разделить его на три ромба. Таким образом, (а) они имеют одинаковую площадь, и (б) вы можете выбрать случайную точку в любом ромбе с помощью двух случайных переменных от 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 )
То есть найдите прямоугольник, полностью содержащий ваш шестиугольник, а затем сгенерируйте равномерно случайные точки внутри прямоугольника (это просто, просто независимо генерируйте случайные значения для каждой координаты в правильном диапазоне ). Проверьте, попадает ли случайная точка внутрь шестиугольника. Если да, оставьте это себе. Если нет, нарисуйте еще одну точку.
Пока вы можете найти хороший ограничивающий прямоугольник (площадь прямоугольника не должна быть более чем на постоянный коэффициент больше, чем площадь шестиугольника, который он охватывает), это будет очень быстро.
Традиционный подход (применимый к областям любой многоугольной формы) заключается в выполнении трапециевидного разложения исходного шестиугольника. После этого можно выбрать случайные точки с помощью следующего двухэтапного процесса:
1) Выберите случайную трапецию из разложения. Каждая трапеция выбирается с вероятностью, пропорциональной ее площади.
2) Выберите случайную точку, равномерно расположенную в трапеции, выбранной на шаге 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;
}
1) сделать привязку от точек к числам (просто перечислить их), получить случайное число -> получить точку.
Другое решение.
2) если N - длина стороны шестиугольника, возьмите 3 случайных числа из [1...N], начните с какого-нибудь угла и двигайтесь 3 раза с этими числами по 3 направлениям.
Возможно, простой способ заключается в следующем:
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).
Точно так же любую точку Q в параллелограмме BECO можно записать как линейную комбинацию векторов BO и BE, такую что
Q = x BO + y BE, где 0 <= x <= 1 и 0 <= y <= 1.
Таким образом, чтобы выбрать случайную точку
, мы выбираем
A с вероятностью 2/3 и B с вероятностью 1/3.
Если вы выбрали A, выберите x в [0,1) (примечание, полуоткрытый интервал [0,1)) и y в [-1,1] и выберите точку P = x AO + y AF, если y> 0, иначе выбираем P = x * AO + | y | * AD.
Если вы выбрали B, выберите x в [0,1] и y в [0,1] и выберите точку Q = x BO + y BE.
Таким образом, для выбора одной точки потребуется три вызова случайных чисел, что может быть достаточно хорошим, в зависимости от вашей ситуации.