Нахождение случайных координат x, y на фигуре, где вы знаете границу - PullRequest
Новая
       75

Нахождение случайных координат x, y на фигуре, где вы знаете границу

1 голос
/ 08 мая 2020

Цель - найти координаты фигуры неизвестной формы. Известен список координат границы этого рисунка, например:

boundary = [(0,0),(1,0),(2,0),(3,0),(3,1),(3,2),(3,3),(2,3),(2,2),(1,2),(1,3),(0,3),(0,2),(0,1]

, который будет выглядеть примерно так:

Квадрат

Это очень простой c пример, и я хотел бы сделать это с очень большими списками самых разных фигур.

Вопрос в том, как получить случайную координату, которая находится внутри фигуры, БЕЗ жесткого кодирования чего-либо о форме фигуры, потому что это будет неизвестно в начале? Есть ли способ узнать наверняка или сделать оценку наилучшего варианта? Как мне реализовать такую ​​оценку?

1 Ответ

0 голосов
/ 08 мая 2020

Вот предварительный ответ. Вы выбираете числа в два этапа.

Перед тем, как провести подготовительную работу - разбить фигуру на простые элементарные объекты. В вашем случае вы разбиваете его на прямоугольники, часто люди триангулируют и разбивают его на треугольники.

Итак, у вас есть N простых объектов, каждый с площадью A i и общей площадью A = Sum (A i ).

Первый шаг выборки - выберите, из какого прямоугольника выбрать точку. В каком-то псевдокоде 

r = randomU01(); // random value in [0...1) range
for(i in N) {
    r = r - A_i/A;
    if (r <= 0) {
        k = i;
        break;
    }
}

Итак, вы взяли один прямоугольник с индексом k, а затем просто равномерно выбрали точку в этом прямоугольнике 

x = A_k.dim.x * randomU01();
y = A_k.dim.y * randomU01();

return (x + A_k.lower_left_corner.x, y + A_k.lower_left_corner.y);

И все. Очень похожий метод для триангулированной фигуры.

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

ОБНОВЛЕНИЕ

Если ваша граница является generi c, тогда единственный хороший способ go - это триангулировать ваш многоугольник с помощью любой хорошей библиотеки (например, Triangle ), а затем выбрать один из треугольников в зависимости от площади (шаг 1) , затем выберите равномерно точку в треугольнике, используя два случайных числа U01 r1 и r2, 

P = (1 - sqrt(r1)) * A + (sqrt(r1)*(1 - r2)) * B + (r2*sqrt(r1)) * C

, т.е. в псевдокоде 

r1 = randomU01();
s1 = sqrt(r1);
r2 = randomU01();

x = (1.0-s1)*A.x + s1*(1.0-r2)*B.x + r2*s1*C.x;
y = (1.0-s1)*A.y + s1*(1.0-r2)*B.y + r2*s1*C.y;

return (x,y);
...