Generiert zufällige Koordinaten um einen Standort
Ich würde gerne eine Funktion akzeptiert eine geo-location (Latitude, Longitude) und generiert zufällige Sätze von Koordinaten, die um es herum, sondern nimmt auch diese Parameter als Teil der Berechnung:
- Anzahl Der Zufälligen Koordinaten Um
- Radius zu erzeugen, in
- Min Abstand zwischen den zufälligen Koordinaten in Metern
- Die root-Koordinaten zu erzeugen, die locations um ihn herum.
Beispiel dafür, wie die generation wäre:
Was ist ein guter Ansatz um dies zu erreichen?
- Zum Beispiel könnten Sie wählen Sie eine Regel - oder gleichmäßig verteilt radius mit vorgeschriebenen Mittelwert oder range und einer gleichmäßig verteilten Winkel.
- Und dann mit einem brute-force-Methode zu überprüfen, den Abstand zwischen den Punkten 🙂
- Ja, man konnte wählen Sie einen zufälligen Winkel und einen zufälligen radius. Aber immer die zufälligen Winkel nach rechts ist wohl schwierig. Könnte besser sein, zu wählen (innerhalb der Grenzen, die gehören der Kreis) zufällige X-und Y-Werte, und diejenigen ausschließen, die nicht in den Kreis (sqrt(X2 + Y2)).
- Wie viele Meter ist ein pixel?
- Was ist der Zweck dieser Aufgabe? Eine Art von wissenschaftlicher Forschung? oder Visualisierung? Was ist die maximale Anzahl der Punkte? Was ist das wichtigste problem, das Sie derzeit konfrontiert? Die Geschwindigkeit?
- Irgendwie, das Hauptproblem ist wirklich die Geschwindigkeit.
- Der schwierige Teil des Problems ist die minimale Distanz. Erzeugung von Zufallszahlen Punkte machen es schwieriger und schwieriger zu finden, einen Punkt Befestigung. Vielleicht, wenn dies ist zufällig genug, Sie könnte die erste partition der Kreis im Quadrat in den Kreis, und platzieren Sie Punkte in zufälliger verfügbaren Plätze?
Du musst angemeldet sein, um einen Kommentar abzugeben.
Einem brute-force-Methode sollte gut genug sein.
In PHP, generieren Sie einen neuen Punkt einfach
Dann Berechnung der Distanz zwischen zwei Punkten
** Bearbeiten **
Für die Klarheit, was andere gesagt haben, und nach einigen weiteren Recherchen (ich bin kein Mathematiker, aber die Kommentare hat machen Frage ich mich), hier die einfache definition einer Gauß-Verteilung :
Deshalb, um eine Normalverteilung, würden Sie ändern die Zeile des generierten radius zu
wie andere vorgeschlagen haben.
O(n^2)
Laufzeit, während es kann leicht seinO(n log n)
0
und359000
und dividieren Sie das Ergebnis durch1000
für ein Tausendstel Wert für die Genauigkeit, etc. Und, ja, der radius sollte auch zufällig sein 🙂Generieren von zufälligen Koordinaten um einen Standort
Nutzung
als die andere Antwort sagt, der einfachste Ansatz wird sein, die Generierung von Zufallszahlen Punkte und dann verwerfen Sie diejenigen, die zu nah an anderen (vergessen Sie nicht zu prüfen, min Entfernung zum zentralen Punkt zu, falls nötig).
jedoch die Generierung der zufälligen Punkte ist schwerer als erklärt. zuerst müssen Sie wählen Sie den radius nach dem Zufallsprinzip. zweitens müssen Sie, um mehr Punkte bei großen Radien (weil es "mehr Raum" da draußen"). so können Sie nicht nur make-radius eine einheitliche Zufallszahl.
stattdessen wählen Sie eine Zahl zwischen 0 und
$radius * $radius
. dann nehmen Sie diesqrt()
zu finden, der radius zur Handlung auf (das funktioniert, weil die Fläche proportional zum Quadrat des radius).ich weiß nicht, php (sehen, die Korrektur von Karolis in den Kommentaren), aber von der anderen Antwort, die ich denke, dass würde bedeuten:
dann überprüfen Sie, dass gegen die vorstehenden Punkte wie bereits beschrieben.
schließlich, vergessen Sie nicht, dass Sie einen Zustand erreichen, wo können Sie generieren keine Punkte mehr, so möchten Sie vielleicht, um eine Obergrenze auf den "try and discard" - Schleife zu vermeiden, auf eine unendliche Schleife, wenn der Raum ist (fast) voll.
ps wie ein Kommentar sagt, auf eine andere Antwort, das ist O(n^2) und damit ungeeignet für eine große Anzahl von Punkten. Sie können die Adressen, die zum Teil durch die Sortierung der Punkte von radius und nur wenn man diejenigen, die innerhalb einer Differenz von
$min_distance
, solange$min_distance << $max_radius
(wie es in der Zeichnung); besser als das erfordert eine komplexere Lösung (zum Beispiel bei größeren Radien auch über Winkel, oder über eine separate quad-Baum zu speichern und zu vergleichen, Positionen). aber für zehn Punkte, die ich mir vorstellen, dass wäre nicht nötig.mt_rand()
Funktion gibt eine Ganzzahl zurück, das ist nicht das, was wir brauchen. Wir können zufällige Winkel mit diesem:$angle = lcg_value() * 2 * pi()
. Und random-radius mit dieser:$radius = sqrt(lcg_value() * $max_radius * $max_radius)
Andere haben bereits erklärt, die Mathematik, die Sie brauchen. Aber ich denke, die problematischste Teil ist die Leistung. Die brute-force-Methode zum überprüfen der Abstände zwischen den Punkten können gut genug sein, wenn Sie über 50 Punkte nur. Aber zu langsam, wenn du 1000 Punkte oder noch mehr. Für 1000 Punkte dies erfordert mindestens eine halbe million Operationen.
Daher wäre mein Vorschlag für das speichern aller zufällig generierten Punkte in B-Baum oder binary search tree (von x-Wert und y-Wert). Mit einer geordneten Struktur werden Sie in der Lage, die Punkte zu Holen die in der Gegend [x ± min_distance, y ± min_distance] effizient. Und diese sind die einzigen Punkte, die geprüft werden müssen, drastisch reduzieren die Anzahl der benötigten Operationen.