Wie identifiziere ich, in welche Region ein zufällig generierter Punkt auf einer Karte fällt?Ich habe diese Frage bereits auf stackoverflow gepostet wurde aber auf die Community hingewiesen, da diese eher eine Antwort bekommt. Es gibt auch eine Bilddarstellung meines Problems.
Im Wesentlichen habe ich eine "Karte", die aus mehreren rechteckigen Regionen besteht. Ich habe Zugriff auf die Koordinaten aller Scheitelpunkte jeder rechteckigen Region (ihre x_min, x_max, y_min, y_max).
Ich erzeuge zufällig einen Punkt, der irgendwo auf dieser Karte liegt. Ich kenne die Koordinaten dieses Punktes (x und y). Das Problem, das ich lösen möchte, ist herauszufinden, in welcher Region der Punkt liegt.
Was ich getan habe, ist einfach eine große Bedingungsanweisung durchzugehen, die nacheinander überprüft, ob die x- und y-Koordinate des Punkts zwischen x_min und x_max und y_min und y_max jeder Region liegt. Ich habe jedoch das Gefühl, dass es dafür einen skalierbareren, verallgemeinerbaren und effizienteren Weg geben muss, aber ich kann keinen Weg dazu finden, zumindest nicht etwas, das nicht in einer Bibliothek für eine andere Programmiersprache enthalten ist. Ich dachte daran, vielleicht etwas zu tun, wo ich die Karte in zwei Hälften teile, finde heraus, in welcher Hälfte der Punkt liegt, zähle alle Regionen in dieser Hälfte, prüfe, ob noch eine Region übrig ist und wenn nicht, teile die Karte wieder in zwei Hälften und den Vorgang noch einmal durchlaufen. Ich habe einfach keine gute Vorstellung davon, wie das umgesetzt werden kann und ob das machbar ist oder besser als die aktuelle Methode, die ich habe.
SkriptingFensterBetreff: Wie identifiziere ich, in welche Region ein zufällig generierter Punkt auf einer Karte fällt?Wenn ich einen Algorithmus für die gekachelten rechteckigen Bereiche erfinden würde, würde ich die KDTable-Funktion verwenden und alle Eckpunkte in die Tabelle laden. Etwas wie das:
ein bis vier Rechtecke teilen sich jede Ecke
Die KDTable erkennt effizient, welche Ecke einer abgefragten xy-Position am nächsten liegt. Wenn Sie eine weitere Tabelle aller Rechtecke führen, die diesen Punkt teilen, müssen Sie nur bis zu vier ankreuzen. Je nachdem, wie Sie die Daten anordnen, sagt nur die Kenntnis von
Die KDTable macht ziemlich genau das, was Sie beschrieben haben, in K-Dimensionen. für xy-Daten K==2.
Betreff: Wie identifiziere ich, in welche Region ein zufällig generierter Punkt auf einer Karte fällt?Oder vielleicht ist es schwieriger.
Dies wird die falsche Ecke finden.
Betreff: Wie identifiziere ich, in welche Region ein zufällig generierter Punkt auf einer Karte fällt?Wie viel Auflösung benötigen Sie? Wenn eine 10K x 10K Bitmap gut genug wäre und es weniger als 16E6 Polygone gibt, können Sie die Rechtecke mit einzigartigen Farben in die Bitmap zeichnen (2^24 Farben sind 16 Millionen Farben) und sofort ein gerundetes xy-Pixel abfragen. Ich habe so etwas gemacht in JSL-BLOB in einer ESP32-Uhr für GPS-Lookups in einer Zeitzonenkarte. In meinem Fall nahm ich die Auflösung, die ich erreichen konnte, nämlich ein oder zwei Meilen in der Nähe einer Zeitzonengrenze; Ich brauchte nicht die Geschwindigkeit, sondern die Möglichkeit, die Bitmap in Lauflängen zu codieren, damit sie auf einen winzigen Computer passt.
Edit: anscheinend habe ich eine so große Bitmap erstellt
composition = J( 16000, 30000, 0 );
die entweder keinen Speicher mehr hatte oder eine Pixelgrenze überschritten, wenn ich größer wurde ... Ich habe 16000 für den +/- 90-Grad-Breitengrad und 30K (nicht 32K) für den +/- 180-Grad-Längengrad verwendet. Das ist über ein GB unkomprimiert. Sie benötigen eine PNG-Datei, kein JPG. JPG würde die Farben nicht beibehalten.
Betreff: Wie identifiziere ich, in welche Region ein zufällig generierter Punkt auf einer Karte fällt?Da die Rechtecke nicht gedreht zu sein scheinen und sich nicht überlappen:
Vier Kontrollen/Schleifen und entfernen Sie immer diejenigen, die nicht übereinstimmen:
1. Suche nach allen Quadraten, deren x_min kleiner als x . des Punktes ist
2. Überprüfe aus allen verbleibenden Quadraten, deren x_max größer als x . des Punktes ist
3. Überprüfe aus allen verbleibenden Quadraten, deren y_min kleiner als das y . des Punktes ist
4. Überprüfe aus allen verbleibenden Quadraten, deren y_max größer als das y . des Punktes ist
Und Sie können an jedem Punkt davon anhalten, wenn nur noch ein Feld übrig ist. Im Fall von JMP können Sie dies mit Hilfe von Loc() tun.
Oder durchlaufen Sie dann alle Quadrate Min-Max-Werte und brechen Sie ab, wenn Sie eine Übereinstimmung mit etwas finden wie:
:xmin < x < :xmax & :ymin < y < :ymax
Einige Links, die verwandt sein könnten und ausgefallenere mögliche Lösungen haben:
https://stackoverflow.com/questions/1897779/test-if-point-is-in-some-rectangle
https://www.reddit.com/r/programming/comments/80dlc/i_have_a_set_of_rectangles_and_need_to_determine/
