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

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

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

2. Если ваш параллелограмм определяется точками 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 в квадрате может быть описана четверкой, такой что:

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

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

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

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

Для этого мы:

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

   

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

   

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

   

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

   

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

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

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

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

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

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

.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 здесь). По сути, существует билинейная параметризация, которая отображает квадрат в uv-пространстве (в данном случае для u, v \ in [-1, 1]) в ваш четырехугольник, который состоит из точек p_i (для i = 1,2,3,4 ). Обратите внимание, что в предоставленной ссылке параметры называются \ eta и \ xi.

Базовый рецепт:

1. Выберите подходящий генератор случайных чисел для создания хорошо распределенных точек в квадратной 2D-области.
2. Генерация случайных пар u-v в диапазоне [-1, 1]
3. Для каждой пары 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 в ограничивающем прямоугольнике квадрата и написать тест «точка в квадрате» (возможно, разделив проблему на две точки в трис), чтобы отсеять случайные точки, которые находятся вне.

Должны ли баллы быть распределены равномерно, или любое распределение приемлемо?

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

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

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

Какое распределение вы хотите, чтобы баллы были? Если вам все равно, вышеуказанные методы подойдут. Если вы хотите равномерного распределения, подойдет следующая процедура: Разделите многоугольник на два треугольника, 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) является выборкой из равномерного распределения на многоугольнике.

Функция 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;