Generieren zufällige Stellen innerhalb einer dreieckigen Domäne

Question

I xy und mit einer gleichmäßigen Verteilung und begrenzt durch [xmin,xmax] und [ymin,ymax]

die Punkte (x, y) soll innerhalb eines Dreiecks erzeugen soll.

Wie kann ich ein solches Problem lösen?

Answer 1

Uniform auf dem Dreieck?

import numpy as np 

N = 10 # number of points to create in one go 

rvs = np.random.random((N, 2)) # uniform on the unit square 
# Now use the fact that the unit square is tiled by the two triangles 
# 0 <= y <= x <= 1 and 0 <= x < y <= 1 
# which are mapped onto each other (except for the diagonal which has 
# probability 0) by swapping x and y. 
# We use this map to send all points of the square to the same of the 
# two triangles. Because the map preserves areas this will yield 
# uniformly distributed points. 
rvs = np.where(rvs[:, 0, None]>rvs[:, 1, None], rvs, rvs[:, ::-1]) 

Finally, transform the coordinates 
xmin, ymin, xmax, ymax = -0.1, 1.1, 2.0, 3.3 
rvs = np.array((ymin, xmin)) + rvs*(ymax-ymin, xmax-xmin) 

Gleichmäßige marginals? Die einfachste Lösung wäre, gleichmäßig die Masse auf der Linie (ymin, xmin) zu konzentrieren - (ymax, xmax)

rvs = np.random.random((N,)) 
rvs = np.c_[ymin + (ymax-ymin)*rvs, xmin + (xmax-xmin)*rvs] 

aber das ist nicht sehr interessant, oder?

Answer 2

Schritt (1): Erzeugen eines xr in [xmin, xmax] und yr in [ymin, ymax] mit einer Zufallszahl eines Koordinaten Python random function

für Schritt (2): Verwerfen der anderen Zufall einer Koordinate und wählt, wenn [xr, yr] nicht innerhalb nicht liegen das Dreieck. Es gibt verschiedene Möglichkeiten, um zu überprüfen, ob der Punkt innerhalb eines konvexen Polygon wie ein Dreieck ist, zum Beispiel:

• Dividing das Dreieck in drei Unterdreiecken und die Überprüfung, ob die Fläche der drei Teildreiecke dieselbe hat Größe wie das ursprüngliche Dreieck
• für jede Linie des Dreiecks überprüft, ob die Zufalls liegt auf der gleichen Seite der Ebene wie der dritte Punkt der baryzentrischen Koordinaten

die beiden letzteren Verwendung

Dreiecks-Koordinaten Strategien werden näher erläutert in this article

Es gibt mehrere Methoden, aber diese drei sind in Python auch mit wenig mathematischem Hintergrund einfach zu implementieren.

P. S .: Wikipedia-Links auch zu this article describing several methods mit Beispielcodes

Answer 3

Es ist ein wenig unklar mir, was Sie fordern, aber hier ist einige Code, der Punkte gleichmäßig auf einem beliebigen Dreieck in der Ebene erzeugt.

import random 

def point_on_triangle(pt1, pt2, pt3): 
    """ 
    Random point on the triangle with vertices pt1, pt2 and pt3. 
    """ 
    s, t = sorted([random.random(), random.random()]) 
    return (s * pt1[0] + (t-s)*pt2[0] + (1-t)*pt3[0], 
      s * pt1[1] + (t-s)*pt2[1] + (1-t)*pt3[1]) 

Die Idee ist, ein gewichtetes Mittel der drei Scheitelpunkte zu berechnen, wobei die von einem Zufallsgenerator Bruch des Einheitsintervalls [0, 1] in drei Stücke (gleichmässig über alle solche Pausen) angegebenen Gewichte.

Hier ist ein Beispiel für die Verwendung, die 10000 Punkte in einem Dreieck erzeugt:

pt1 = (1, 1) 
pt2 = (2, 4) 
pt3 = (5, 2) 
points = [point_on_triangle(pt1, pt2, pt3) for _ in range(10000)] 

und ein Grundstück von oben erhalten, was zeigt die Gleichförmigkeit.Das Grundstück wurde von diesem Code generiert:

import matplotlib.pyplot as plt 
x, y = zip(*points) 
plt.scatter(x, y, s=0.1) 
plt.show() 

Hier ist das Bild:

Und da Sie die Frage mit dem „numpy“ Tag markiert, hier ist eine NumPy Version, die mehrere Proben erzeugt an Einmal. Beachten Sie, dass es den Matrixmultiplikationsoperator @ verwendet, der in Python 3.5 eingeführt wurde und in NumPy> = 1.10 unterstützt wird. Sie müssen dies durch einen Aufruf an np.dot für ältere Python oder NumPy-Versionen ersetzen.

import numpy as np 

def points_on_triangle(v, n): 
    """ 
    Give n random points uniformly on a triangle. 

    The vertices of the triangle are given by the shape 
    (2, 3) array *v*: one vertex per row. 
    """ 
    x = np.sort(np.random.rand(2, n), axis=0) 
    return np.column_stack([x[0], x[1]-x[0], 1.0-x[1]]) @ v 


# Example usage 
v = np.array([(1, 1), (2, 4), (5, 2)]) 
points = points_on_triangle(v, 10000) 

Answer 4

Ok, Zeit, um eine andere Version hinzuzufügen, denke ich. Es gibt einen bekannten Algorithmus zum gleichmäßigen Abtasten im Dreieck, siehe paper, Kapitel 4.2 für Details.

Python-Code:

import math 
import random 

import matplotlib.pyplot as plt 

def trisample(A, B, C): 
    """ 
    Given three vertices A, B, C, 
    sample point uniformly in the triangle 
    """ 
    r1 = random.random() 
    r2 = random.random() 

    s1 = math.sqrt(r1) 

    x = A[0] * (1.0 - s1) + B[0] * (1.0 - r2) * s1 + C[0] * r2 * s1 
    y = A[1] * (1.0 - s1) + B[1] * (1.0 - r2) * s1 + C[1] * r2 * s1 

    return (x, y) 

random.seed(312345) 
A = (1, 1) 
B = (2, 4) 
C = (5, 2) 
points = [trisample(A, B, C) for _ in range(10000)] 

xx, yy = zip(*points) 
plt.scatter(xx, yy, s=0.2) 
plt.show() 

und das Ergebnis sieht aus wie