Ermitteln aller durch ein Rechteck "abgedeckter" Gebiete in einen QuadTree
-
Hallo, hab folgendes Algorithmisches problem.
Ich habe eine Fläche. Diese Teile ich je nach bedarf immer wieder in Viertel.
Also zuerst ist es ein Rechteck, nach einer Itererierung sind es 4 Rechtecke. Hier kann ich wieder eines der Subrechtecke auswählen und wieder Teilen. Die Teilung erfolgt nicht mittig. Für die REchtecke ist mir aber immer bekannt wo es geteilt wurde, und wie groß es ist. Das ganze könnte z.B. So aussehen
+---------+-----------+------------------------------------------+ | | | | +---------+-----------+ | | | | | +---------+-----------+--------------+---------------------------+ | | | | | | | | | +--------------+--------------+------------+ | | | | | | | +--------------+------------+ | | | | | +---------------------+--------------+--------------+------------+Jetzt möchte ich in diese Ebene ein Rechteck legen und schauen welche Regionen Teil des Rechtecks sind.
+---------+-----------+------------------------------------------+ | | | | +---------+-----------+ | | | O | O | +---------+-----------+--------------+---------------------------+ | | | | | | | | | +--------------+--------------+------------+ | | | | | | | +--------------+------------+ | O | | O | | +---------------------+--------------+--------------+------------+Die 0 seien die Eckpunkte des Rechteckes
+---------+-----------+------------------------------------------+ | | | | +---------+-----------+ X | | | X | | +---------+-----------+--------------+---------------------------+ | | X | | | | | X | | X +--------------+--------------+------------+ | | | X | | | | X +--------------+------------+ | | | X | | +---------------------+--------------+--------------+------------+X sind die Gebiete welche Teil des Rechteckes sind.
Mir fällt gerade überhaupt kein Ansatz ein zu ermitteln welche Rechtecke Abgedeckt werden.
Die Datenstruktur ist ein Baum, die Äste haben immer genau die 4 regionen (oben_links,oben_rechts,unten_links,unten_recht) diese können jeweils wieder andere Äste sein, oder ein Leaf. Die Äste kennen halt ihre Grenzen (MaxX,MaxY,MinX,MinY) und ihre Sub-Äste. Ein Leaf kennt nur seine Grenzen.
Ich hab kein Problem zu ermitteln in welche Gebiet ein Punkt liegt, aber das mit den REchtecken krieg ich nicht hin. Ggf kennt jemand einen Ansatz.
-
Mir ist ein erster Ansatz eingefallen, da ich die Grenzen der Gebiete kenne. Könnte ich für jedes Leaf prüfen ob die obere oder untere Grenze des Gebietes innerhalb des Rechteckes liegt. Das gleiche mache ich für die Linke und rechte Grenze. Wenn nur eines davon zutrifft ist die Region Teil der Gesuchten menge. Ggf gibts aber bessere Ansätze.
-
Du musst nicht jedes Leaf überprüfen. Die Rekursion ist recht einfach:
Pseudo-Code
ausgabeblatt(blatt); alleblaetteraufzaehlen(q_baum_knoten) { if (ist_blatt(q_baum_knoten)) ausgabeblatt(q_baum_knoten); for alle kinder k von q_baum_knoten alleblaetteraufzaehlen(k); } machdas(q_baum_knoten, abfrage_rechteck) { schnittmenge = schnitt(q_baum_knoten.box, abfrage_rechteck); if (schnittmenge == leer) return; if (schnittmenge == q_baum_knoten.box) { // Knoten ist komplett im Abfragerechteck drin. // Das gilt dann auch automatisch für alle // Kindknoten --> keine Schnitttests mehr nötig. alleblaetteraufzaehlen(q_baum_knoten); } else { if (ist_blatt(q_baum_knoten)) { ausgabeblatt(q_baum_knoten); } else { for alle kinder k von q_baum_knoten machdas(k, abfrage_rechteck); } } }
-
Stimmt, ich hatte getrost ignoriert das
1.) bestimmte Regionen gar nicht in Frage kommen können.
2.) wenn eine Region komplett enthalten ist, diese eigentlich nicht näher geprüft werden muss.2.) Kann ich weiterhin ignorieren, ich brauche eh alle leafs. Auch wenn ich weiss das eine Bestimmte Region komplett in Frage kommt, muss ich dort eh reinschauen um die Leafes dort drinne zu bekommen. 1. Muss ich noch mit in betracht ziehen um unnötige Prüfungen zu vermeiden.
Besten Dank für den Hinweis.
-
Wieso (2) ignorieren? Da geht's doch um das Vermeiden von unnötigen Schnitttests. Im Pseudocode rufe ich da
alleblaetteraufzaehlenauf, welches Dir auch hier für all die Blätter ein X erzeugen sollte.So, wie ich das sehe, ist das genau das richtige, um alle "Xe" zu erfahren und dabei die Zahl der Schnitttests klein zu halten. Es sollte damit Deine Frage beantworten.
-
So, das klappt. Jetzt wollte ich das ganze noch für Linien machen. Also wirklich prüfen durch welche Regionen eine Linie läuft (Hatte ja ein ähnliches Problem schonmal mit festgelegten Regionengrößen, aber der Algo zieht ja hier nicht).
Die Trivallösung wäre ja:
1.) Ermittle alle Regionen für das Rechteck welches durch den Start/Endpunkt der Linie definiert wird.
2.) Prüfe für jede dieser Region ob die Linie innerhalb dieser liegt.Dabei Prüfe ich zuviel ab. Besser wäre ja folgendes:
1.) Start am Startpunkt der Linie und Schaue an welchen Punkt er diese Region verlässt.
2.) Suche die Ermittelte Region und mache dort wieder das gleiche
3.) Mache 1. 2. Solange bis der Endpunkt erreicht ist.Jetzt habe ich aber folgendes Problem:
Die Grenzen meiner Region sind als Floats definiert.
Ein punkt ist denn innerhalb der Region wenn sein X Wert >= Linke Grenze und < als Rechte Grenze.
Das gleiche für Y mit oberer und unterer Grenze.
Ggf fällt einem jetzt schon das Problem auf. Wie bestimme ich den nächsten Punkt wenn die Linie die Region nach oben oder links Verlässt. Ich kann maximal den letzten Punkt ermitteln der in meiner Region liegt.
Als einfachstes Mittel könnte reichen einfach von der Linken oder Oberen Grenze ein festes Delta Subtrahieren und dafür den nächsten Punkt berechnen. Wenn das Delta dabei zu groß ist, könnte es aber sein das ich mir Regionen wegsubtrahiere. Was ggf bei der beschränkten Genauigkeit von Floats nicht relevant wäre. Ggf kennt jemand bessere Ansätze.
-
Die Linie sei als Startpunkt und Endpunkt gegeben. Einen Punkt der Linie kannst Du über t parametrisieren, p(t) = start + differenz * t, wobei differenz = end-start. Wenn Du innerhalb einer Region bist und differenz.x>=0 gilt, musst Du die Schnittpunkte mit der linken Wand nicht testen, wenn Du wissen willst, wo die Region verlassen wird. Wenn differenz.x<=0 gilt, musst Du nie Schnittpunkte mit der rechten Want testen. Das gleiche gilt für die y-achse.
(1) Setze t=0, such die Zelle c, die p(0) enthält (von der Wurzel aus)
(2) Wenn der Endpunkt in c auch enthalten ist, bist Du fertig [END]
(3) Berechne den Schnittpunkt zwischen Linie und ein bis zwei Wände der Zelle, die in Frage kommen (nur 1-2 Schnitte notwendig). Sanity check: altes t <= neues t.
(4) Hol Dir je nach getroffene Wand die neue Nachbar-Zelle und mach weiter bei 2Statt in (4) den Baum komplett von der Wurzel aus wieder runterzulaufen, solltest Du Dir in den Kind-Knoten auch Zeiger zu Vater-Knoten merken und Dir eine Funktionen der folgenden Art basteln:
Knoten* benachbartesBlatt( Knoten* subbaum, // aktueller Unterbaum vec2d punkt, // Punkt am Rand im Einzugsgebiet des Unterbaums richtung r // Nachbar-Richtung (hoch/runter/links/rechts) );Die Funktion wandert den Baum ausgehend von
blatthoch so lange bis man an eine Gabelung gekommen ist, in der man einen anderen Pfad (hoch/runter/links/rechts) einschlagen kann, um zur richtigen Nachbarzelle zu kommen. Ab dann kann man sich dann wieder an der Punktkoordinate orientieren, um das richtige Blatt zu finden. Damit umgehst Du numerische Probleme, brauchst auch kein "epsilon" irgendwo drauf addieren und reduzierst gleich noch die Zahl der Knoten, die angefasst werden müssen, da man im Baum typischerweise nicht weit laufen muss und nur ganz selten zwischendurch bis kurz zur Wurzel hoch muss...
-
Ich glaube wir sind fast exakt auf den gleichen Algorithmus gekommen. Ich implementier gerade nahezu das gleiche was du Vorschlägst. (Hoffe ich zumindest, schließlich ist heut Freitag nachmittag [und das den ganzen Tag lang])
(4) Hol Dir je nach getroffene Wand die neue Nachbar-Zelle und mach weiter bei 2
Das ist etwas schwieriger, je nach aufbau kann eine Zelle ja mehrere Nachbarzellen haben. Also wenn ich weiss das ich die Aktuelle Region nach oben verlasse, ist damit noch nicht klar in welcher Region ich dort prüfen muss. Durch meine Idee mit dem Delta, kann ich zumindest noch ermitteln in welcher Region ich ankomme.
| | | X | | | | X | +---------+----------+-------------X-------------+ | X | | X |
-
Fedaykin schrieb:
(4) Hol Dir je nach getroffene Wand die neue Nachbar-Zelle und mach weiter bei 2
Das ist etwas schwieriger, je nach aufbau kann eine Zelle ja mehrere Nachbarzellen haben.
Daher habe ich eine Funktion vorgeschlagen, die auch eine 2D koordinate bekommt, die, nachdem, man die entsprechende gabelung im baum gefunden hat, dazu benutzt wird, die richtige zelle zu finden.
-
krümelkacker schrieb:
Daher habe ich eine Funktion vorgeschlagen, die auch eine 2D koordinate bekommt,
(Das soll der Schnittpunkt sein)