Zufällige Punkte innerhalb eines Parallelogramms

Question

Ich habe einen 4 Seite konvexen Polygon um 4 Punkte in 2D definiert ist, und ich mag zufällige Punkte im Innern erzeugen können.

Wenn es wirklich das Problem vereinfacht, ich das Polygon ein Parallelogramm begrenzen, sondern eine allgemeinere Antwort bevorzugt wird.

Zufalls-Punkte, bis man im Inneren das Polygon funktionieren würde nicht, weil es die Zeit es braucht, wirklich unberechenbar ist.

Answer 1

A. Wenn Sie Ihre Eingabe Parallelogramm beschränken kann, das ist wirklich einfach:

1. Nehmen Sie zwei Zufallszahl zwischen 0 und 1. Wir werden dann u und v nennen.

2. Wenn Ihr Parallelogramm durch die Punkte ABCD so definiert ist, dass AB, BC, CD und DA die Seiten sind, dann ist dein Punkt als Wesen nehmen:

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

Wo AB der Vektor von A nach B ist und AD den Vektor von A bis D.

B. Nun, wenn Sie nicht, Sie können immer noch die baryzentrischen Koordinaten verwenden. Die baryzentrischen Koordinaten entsprechen, zu einem Quad, bis 4 (a,b,c,d) so dass a+b+c+d=1 Koordinaten. Dann kann jeder Punkt P im Quad von einem 4-e in Paar beschrieben, so dass:

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

In Ihrem Fall können Sie 4 Zufallszahl zeichnen und normalisieren, so dass sie auf 1 summieren sich, dass Sie gibt einen Punkt. Beachten Sie, dass die Verteilung der Punkte wird in diesem Fall nicht einheitlich sein.

C. Sie können auch, wie an anderer Stelle, zersetzen das Quad in zwei Dreiecken vorgeschlagen und verwenden, um die Halb Parallelogramm-Methode (das heißt, als das Parallelogramm, aber sie fügen Sie den Zustand u+v=1) oder die Schwerpunktkoordinaten für Dreiecken. wenn Sie eine gleichmäßige Verteilung Allerdings wollen, muss die Wahrscheinlichkeit, einen Punkt in einem Dreieck mit der Fläche des Quad aufgeteilt auf die Fläche des Dreiecks gleich sein.

Answer 2

