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

https://stackoverflow.com/questions/240778

04-07-2019
|

Вопрос

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

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

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

Решение

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

Возьмите два случайных числа от 0 до 1.Мы позвоним тогда u и v.
Если ваш параллелограмм определяется точками ABCD, причем стороны AB, BC, CD и DA, то примите точку так:
```
 p = A + (u * AB) + (v * AD)
```

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

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

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

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

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

Другие советы

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

Для этого мы:

<Ол>

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

введите описание изображения здесь

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

расчет веса

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

введите описание изображения здесь

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

введите описание изображения здесь

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

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

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

Назовите углы треугольника 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, за исключением предварительной обработки и последнего шага, который сгибает точку обратно в треугольник, поэтому он может обрабатывать другие формы, чем параллелограммы).

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

Вероятно, не лучшее решение, но оно бы сработало.

Несколько менее &, na & # 239; ve < ! / а> <> Quot; подход будет заключаться в использовании алгоритма заполнения полигонов , а затем случайным образом выбирайте точки из линий заполнения.

Пример кода 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.

По " общему " Вы имеете в виду все непараллелограммные 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);

}

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

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

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

<Ол>

Выберите подходящий генератор случайных чисел для генерации хорошо распределенных точек в квадратной двумерной области

Генерация случайных пар u-v в диапазоне [-1, 1]

Для каждой ультрафиолетовой пары соответствующая случайная точка в вашем квадре = 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 в пределах ограничительной рамки четырехугольника и написать тест «точка-четверка» (возможно, разделив задачу на две точки в трисе), чтобы отобрать случайные точки, находящиеся снаружи.

Должны ли точки распределяться равномерно или все в порядке?

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

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

Легко выбрать случайную точку на линии между двумя точками, просто A + p (B-A), где A и B - точки, а p - случайное число от 0,0 до 1,0.

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

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

Для 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;

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow