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

Ответ 1

Разделите ваш четырехangularьник на два треangularьника и затем используйте этот превосходный ответ SO, чтобы быстро найти случайную точку в одном из них.

Обновление:

Заимствование этой замечательной ссылки у Акусте при выборе случайной точки в треangularьнике.

_{(из MathWorld - веб-ресурс Wolfram: wolfram.com)}

Дан треangularьник с одной вершиной в Происхождение и другие в позициях v ₁ и v ₂, выберите
_{(из MathWorld - веб-ресурс Wolfram: wolfram.com)}
 где A ₁ и A ₂ одинаковы изменяется в интервале [0,1], что дает точки равномерно распределены в четырехangularьник (левая фигура). точки не в интерьере треangularьника затем может быть либо отброшен, либо превращается в соответствующий указать внутри треangularьника (справа рисунок).

Ответ 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, которая приближается к экспоненциальному экспоненциально.

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

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

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

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

Ответ 3

Подход "грубой силы" просто прокручивается до тех пор, пока у вас не будет действительной координаты. В псевдокоде:

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". Я понимаю, что это не самая быстрая вещь в мире, но я думаю, что это сработает.

Ответ 4

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

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

Ответ 5

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

Кстати, в этом заявлении проблемы, я думаю, использование слова "найти" является сбивающим с толку. Вы не можете найти случайное значение, которое удовлетворяет условию; рандомизатор просто дает его вам. То, что вы пытаетесь сделать, это установить параметры рандомизатора, чтобы дать вам значения, соответствующие определенным критериям.

Ответ 6

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

Итак:

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

Ответ 7

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

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

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

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

Ответ 8

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

Здесь алгоритм:

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

изменить

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

Ответ 9

Итак, это зависит от того, как вы хотите, чтобы ваш дистрибутив.

Если вы хотите, чтобы точки случайным образом были выбраны в вашем пространстве просмотра 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-пространстве (метод Якова) или равномерным в пространстве параметров.