Die Frage nach der OP ist ein bisschen zweideutig, so dass die Frage, die ich beantworten ist: Wie man einen Punkt aus einer gleichmäßigen Verteilung innerhalb eines beliebigen Vierecks erzeugen , das ist eigentlich eine Verallgemeinerung von ist Wie ein Punkt aus einer gleichmäßigen Verteilung innerhalb eines beliebig (konvex) Polygon zu erzeugen. Die Antwort basiert auf dem Fall der Verwendung eine Probe, die von einer gleichmäßigen Verteilung in einem Dreieck zu erzeugen (siehe http: // MathWorld .wolfram.com / TrianglePointPicking.html , die eine sehr schöne Erklärung hat).

Um diese wir zu erreichen:

1. Triangulate das Polygon (d.h. erzeugen eine Sammlung von nicht-überlappenden dreieckigen Bereiche, die das Polygon bedecken). Für den Fall eines Vierecks, schafft eine Kante über zwei beliebige nicht benachbarte Vertices. siehe andere Polygone, http://en.wikipedia.org/wiki/Polygon_triangulation für einen Start Punkt oder http://www.cgal.org/ wenn Sie benötigen nur eine Bibliothek.

   

2. eine der Dreiecke nach dem Zufallsprinzip auszuwählen, kehren wir zu jedem Dreieck einen Index zuzuordnen (d.h. 0,1,2, ...). Für das Viereck, werden sie 0,1 betragen. Für jedes Dreieck weisen wir ein Gewicht gleich wie folgt:

   

3. erzeugt dann einen zufälligen Index i aus der endlichen Verteilung über Indizes aufgrund ihrer Gewicht. Für das Viereck, das ist eine Bernoulli-Verteilung:

   

4. Let v0, v1, Eckpunkte des Dreiecks V 2 (durch ihre Punktpositionen dargestellt, so daß v0 = (x0, y0) usw. Dann haben wir beide erzeugen zwei Zufallszahlen a0 und a1, gezogen gleichmäßig von das Intervall [0,1]. Dann berechnen wir den beliebigen Punkt x durch x = a0 (V1-V0) + a1 (v2-v0).

   

5. Beachten Sie, dass mit einer Wahrscheinlichkeit von 0,5, x außen außerhalb des Dreiecks liegt, aber wenn es der Fall ist, liegt es innerhalb des Parallelogramms der Vereinigung des Dreiecks zusammengesetzt ist damit nach einer Drehung von Pi um den Mittelpunkt des Bildes ist (v1 v2) (Linien im Bild gestrichelt). In diesem Fall können wir einen neuen Punkt x‘= v0 + R (pi) (x - v3) erzeugen, wobei R (pi) ist eine Drehung von pi (180 Grad). Der Punkt x‘wird innerhalb des Dreiecks sein.

6. Ferner ist zu beachten, dass, wenn das Viereck bereits ein Parallelogramm ist, dann brauchen wir uns nicht ein Dreieck nach dem Zufallsprinzip auswählen, können wir entweder eine determinis holen, und dann den Punkt x wählen, ohne Prüfung, dass es innen ist es Quelle Dreieck.

Answer 3

Angenommen, Sie eine gleichmäßige Verteilung wollen: Form zwei Dreiecke aus dem Polygon. Wählen, welche den Punkt in Dreieck entsprechend ihrem Flächenverhältnis zu erzeugen.

Ruf die Ecken des Dreiecks A, B, C, die Seitenvektoren AB, BC, AC und erzeugen zwei Zufallszahlen in [0,1] genannt u und v. Es sei p = u * v * AB + AC.

Wenn A + p ist innerhalb des Dreiecks, Rückkehr A + p

Wenn A + p außerhalb des Dreiecks ist, kehrt A + AB + AC - p

(Dies ist Formel ist grundsätzlich PierreBdR mit Ausnahme der Vorverarbeitung und der letzte Schritt, den Punkt faltet sich zurück in ein Dreieck, so kann es auch andere Formen als Parallelogramme handhaben).

Answer 4

Ihr Polygon zwei Dreiecken, also warum nicht zufällig einen von denen wählen, dann einen beliebigen Punkt im Dreieck finden.

Wahrscheinlich nicht die beste Lösung, aber es würde funktionieren.

Answer 5

Ein etwas weniger „ naiv “ Ansatz wäre ein verwenden < a href = "http://alienryderflex.com/polygon_fill/" rel = "nofollow noreferrer"> Polygonfüllprozedur Algorithmus , und wählen Sie dann Punkte aus den Fülllinien zufällig.

C Codebeispiel

//  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.

Answer 6

Mit dem „allgemeinen“ meinen Sie alle nicht-Parallelogramm 4-seitige Polygone im Allgemeinen oder alle möglichen Polygone?

Wie wäre es eine zufällige Strichzeichnung, die vier Seiten verbindet z.B. Wenn Sie diese haben:

.BBBB.
A    C
A    C
.DDDD.

Dann einen beliebigen Punkt auf einem Einheitsquadrat erzeugen, markiert dann den Punkt auf der Linie B und D auf dem Prozentsatz der Entfernung auf der X-Achse. Machen Sie dasselbe auf der Linie A und C unter Verwendung von Wert aus der Y-Achse.

dann den Punkt auf der Linie A bis Zeile C verbinden und die Linie B D Zeile, wird der Schnittpunkt dann als Zufallspunkt verwendet.

Es ist nicht einheitlich, da Rundungsfehler werden bestimmte Punkte helfen, aber es sollte in der Nähe sein, wenn Sie mit Fließkommawerten arbeiten.

Die Implementierung sollte ziemlich einfach sein, auch, da Sie bereits mit Polygonen arbeiten. Sie sollten bereits einen Code, der diese einfachen Aufgaben der Fall ist.

Hier ist ein kurzer Pseudo-Code:

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

}

Answer 7

Dies funktioniert für die allgemeine konvexe Vierecke:

Sie können einige Konzepte aus der Finite-Elemente-Methode borgen, die speziell für Viereck (4-sided) Elemente ( siehe Abschnitt 16.5 hier ). Grundsätzlich gibt es eine bilineare Parametrisierung, die einen Platz in der uv-Raum abbildet (für u, v \ in [-1, 1] in diesem Fall) zu Ihrem Viereck, das aus Punkten p_i (für i = 1,2,3,4 besteht ). Beachten Sie, dass in der vorgesehenen Referenz die Parameter \ eta und \ xi bezeichnet werden.

Grundrezept:

1. Wählen Sie einen geeigneten Zufallszahlengenerator gut verteilte Punkte in einem quadratischen 2D-Domäne zu erzeugen
2. Erzeugen Sie gelegentliche u-v-Paare im Bereich [-1, 1]
3. Für jedes UV-Paar, der entsprechenden zufällige Punkt in dem Quad = 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)

