Алгоритм: вычисление псевдослучайной точки внутри эллипса

Question

Для простой системы частиц, которую я создаю, мне нужно, учитывая эллипс с шириной и высотой, вычислить случайную точку X, Y, которая лежит в этом эллипсе.

Теперь я нелучше всего по математике, поэтому я хотел бы спросить здесь, может ли кто-нибудь направить меня в правильном направлении.

Может быть, правильный путь - это выбрать случайное число с плавающей точкой в ​​диапазоне ширины, взять его за X и от негорассчитать значение Y?

Answer 1

1. Создание случайной точки внутри круга с радиусом 1. Это можно сделать, взяв случайный угол phi в интервале [0, 2*pi) и случайное значение rho в интервале [0, 1) и вычислив

   x = sqrt(rho) * cos(phi)
   y = sqrt(rho) * sin(phi)
   

   Квадратный корень в формуле обеспечивает равномерное распределение внутри круга.

2. Масштаб x и y до размеров эллипса

   x = x * width/2.0
   y = y * height/2.0
   

Answer 2

Использование выборка отклонения : выберите случайную точку в прямоугольнике вокруг эллипса. Проверьте, находится ли точка внутри эллипса, проверив знак (x-x0) ^ 2 / a ^ 2 + (y-y0) ^ 2 / b ^ 2-1. Повторите, если точка не внутри. (Это предполагает, что эллипс выровнен с осями координат. Аналогичное решение работает в общем случае, но, конечно, более сложно.)

Answer 3

Можно создать точки в эллипсе, не используя слишком отбрасывающую выборку, тщательно продумав ее определение в полярной форме.Из википедии полярная форма эллипса задается как

Интуитивно говоря, мы должны выбирать полярный угол θ чаще, гдерадиус больше.Если говорить более математически, то наш PDF для случайной величины θ должен быть p (θ) dθ = dA / A, где dA - площадь одного сегмента под углом θ с шириной dθ.Используя уравнение для площади полярного угла dA = 1/2 r ² dθ и площади эллипса, равной π ab, тогда PDF становится

Для случайной выборки из этого PDF-файла одним прямым методом является метод обратного CDF .Для этого необходимо рассчитать функцию накопленной плотности (CDF) и затем инвертировать эту функцию.Использование Wolfram Alpha для получения неопределенного интеграла, а затем его инвертирование дает обратный CDF, равный

, где u проходит от 0 до 1. Таким образом, для выборки случайногоугол θ, вы просто генерируете равномерное случайное число u между 0 и 1 и подставляете его в это уравнение для обратного CDF.

Чтобы получить случайный радиус, можно использовать ту же технику, которая работает для круга(см., например, Создание случайной точки в круге (равномерно) ).

Вот пример кода Python, который реализует этот алгоритм:

import numpy
import matplotlib.pyplot as plt
import random

# Returns theta in [-pi/2, 3pi/2]
def generate_theta(a, b):
    u = random.random() / 4.0
    theta = numpy.arctan(b/a * numpy.tan(2*numpy.pi*u))

    v = random.random()
    if v < 0.25:
        return theta
    elif v < 0.5:
        return numpy.pi - theta
    elif v < 0.75:
        return numpy.pi + theta
    else:
        return -theta

def radius(a, b, theta):
    return a * b / numpy.sqrt((b*numpy.cos(theta))**2 + (a*numpy.sin(theta))**2)

def random_point(a, b):
    random_theta = generate_theta(a, b)
    max_radius = radius(a, b, random_theta)
    random_radius = max_radius * numpy.sqrt(random.random())

    return numpy.array([
        random_radius * numpy.cos(random_theta),
        random_radius * numpy.sin(random_theta)
    ])

a = 2
b = 1

points = numpy.array([random_point(a, b) for _ in range(2000)])

plt.scatter(points[:,0], points[:,1])
plt.show()

Answer 4

Вы можете использовать преобразование полярных в декартовы координаты:

x = cos(angle) * radius
y = sin(angle) * radius

, что является незначительным изменением

x = cos(angle) * width
y = sin(angle) * height

Вы не указали язык, но вот небольшая демонстрация с использованием Processing:

float ellipseWidth = 150,ellipseHeight = 100;
float angle,radius,x,y;
void setup(){
  size(400,400);
  smooth();
  noStroke();
  ellipseMode(CENTER);
  background(0);
  fill(255);
}

void draw(){
  //choose a random angle on the ellipse
  angle = random(TWO_PI);
  //convert from polar to cartesian, using both width and height as radii
  x = cos(angle) * ellipseWidth;
  y = sin(angle) * random(ellipseHeight);//random 'lengths' vertically
  //draw
  translate(200,200);//move to centre
  ellipse(x,y,5,5);  
}

Вы можете увидеть, как он запускается здесь

HTH