Losowe punkty wewnątrz równoległoboku

Pytanie OP jest nieco niejednoznaczne, więc na pytanie odpowiem: Jak wygenerować punkt z równomiernego rozkładu wewnątrz dowolnego czworokąta, które jest w rzeczywistości uogólnieniem Jak wygenerować punkt z równomiernego rozkładu wewnątrz dowolnego (wypukłego) wielokąta. Odpowiedź opiera się na przypadku generowania próbki z równomiernego rozkładu w trójkącie (patrz http://mathworld.wolfram.com/TrianglePointPicking.html , który ma bardzo ładne Wyjaśnienie).

Aby to osiągnąć My:

1. Trianguluj wielokąt (tzn. Wygeneruj zbiór nie nakładających się trójkątnych regionów, które pokrywają wielokąt). W przypadku czworokąta tworzymy krawędź w poprzek dowolne dwa nie sąsiadujące wierzchołki. Inne wielokąty zobacz http://en.wikipedia.org/wiki/Polygon_triangulation dla punktu wyjścia, lub http://www.cgal.org / if you just need a biblioteka.

   

2. Aby wybrać jeden z trójkątów losowo, przypisajmy indeks do każdego trójkąta (tj. 0,1,2,...). Dla czworokąta będą one równe 0,1. Dla każdego trójkąta przypisujemy wagę równą w następujący sposób:

   

3. Następnie Wygeneruj losowy indeks i z skończonego rozkładu nad indeksami podanymi ich wagami. Dla czworokąta jest to rozkład Bernoulliego:

   

4. Niech v0, v1, V2 będzie wierzchołki trójkąta (reprezentowane przez ich miejsca punktowe, tak że v0 = (x0, y0), itd. Następnie generujemy dwie losowe liczby a0 i a1, obie narysowane równomiernie z przedziału [0,1]. Następnie obliczamy losowy punkt x przez x = a0 (v1-v0) + A1 (v2-v0).

   

5. Zauważ, że z prawdopodobieństwem 0,5, x leży poza trójkątem, jednak jeśli tak, to leży wewnątrz równoległoboku złożonego ze Związku trójkąta z jego obrazem po obrocie pi wokół punktu środkowego (v1,v2) (przerywane linie na obrazku). W takim przypadku możemy wygenerować nowy punkt x ' = v0 + R (pi) (x - v3), gdzie R (pi) to Obrót O pi (180 stopni). Punkt x ' będzie wewnątrz trójkąta.

6. Następnie zauważmy, że jeśli czworokąt był już równoległobokiem, to nie musimy wybierać trójkąta losowo, możemy wybrać albo jeden deterministycznie, a następnie wybrać punkt x bez testowania, że znajduje się on wewnątrz jego trójkąta źródłowego.

Zakładając, że chcesz równomiernego rozkładu: uformuj dwa trójkąty z wielokąta. Wybierz, który Trójkąt wygenerować punkt w zależności od ich stosunku powierzchni.

Wywołaj narożniki trójkąta A, B, C, wektory boczne AB, BC, AC i generuj dwie liczby losowe w [0,1] zwane u i v. niech p = u * AB + v * AC.

Jeśli A + p znajduje się wewnątrz trójkąta, zwróć a + p

Jeśli A + p znajduje się poza trójkątem, zwróć A + AB + AC-p

(jest to w zasadzie wzór Pierrebdra z wyjątkiem wstępnego przetwarzania i ostatniego kroku, który składa punkt z powrotem do trójkąta, dzięki czemu może obsługiwać inne kształty niż równoległoboki).

Twój wielokąt to dwa trójkąty, więc dlaczego nie wybrać losowo jednego z nich, a następnie znaleźć losowy punkt w trójkącie.

Prawdopodobnie nie jest to najlepsze rozwiązanie, ale zadziała.

Nieco mniej "naiwne " byłoby użycie algorytmu wypełniania wielokątów, a następnie losowe wybieranie punktów z linii wypełniania.

Próbka Kodu 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.

Przez "ogólne" masz na myśli wszystkie wielokąty bez równoległoboku w ogólności lub wszystkie możliwe wielokąty?

Może narysujesz losową linię łączącą 4 strony np. jeśli masz to:

.BBBB.
A    C
A    C
.DDDD.

Następnie Wygeneruj losowy punkt na jednostkowym kwadracie, a następnie zaznacz punkt na linii B I D w procentach odległości na osi X. Zrób to samo w linii A i C używając wartości z osi Y.

Następnie połącz punkt na linii a z linią C i linią B z linią D, przecięcie punkt jest następnie używany jako punkt losowy.

Nie jest jednolita, ponieważ błędy zaokrąglania pomagają określonym punktom, ale powinna być bliska, jeśli pracujesz z wartościami zmiennoprzecinkowymi.

Implementacja powinna być dość łatwa, ponieważ już pracujesz z wielokątami. Powinieneś już mieć kod, który wykonuje te proste zadania.

Oto szybki pseudokod:

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);

}