Das einzige Problem besteht darin, dass gleichmäßig verteilen Punkte in dem u-v-Raum nicht gleichmäßig Punkte in Ihrem Quad verteilt produzieren (im euklidischen Sinne). Wenn das wichtig ist, können Sie innerhalb des Begrenzungsrahmen des Quad direkt in 2D arbeiten und eine Point-in-Quad schreiben (vielleicht durch das Problem in zwei Punkte in Tris Splitting) Test zufällige Punkte keulen, die außerhalb sind.

Answer 8

Sind die Punkte müssen gleichmäßig verteilt werden, oder eine beliebige Verteilung ok?

Kann das Polygon konkav oder konvex ist es guarenteed zu sein?

Wenn die Antwort auf beide der oben nicht ist, dann wählen Sie eine beliebige zwei der Eckpunkte und einen beliebigen Punkt auf dem Liniensegment zwischen ihnen wählen. Dies ist auf die Linie der Vertices Segements verbindet (dh sehr ungleichmäßigen); Sie können ein bisschen besser machen, indem eine dritte Eckpunkt Kommissionierung und dann einen Punkt zwischen diesem und dem ersten Punkt Kommissionierung - noch nicht einheitlich, aber zumindest ein Punkt im Polygon ist möglich

einen zufälligen Punkt Picking auf einer Linie zwischen zwei Punkten ist einfach, nur A + p (B-A), wobei A und B sind die Punkte, und p ist eine Zufallszahl zwischen 0,0 und 1,0

Answer 9

Welche Verteilung wollen Sie die Punkte haben? Wenn Sie sich nicht, funktionieren die oben genannten Methoden in Ordnung. Wenn Sie eine gleichmäßige Verteilung wollen, wird das folgende Verfahren arbeiten: Teilen Sie das Polygon in zwei Dreiecke, a und b. Es sei A (a) und A (b) ihre Bereiche sein. Probe einen Punkt p aus der gleichmäßigen Verteilung auf dem Intervall zwischen 0 und A (a) + A (b). Wenn p

Answer 10

Die MATLAB-Funktion cprnd erzeugt Punkte aus der gleichmäßigen Verteilung auf einem Allgemein konvexen Polytops. Für Ihre Frage ein spezialisierter Algorithmus, der auf das Viereck in Dreiecke auf Zersetzung effizienter ist.

Answer 11

Für PostGIS, ist es das, was ich benutze (man könnte für mögliche Endlosschleifen eine Station wollen). Sie könnten den Algorithmus zu Ihrer Programmiersprache exportieren:

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;