Random mesh grid

[KomplexKompliziert]

Hallo zusammen!
Ich muss ein Random mesh grid in python implementieren. Hat jemand eine Idee? Am liebsten wäre es mir, wenn ich nur die Pakete nympy, matplotlib, pylab und scipy benötigen würde.
Wäre super, wenn mir jemand helfen könnte!!

[EyDu]

Ich würde ja einfach mal anfangen es zu implementieren ...

[KomplexKompliziert]

ich hab jetzt erstmal ein gewöhnliches Gitter implementiert und zwar so

Code: Alles auswählen

x=linspace(0,0.6,3)
y=linspace(0,0.6,3)
X,Y=meshgrid(x,y)
ylim(-0.1,1)
xlim(-0.1,1)
plot(X,Y,'y')
plot(Y,X,'y')
show()

Das macht mir aber immer ein rechteckiges Gitter. Ich bräuchte aber etwas, das mir verschiedene Formen in dem Gitter gibt, also z.B. Dreiecke, Rechtecke, Kreise,.... Pro aufruf sollte das Gitter dann immer anders aussehen (also zufällig).

[EyDu]

Wo hakt es denn bei dir genau? Ist es der Algorithmus an sich oder die Umsetzung in Python?

[KomplexKompliziert]

Ich hab im Netz leider jetzt kein besseres Bild gefunden, aber ich bräuchte ein Netz, das so ähnlich wie (b) aussieht (es muss ein zufälliges Gitter sein) - und das geht mit meshgrid doch nicht oder?

oder auch die rechte Grafik

[deets]

Ja und jetzt? Wo ist das Problem, ein gleichmaessiges Grid zu erzeugen, und dann die Stuetzpunkte randomisiert zu verschieben?

[EyDu]

Wenn du uns nicht verräts, was du eigentlich machen willst, dann kann man dir nur mit Allgemeinplätzen antworten. Welche Anforderungen stellst du denn an das Gitter und was willst du damit machen? Mus es regelmäßig sein und dann nur noch transformiert werden? Was hat es mit den Formen auf sich? Müssen die Kanten überschneidungsfrei sein? Oder reicht vielleicht ein zufälliger Graph aus? Den könnte man dann leicht mit Voronoi oder Delaunay aus zufälligen Punkten erstellen. Und sollte es zu dem Thema nicht das eine oder andere Buch oder Paper geben?

[KomplexKompliziert]

1. Ich glaube, das hab ich gesucht:

Stuetzpunkte randomisiert [..] verschieben

. Dann muss ich die Stützpunkte in linspace randomisieren. Ist das richtig?

2. Der Vorschlag von EyDu ist aber auch gut. In der Literatur steht, dass man ein sehr sehr feines zufälliges Netz erzeugen soll und dies als Graph interpretieren. In diesem Netz existieren ausgewählte Punkte/Knoten und diese Punkte soll ich dann später mit einem neuen Algorithmus einen Steinerbaum basteln.
Das Netz darf nicht regelmäßig sein, aber ein sehr sehr feiner zufälliger Graph würde vielleicht auch gehen.

Ich werde beide Varianten mal ausprobieren!
Vielen Dank!

[EyDu]

Kurz mal gezimmert:

Code: Alles auswählen

import matplotlib
import matplotlib.pyplot as plt
import numpy as np
import scipy.spatial


points = np.random.rand(100, 2)
delaunay = scipy.spatial.Delaunay(points)

edges = set()
for vertex in delaunay.vertices:
    for index, i in enumerate(vertex):
        j = vertex[(index + 1) % 3]
        edges.add((min(i, j), max(i, j)))

lines = [(delaunay.points[i], delaunay.points[j]) for (i, j) in edges]

fig = plt.figure()
ax = fig.add_subplot(111)

for (sx, sy), (ex, ey) in lines:
    ax.plot([sx, ex], [sy, ey])

plt.axis("equal")
plt.show()

Wird bei vielen Punkten natürlich schon ganz schön langsam.

[KomplexKompliziert]

Hey das ist ja super!!!!!
Ich danke dir!

[EyDu]

Und wenn man sich beim Zeichnen nich so dumm anstellt wie ich, dann kann man auch wirklich große Graphen bauen

Code: Alles auswählen

import matplotlib.pyplot as plt
from matplotlib.collections import LineCollection
import numpy as np
import scipy.spatial

points = np.random.rand(10000, 2)
delaunay = scipy.spatial.Delaunay(points)

edges = set()
for vertex in delaunay.vertices:
    for index, i in enumerate(vertex):
        j = vertex[(index + 1) % 3]
        edges.add((min(i, j), max(i, j)))


lines = LineCollection(
    (delaunay.points[i], delaunay.points[j])
    for (i, j)
    in edges)

plt.gca().add_collection(lines)
plt.axis("equal")
plt.show()

Du könntest noch die gleichverteilten Punkte durch Quasi-Zufallszahlen ersetzen. Dann sind die lokalen Dichteunterschiede weniger stark ausgeprägt und das ganze sieht wieder etwas mehr nach einem Gitter aus, bzw. nach dem Verfahren, mit dem du die Quasi-Zufallspunkte anordnest.