Случайные точки внутри параллелограмма

Ответ 1

а. Если вы можете ограничить свой ввод параллелограммом, это очень просто:

• Возьмем два случайных числа между 0 и 1. Мы будем называть тогда u и v.

• Если ваш параллелограмм определяется точками ABCD, так что AB, BC, CD и DA - стороны, тогда возьмите свою точку как:

   p = A + (u * AB) + (v * AD)
  

Где AB - вектор от A до B и AD вектор от A до D.

В. Теперь, если вы не можете, вы все равно можете использовать барицентрические координаты. Барицентрические координаты соответствуют для квадранта 4 координатам (a,b,c,d) таким, что a+b+c+d=1. Тогда любая точка P внутри квада может быть описана 4-uple такой, что:

P = a A + b B + c C + d D

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

С. Вы также можете, как было предложено в другом месте, разложить квадрат на два треугольника и использовать метод полупараллелограммы (т.е. Как параллелограмм, но вы добавляете условие u+v=1) или барицентрические координаты для треугольников. Однако, если вы хотите равномерного распределения, вероятность наличия точки в одном из треугольников должна быть равна площади треугольника, деленной на площадь квадрата.

Ответ 2

Вопрос OP немного неоднозначен, поэтому вопрос, на который я буду отвечать, следующий: Как создать точку из равномерного распределения внутри произвольного четырехугольника, что на самом деле является обобщением Как создать точку из равномерного распределения внутри произвольного (выпуклого) многоугольника. Ответ основан на примере создания образца из равномерного распределения в треугольнике (см. http://mathworld.wolfram.com/TrianglePointPicking.html, который имеет очень хорошее объяснение).

Для этого мы:

• Триангулировать многоугольник (т.е. создать набор неперекрывающихся треугольных областей, покрывающих многоугольник). Для случая четырехугольника создайте любые две несмежные вершины. Для других полигонов см. http://en.wikipedia.org/wiki/Polygon_triangulation для начальной точки или http://www.cgal.org/, если вам просто нужна библиотека.

• Чтобы выбрать один из треугольников случайным образом, присвойте индекс каждому треугольнику (т.е. 0,1,2,...). Для четырехугольника они будут равны 0,1. Для каждого треугольника мы присваиваем вес, равный следующему:

• Затем создадим случайный индекс я из конечного распределения по индексам с учетом их весов. Для четырехугольника это распределение Бернулли:

• Пусть v0, v1, v2 - вершины треугольника (представленные их точками, так что v0 = (x0, y0) и т.д. Затем мы генерируем два случайных числа a0 и a1, интервал [0,1]. Затем мы вычисляем случайную точку x по x = a0 (v1-v0) + a1 (v2-v0).

• Заметим, что с вероятностью 0,5 x лежит вне внешней стороны треугольника, однако, если это так, то оно лежит внутри параллелограмма, состоящего из объединения треугольника с его изображением после поворота pi вокруг середины (v1, v2) (пунктирные линии на изображении). В этом случае мы можем создать новую точку x '= v0 + R (pi) (x - v3), где R (pi) - вращение на pi (180 град). Точка x 'будет находиться внутри треугольника.

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

Ответ 3

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

Вызвать углы треугольника A, B, C, боковые векторы AB, BC, AC и сгенерировать в [0,1] два случайных числа, называемых u и v. Пусть p = u * AB + v * AC.

Если A + p находится внутри треугольника, верните A + p

Если A + p находится вне треугольника, верните A + AB + AC - p

(Это в основном формула PierreBdR, за исключением предварительной обработки и последнего шага, который сбрасывает точку обратно в треугольник, поэтому он может обрабатывать другие фигуры, чем параллелограммы).

Ответ 4

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

Возможно, это не лучшее решение, но оно будет работать.

Ответ 5

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

Пример кода C

//  public-domain code by Darel Rex Finley, 2007

int  nodes, nodeX[MAX_POLY_CORNERS], pixelX, pixelY, i, j, swap ;

//  Loop through the rows of the image.
for (pixelY=IMAGE_TOP; pixelY<IMAGE_BOT; pixelY++) {

  //  Build a list of nodes.
  nodes=0; j=polyCorners-1;
  for (i=0; i<polyCorners; i++) {
    if (polyY[i]<(double) pixelY && polyY[j]>=(double) pixelY
    ||  polyY[j]<(double) pixelY && polyY[i]>=(double) pixelY) {
      nodeX[nodes++]=(int) (polyX[i]+(pixelY-polyY[i])/(polyY[j]-polyY[i])
      *(polyX[j]-polyX[i])); }
    j=i; }

  //  Sort the nodes, via a simple "Bubble" sort.
  i=0;
  while (i<nodes-1) {
    if (nodeX[i]>nodeX[i+1]) {
      swap=nodeX[i]; nodeX[i]=nodeX[i+1]; nodeX[i+1]=swap; if (i) i--; }
    else {
      i++; }}

  //  Fill the pixels between node pairs.
  //  Code modified by SoloBold 27 Oct 2008
  //  The flagPixel method below will flag a pixel as a possible choice.
  for (i=0; i<nodes; i+=2) {
    if   (nodeX[i  ]>=IMAGE_RIGHT) break;
    if   (nodeX[i+1]> IMAGE_LEFT ) {
      if (nodeX[i  ]< IMAGE_LEFT ) nodeX[i  ]=IMAGE_LEFT ;
      if (nodeX[i+1]> IMAGE_RIGHT) nodeX[i+1]=IMAGE_RIGHT;
      for (j=nodeX[i]; j<nodeX[i+1]; j++) flagPixel(j,pixelY); }}}

   // TODO pick a flagged pixel randomly and fill it, then remove it from the list.
   // Repeat until no flagged pixels remain.

Ответ 6

Под "общим" вы подразумеваете все непараллельные 4-сторонние многоугольники вообще или все возможные полигоны?

Как рисовать случайную линию, соединяющую 4 стороны, например. Если у вас есть это:

.BBBB.
A    C
A    C
.DDDD.

Затем создайте случайную точку на единичном квадрате, затем отметьте точку на линии B и D на процент расстояния от оси X. Сделайте то же самое на линиях A и C, используя значение по оси Y.

Затем подключите точку в строке A к строке C и строке B к строке D, тогда точка пересечения используется как случайная точка.

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

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

Здесь быстрый псевдокод:

void GetRandomPoint(Polygon p, ref float x, ref float y) {

    float xrand = random();
    float yrand = random();

    float h0 = p.Vertices[0] + xrand * p.Vertices[1];
    float h1 = p.Vertices[2] + yrand * p.Vertices[3];

    float v0 = p.Vertices[0] + xrand * p.Vertices[2];
    float v1 = p.Vertices[1] + yrand * p.Vertices[3];

    GetLineIntersection(h0, h1, v0, v1, x, y);

}

Ответ 7

Это работает для общих выпуклых четырехугольников:

Вы можете одолжить некоторые понятия из метода конечных элементов, в частности для четырехсторонних (четырехсторонних) элементов ( обратитесь к разделу 16.5 здесь). В принципе, существует билинейная параметризация, которая отображает квадрат в uv-пространстве (для u, v\in [-1, 1] в этом случае) на ваш четырехугольник, который состоит из точек p_i (для я = 1,2,3,4). Обратите внимание: в приведенной ссылке параметры называются \eta и\xi.

Основной рецепт:

• Выберите подходящий генератор случайных чисел для генерации хорошо распределенных точек в квадратной 2D-области
• Генерировать случайные пары u-v в диапазоне [-1, 1]
• Для каждой пары uv соответствующая случайная точка в вашем квадрате = 1/4 * ((1-u) (1-v) * p_1 + (1 + u) (1-v) * p_2 + (1+ u) (1 + v) * p_3 + (1-u) (1 + v) * p_4)

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

Ответ 8

Нужно ли равномерно распределять точки или любое распределение нормально?

Может ли многоугольник быть вогнутым или он должен быть выпуклым?

Если ответ на оба вышеизложенного отсутствует, затем выберите любую из двух вершин и выберите случайную точку на сегменте линии между ними. Это ограничивается линиями, соединяющими вершины (т.е. ОЧЕНЬ неоднородными); вы можете сделать немного лучше, выбрав третью вершину и затем выбрав точку между ней и первой точкой - все еще неравномерную, но возможно хотя бы любую точку в полигоне

Выбор случайной точки на линии между двумя точками легко, просто A + p (B-A), где A и B - точки, а p - случайное число между 0.0 и 1.0

Ответ 9

Какое распределение вы хотите получить от очков? Если вам все равно, эти методы будут работать нормально. Если вы хотите равномерного распределения, будет работать следующая процедура: Разделите многоугольник на два треугольника: a и b. Пусть A (a) и A (b) - их области. Выделите точку p из равномерного распределения на интервале между 0 и A (a) + A (b). Если p < A (a), выберите треугольник a. В противном случае выберите треугольник b. Выберем вершину v выбранного треугольника, а c и d - векторы, соответствующие сторонам треугольника. Образец двух чисел x и y из экспоненциального распределения с единичным средним. Тогда точка (xc + yd)/(x + y) является образцом из равномерного распределения на многоугольнике.

Ответ 10

Функция MATLAB cprnd генерирует точки из равномерного распределения на общем выпуклом многограннике. Для вашего вопроса более эффективен более специализированный алгоритм, основанный на разложении четырехугольника на треугольники.

Ответ 11

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

CREATE or replace FUNCTION random_point(geometry)
RETURNS geometry
AS $$
DECLARE 
    env geometry;
    corner1 geometry;
    corner2 geometry;
    minx real;
    miny real;
    maxx real;
    maxy real;
    x real;
    y real;
    ret geometry;
begin

select ST_Envelope($1) into env;
select ST_PointN(ST_ExteriorRing(env),1) into corner1;
select ST_PointN(ST_ExteriorRing(env),3) into corner2;
select st_x(corner1) into minx;
select st_x(corner2) into maxx;
select st_y(corner1) into miny;
select st_y(corner2) into maxy;
loop
    select minx+random()*(maxx-minx) into x;
    select miny+random()*(maxy-miny) into y;
    select ST_SetSRID(st_point(x,y), st_srid($1)) into ret;
    if ST_Contains($1,ret) then
        return ret ;
    end if;
end loop;
end;
$$
LANGUAGE plpgsql
volatile
RETURNS NULL ON NULL INPUT;