To działa dla ogólnych, wypukłych czworokątów:

Można zapożyczyć niektóre pojęcia z metody elementów skończonych, szczególnie dla elementów czworobocznych (4-stronnych) (zobacz sekcję 16.5 tutaj). Zasadniczo, istnieje Dwuliniowa parametryzacja, która odwzorowuje kwadrat w przestrzeni U-v (dla u, V \in [-1, 1] w tym przypadku) na czworokąt, który składa się z punktów p_i (dla i = 1,2,3,4). Zauważ, że w podanej referencji parametry nazywane są \eta i \ xi.

Przepis podstawowy:

1. Wybierz odpowiedni generator liczb losowych, aby wygenerować dobrze rozmieszczone punkty w kwadratowej domenie 2D
2. generowanie losowych par u-v w zakresie [-1, 1]
3. dla każdej pary u-v, odpowiedni punkt losowy w Twoim kwadracie = 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)

Jedynym problemem jest to, że równomiernie rozłożone punkty w przestrzeni u-v nie będą produkować równomiernie rozłożonych punktów w Twoim kwadracie (w sensie Euklidesowym). Jeśli jest to ważne, możesz pracować bezpośrednio w 2D wewnątrz obwiedni quada i napisać test point-in-quad (może dzieląc problem na dwa punkty w tris), aby usunąć losowe punkty, które są na zewnątrz.

Czy punkty muszą być równomiernie rozłożone, czy dowolny rozkład jest w porządku?

Czy wielokąt może być wklęsły, czy może być wypukły?

Jeśli odpowiedź na oba powyższe pytania brzmi nie, wybierz dowolne dwa wierzchołki i wybierz losowy punkt na odcinku linii między nimi. Jest to ograniczone do segmentów linii łączących wierzchołki( tj. bardzo niejednorodne); możesz zrobić trochę lepiej, wybierając trzeci wierzchołek, a następnie wybierając punkt między tym a pierwszym punktem -- nadal niejednorodne, ale przynajmniej dowolny punkt w wielokątu jest możliwy

Wybór losowego punktu na linii między dwoma punktami jest łatwy, tylko A + p (B-A), gdzie A i B są punktami, a p jest liczbą losową między 0,0 a 1,0

Jaki rodzaj dystrybucji chcesz, aby punkty miały? Jeśli cię to nie obchodzi, powyższe metody będą działać dobrze. Jeśli chcesz równomiernego rozkładu, będzie działać następująca procedura: podziel wielokąt na dwa trójkąty, a i b. niech A(a) i A (b) będą ich obszarami. Próbkę punktu p z równomiernego rozkładu w przedziale od 0 do A (a)+A (b). Jeśli p

Funkcja MATLAB cprnd generuje punkty z równomiernego rozkładu na ogólnym wypukłym politopie. Dla Twojego pytania bardziej wyspecjalizowany algorytm oparty na rozkładaniu czworokąta na Trójkąty jest bardziej wydajny.

Dla PostGIS, to jest to, co używam (możesz chcieć oddział dla możliwych nieskończonych pętli). Możesz wyeksportować algorytm do swojego języka programowania:

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;