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

Question

Я должен иметь возможность установить произвольное местоположение для точки маршрута для симулятора полета.Задача по математике проста:

«Найти одно случайное место в четырехугольнике, где есть равная вероятность того, что точка находится в любом месте».

Визуально это выглядит так:

Пример четырехугольника ABCD: A: [21417.78 37105.97] B: [38197.32 24009.74] C: [1364.19 2455.54] D: [1227.77 37378.81]

Заранее благодарим за любую помощь, которую вы можете оказать.: -)

РЕДАКТИРОВАТЬ Спасибо всем за ваши ответы.Я посмотрю на это в выходные и награду принятый ответ тогда.Кстати, я должен был упомянуть, что четырехугольник может быть выпуклым или вогнутым.Шрай бой дата.

Answer 1

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

Обновление:

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

главная фигура http://mathworld.wolfram.com/images/eps-gif/TrianglePointPicking_700.gif

Учитывая треугольник с одной вершинойв начале координат и в других позициях v ₁ и v ₂ , выберите x http://mathworld.wolfram.com/images/equations/TrianglePointPicking/NumberedEquation2.gif, где A ₁ и A ₂ являются равномерными переменными в интервале [0,1] , что дает точки, равномерно распределенные вчетырехугольник (левая фигура).Точки, находящиеся не внутри треугольника, могут быть либо отброшены, либо преобразованы в соответствующую точку внутри треугольника (правая фигура).

Answer 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

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

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

Answer 4

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

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

Answer 5

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

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

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

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

Answer 6

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

Итак:

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

Answer 7

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

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

Answer 8

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

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

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

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

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

Answer 9

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

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

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

edit

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