Как найти случайную точку в четырехугольнике?

Я бы разделил ваш четырехугольник на несколько фигур, где каждая фигура представляет собой правильный многоугольник с одной стороной (или обеими сторонами), параллельной одной из осей. Например, для рисунка выше я бы сначала нашел максимальный прямоугольник, который помещается внутри четырехугольника, прямоугольник должен быть параллелен осям X / Y. Затем в оставшейся области я бы поместил треугольники, такие треугольники будут прилегать к каждой стороне прямоугольника.

то просто написать функцию:

1) получить цифру наугад. 2) найти случайную точку на рисунке.

Если фигура, выбранная в №1, представляет собой прямоугольник, найти в нем случайную точку будет довольно легко. Сложная часть - написать процедуру, которая может найти случайную точку внутри треугольника

Это интересная проблема, и, вероятно, есть действительно интересный ответ, но если вы просто хотите, чтобы она работала, позвольте мне предложить вам кое-что простое.

Вот алгоритм:

1. Выберите случайную точку внутри прямоугольника, ограничивающего четырехугольник.
2. Если это не в пределах четырехугольника (или любой другой формы), повторите.
3. Прибыль!

править

Я обновил первый шаг, упомянув ограничивающую рамку, согласно предложению Барта К..

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

Итак:

1. Найдите ящик, содержащий все точки вашего многоугольника.
2. Создайте случайную точку внутри границ ранее найденного блока. Используйте случайные функции для генерации значений x и y.
3. Проверьте, находится ли эта точка внутри многоугольника (см. здесь или здесь )
4. Если эта точка находится внутри остановки многоугольника, все готово, если нет к шагу 2

Я считаю, что есть два подходящих способа решить эту проблему.

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

  Find Bounding box (x,y,width, height)
  Pick Random Point x1,y1 with ranges [x to x+width] and [y to y+height]
  while (x1 or y1 is no inside the quadrangle){
       Select new x1,y1
  }

Предполагая, что площадь вашего четырехугольника равна Q, а ограничивающая рамка - A, вероятность того, что вам нужно будет сгенерировать N пар точек, равна 1- (Q / A) ^ N, что экспоненциально приближается к 0.

Я бы порекомендовал вышеупомянутый подход, особенно в двух измерениях. Набирать очки и тестировать очень быстро.

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

http://mathworld.wolfram.com/TrianglePointPicking.html

Дает очень хорошее объяснение

Подход «грубой силы» заключается в простом цикле до тех пор, пока у вас не будет действительной координаты. В псевдокоде:

left   = min(pa.x, pb.x, pc.x, pd.x)
right  = max(pa.x, pb.x, pc.x, pd.x)
bottom = min(pa.y, pb.y, pc.y, pd.y)
top    = max(pa.y, pb.y, pc.y, pd.y)
do {
    x = left   + fmod(rand, right-left)
    y = bottom + fmod(rand, top-bottom)
} while (!isin(x, y, pa, pb, pc, pd));

Вы можете использовать стандартную функцию, извлеченную из сети для "isin". Я понимаю, что это не самая быстро выполняемая вещь в мире, но думаю, что это сработает.

Итак, на этот раз о том, как выяснить, находится ли точка внутри квадрата:

Четыре грани можно выразить в виде линий в y = mx + b форме. Проверьте, находится ли точка выше или ниже каждой из четырех линий, и, взятые вместе, вы сможете определить, находится ли она внутри или снаружи.

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

Между прочим, в этой постановке задачи я думаю, что использование слова «найти» сбивает с толку. На самом деле вы не можете найти случайное значение, удовлетворяющее условию; рандомизатор просто передает его вам. Что вы пытаетесь сделать, так это установить параметры в рандомизаторе, чтобы получить значения, соответствующие определенным критериям.

Итак, это зависит от того, как вы хотите получить распределение.

Если вы хотите получить случайную выборку точек в пространстве 2d, то ответ Джейкоба - отличный вариант. Если вы хотите, чтобы точки были как бы в перспективе (в вашем примере больше плотности в правом верхнем углу, чем в левом нижнем), то вы можете использовать билинейную интерполяцию.

Билинейная интерполяция довольно проста. Сгенерируйте два случайных числа s и t в диапазоне [0..1]. Затем, если ваши входные точки p0,p1,p2,p3, то билинейная интерполяция будет такой:

bilerp(s,t) = t*(s*p3+(1-s)*p2) + (1-t)*(s*p1+(1-s)*p0)

Основное различие заключается в том, хотите ли вы, чтобы ваше распределение было равномерным в вашем пространстве 2d (метод Якоба) или равномерным в пространстве параметров.