Zufällige Punkte in einem Parallelogramm

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

1. Nehmen Sie sich zwei Zufallszahlen zwischen 0 und 1. Wir rufen Sie dann u und v.

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

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

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

B. Jetzt, wenn Sie nicht, können Sie immer noch die barycentric coordinates. Die barycentric coordinates entsprechen, für ein quad, 4-Koordinaten (a,b,c,d) so dass a+b+c+d=1. Dann, einen beliebigen Punkt P innerhalb der quad kann beschrieben werden durch eine 4-uple:

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

In Ihrem Fall, können Sie ziehen 4 Zufallszahlen und zu normalisieren, so dass Sie bis zu 1. Geben Sie einen Punkt. Beachten Sie, dass die Verteilung der Punkte wird NICHT einheitlich sein in diesem Fall.

C. Sie können auch, wie vorgeschlagen, anderswo, zerlegen Sie die quad in zwei Dreiecke und verwenden die Hälfte-Parallelogramm-Methode (d.h., als das Parallelogramm, aber Sie fügen Sie die Bedingung u+v=1) oder die barycentric coordinates für Dreiecke. Allerdings, wenn Sie möchten, gleichmäßige Verteilung, die Wahrscheinlichkeit, dass ein Punkt in einem Dreieck gleich sein müssen, um die Fläche eines Dreiecks, dividiert durch die Fläche des quad.

InformationsquelleAutor der Antwort PierreBdR

Angenommen, Sie wollen eine gleichmäßige Verteilung: Bilden zwei Dreiecke, die von Ihr polygon. Wählen Sie, welches Dreieck zu erzeugen, der Punkt, in der je nach Gebiet-Verhältnis.

Rufen Sie die Ecken des Dreiecks A, B, C, die Seite Vektoren AB, BC, AC und erzeugt zwei Zufallszahlen in [0,1] wird aufgerufen, u und v. es seien p = u * AB + v * AC.

Wenn A+p liegt innerhalb des Dreiecks, return A+p

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

(Dies ist im Grunde PierreBdR-Formel-außer für die Vorverarbeitung und den letzten Schritt Falten Sie den Punkt wieder in ein Dreieck, so kann es die Behandlung anderer Formen als Parallelogramme).

InformationsquelleAutor der Antwort jakber

Etwas weniger " naiv " - Ansatz wäre die Verwendung einer polygon fill algorithm, und wählen Sie Punkte aus der fill-Linien nach dem Zufallsprinzip.

C-Code-Beispiel

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

InformationsquelleAutor der Antwort wprl

Diese Werke für die Allgemeine, konvexe Vielecke:

Können Sie leihen einige Konzepte aus der Finite-Elemente-Methode, insbesondere für viereck (4-seitiges) Elemente (finden Sie im Abschnitt 16.5 hier). Grundsätzlich gibt es eine Bilineare Parametrisierung, dass die Karten einen Platz in der u-v-Raum (für u, v \in [-1, 1] in diesem Fall) zu Ihrem viereck, die aus Punkten besteht p_i (i = 1,2,3,4). Beachten Sie, dass sofern Referenz, die Parameter genannt werden \eta \xi.

Basic-Rezept:

1. Wählen Sie einen geeigneten Zufallszahlengenerator zu erzeugen, gut verteilte Punkte in einem Quadrat der 2D-domain
2. Generate random u-v-Paare in dem Bereich [-1, 1]
3. Für jede u-v-pair-Mädchen, den entsprechenden zufälligen Punkt in Ihrem 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 problem ist nur, dass gleichmäßig verteilte Punkte in der u-v-Raum nicht produzieren gleichmäßig verteilte Punkte in Ihrem quad (im euklidischen Sinne). Wenn das wichtig ist, können Sie direkt in 2D innerhalb der bounding box die quad und schreiben Sie eine point-in-quad (vielleicht durch die Aufteilung des Problems in zwei Punkt in tris) test zu pflücken zufällige Punkte, die draußen sind.

InformationsquelleAutor der Antwort Not Sure

Welche Art von distribution Sie wollen die Punkte zu haben? Wenn Sie sich nicht sorgen, die oben genannten Methoden funktionieren. Wenn Sie möchten, eine gleichmäßige Verteilung, die folgende Prozedur funktioniert: Teilen Sie das polygon in zwei Dreiecke, a und b. Lassen Ein(a) und(b) werden Ihre Bereiche. Beispiel eines Punktes p von der gleichmäßigen Verteilung auf das Intervall zwischen 0 und A(A)+(b). Wenn p < Ein(a), wählen Sie im Dreieck ein. Wählen Sie andernfalls Dreieck b. Wählen Sie einen vertex v von der gewählten Dreieck, und lassen c und d werden die entsprechenden Vektoren der Seiten des Dreiecks. Beispiel zwei zahlen x und y aus der exponential-Verteilung mit unit-Durchschnitt. Dann ist der Punkt (xc+yd)/(x+y) ist eine Stichprobe aus der Gleichverteilung auf dem polygon.

InformationsquelleAutor der Antwort Alex Coventry

Für PostGIS, das ist, was ich verwende (vielleicht möchten Sie eine Gemeinde für möglich, Endlosschleifen). Sie könnten den export der Algorithmus zu Ihrer Programmiersprache:

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;

InformationsquelleAutor der Antwort