Hallo,
ich stehe gerade vor folgendem Problem: Ich möchte aus einer Text-Datei
eine Reihe von 2D-Polygonen und Kreisbögen laden (Luftraumstruktur) und
diese möglichst effizient so verwalten, dass man sie auf einem LCD
darstellen kann. Man soll herein- und herauszoomen können und den
Mittelpunkt der Darstellung verschieben können. Das ganze ist also eine
Art Vektorkarte.
Da Durchgehen der Textdatei und das Darstellen auf dem Bildschirm ist
kein Problem. Ich kann die Textdatei interpretieren, die Eckpunkte der
Polygone auf meine Darstellung skalieren und die Linien zeichnen.
Mein Problem ist es, wie halte ich die Daten sinnvoll im Speicher? Und
zwar am besten irgendwie indiziert, so dass ich beim Verschieben des im
LCD sichtbaren Ausschnittes der Karte oder beim Zoomen möglichst schnell
feststellen kann, welche Elemente sichtbar sind?
Die Polygone haben alle eine unterschiedliche Anzahl von Punkten, so
dass man schlecht ein statisches Array programmieren kann. Man bräuchte
eine dynamische Liste für jedes Polygon. Und dann wieder eine dynamische
Liste der dynamischen Listen für den gesamten Luftraum. Nur, dann
funktioniert ein schnelles Durchgehen der Daten und Prüfen auf
Sichtbarkeit nicht.
Ich bin auf einem Embedded Linux auf ARM und habe jede Menge Speicher.
Ich möchte in C programmieren, C++ geht leider aus verschiedenen Gründen
nicht.
Wäre dankbar für ein paar Anstöße und Ideen.
Hier ist mal ein Beispiel der Daten:
Quadtree
http://de.wikipedia.org/wiki/Quadtree
In jedem Blatt des Tree ist eine Liste mit Pointern zu den
Originalpolygonen gespeichert. Die wiederrum sind in eine Datenstruktur
gespeichert, die du skizziert hast.
Ich habe mich damit jetzt mal näher auseinandergesetzt.
Ich sehe aber noch nicht, wie ein Quadtree meine Probleme löst. Meine
Polygone überlappen sich, manche sind sehr klein und wiederum andere
sehr groß. Die großen Polygone beinhalten oft eine Vielzahl von den
kleinen Polygonen.
Die Frage ist, in welchem Blatt würde ein sehr großes Polygon landen und
wie stelle ich bei hohen Zoomfaktoren sicher, dass auch Linien eines
Polygons dargestellt werden, deren Eckpunkte weit außerhalb des
sichtbaren Bereichs liegen?
Polygon-Dreher schrieb:> Ich sehe aber noch nicht, wie ein Quadtree meine Probleme löst. Meine> Polygone überlappen sich, manche sind sehr klein und wiederum andere> sehr groß. Die großen Polygone beinhalten oft eine Vielzahl von den> kleinen Polygonen.
Und? Macht ja nichts.
Ausserdem sagt kein Mensch, dass ein Polygon nur in einem Blatt im
Quadtree sein darf.
> Die Frage ist, in welchem Blatt würde ein sehr großes Polygon landen und> wie stelle ich bei hohen Zoomfaktoren sicher, dass auch Linien eines> Polygons dargestellt werden, deren Eckpunkte weit außerhalb des> sichtbaren Bereichs liegen?
Du machst da einen Fehler.
Der Quadtree liefert dir (hier) nicht die Information, welche Polygone
sichtbar sind sondern die Umkehrung: Wenn ein Blatt des Quadtrees nicht
auf dem LCD sichtbar ist, dann brauchen auch alle Polygone dieses
Quadtrees nicht berücksichtigt zu werden. Das bedeutet nicht
zwangsläufig, dass ein und dasselbe Polygon nicht über ein anderes Blatt
vom Quadtree dann doch sichtbar sein kann. Denn: Warum soll ein Polygon
nicht in mehreren Blättern vorhanden sein?
Der Quadtree ist (hier) also ein Mechanismus, mit dem du viele
Polygongruppen von vorne herein aus dem Renderprozess ausschliessen
kannst, weil sie nicht sichtbar sein können, weil das zugehörige Blatt
des Trees schon nicht sichtbar ist.
Du kannst natürlich auch entscheiden, dass du alle Polygone, die nicht
zur Gänze in einem Blatt des Quadtree liegen, getrennt vom Quadtree
abgelegt werden und nicht über diesen Mechanmisus ausgeschlossen werden.
Wenn du die Auflösung des Quadtrees nicht allzu hoch machst, werden das
nicht allzuviele sein. Man kann die Polygone aber auch über den Baum
verteilen so dass nicht notwendigerweise alle Polygone in den Blättern
liegen, sondern auf den Ästen, die zu den Blättern führen. Varianten
gibt es viele. Denk dir was aus.
Springender Punkt ist, dass du einfach und schnell mit einem Schlag
ganze Polygongruppen als nicht sichtbar ausschliessen kannst. So kriegst
du auch bei großen Datenmengen Speed. Nicht zu detailverliebt sein:
Vortests sind Quick & Dirty Tests. Wenn mal ein paar Polygone durch den
Vortest durchkommen, obwohl sie nicht sichtbar sind, dann ist das nicht
so schlimm. Wenn du, um das abzustellen, den Vortest signifikant
komplizierter machen musst, dann lohnt sich das nicht. Es macht keinen
Sinn den Vortest für 1 Mio Polygone langsamer zu machen nur um zu
verhindern, dass 10 Polygone in die Renderingpipiline geschleust werden,
die eigentlich nicht sichtbar sind.
Hallo,
die Frage, ob ein Polygon im Fenster sichtbar ist, ist schon vielfach
behandelt worden und nicht so ohne weiteres zu vereinfachen. Ich würde
aber mal probieren, die Polygone von vornherein auszuschliessen, die
ganz oberhalb, ganz rechts usw. vom Fenster liegen. Dazu müsste es
helfen, die Polygondatenbank 4fach zu indizieren - nach Xmin, Xmax, Ymin
und Ymax. Das muss man nur einmal machen und wenn z.B. Ymin > obere
Fensterkante, dann ist das Polygon ganz oberhalb des Fensters und also
nicht sichtbar. Die Frage ist, ob das die Menge der genauer zu prüfenden
Polygone im konkreten Fall merklich reduziert, das muss man wohl
ausprobieren.
Gruss Reinhard
Reinhard Kern schrieb:> aber mal probieren, die Polygone von vornherein auszuschliessen, die> ganz oberhalb, ganz rechts usw. vom Fenster liegen. Dazu müsste es> helfen, die Polygondatenbank 4fach zu indizieren - nach Xmin, Xmax, Ymin> und Ymax. Das muss man nur einmal machen
Das Problem ist, dass du nach jedem Zoom, jedem Scrollen die Indizierung
neu machen musst. Kann man machen, wenn man für jedes Polygon eine
Bounding Box im Vorfeld bestimmt hat und bei der Ausgabe erst mal
überprüft ob die Bounding Box überhaupt in der Ausgabefläche liegt.
(Hmm. So gesehen kann man einen Quadtree auch als 'Bounding Box' Test
auffassen. Der Quadtree stellt ein paar Bounding Boxen bereit, in welche
die Polygone einsortiert werden. ANstalle dass man jedes Polygon anhand
seiner persönlichen Bounding Box ausschliesst, geht man von der anderen
Seite ran. Da ist eine 'Bounding Box' (die auch zu gross sein kann) und
wenn die nicht in der Ausgabefläche sichtbar ist, dann können auch alle
Polygone in dieser Bounding Box nicht sichtbar sein :-)
Ansonsten fallen mir jetzt noch Triage Tables ein. Die sind aber im 2D
nicht so gut zu benutzen. Müsste ich jetzt noch mal beim Blinn
nachlesen, wie er das im 2D Fall gemacht hat.
Was ich noch sagen wollte:
Lass dich nicht vom 'Baum' im Ausdruck Quadtree abschrecken.
Was du im Grunde machst ist:
Du 'kachelst' deinen Datenbestand.
Ist deine Welt zb das hier
1
+--------------------------------------+
2
| |
3
| |
4
| |
5
| |
6
| |
7
| |
8
| |
9
| |
10
| |
11
+--------------------------------------+
dann kachelst du mit einem QUadtree der Höhe 1 diese Welt in 4
Teilbereiche
1
+-------------------+------------------+
2
| | |
3
| | |
4
| 1 | 2 |
5
| | |
6
| | |
7
+-------------------+------------------+
8
| | |
9
| | |
10
| 3 | 4 |
11
| | |
12
| | |
13
+-------------------+------------------+
sodass du aus jedem dieser Teilbereiche leicht erfahren kannst, welche
Polygone da drinnen sichtbar sind.
Hat dein Benutzer daher gezoomt, weil er nur einen Teil der Daten sehen
will ....
1
+-------------------+------------------+
2
| | ********** |
3
| | * * |
4
| 1 | * 2 * |
5
| | ********** |
6
| | |
7
+-------------------+------------------+
8
| | |
9
| | |
10
| 3 | 4 |
11
| | |
12
| | |
13
+-------------------+------------------+
... dann ist klar, dass nur Polygone aus dem Teilbereich 2 relevant
sind. Alle anderen Polygone können nicht sichtbar sein.
Und mit jeder Höhenstufe mehr im Quadtree kriegst du eine feinere
Aufteilung in mehr Teilbereiche. Machst du nur 1 Stufe mehr, dann hast
du schon eine Unterteilung in 16 Teile
1
+--------+----------+---------+--------+
2
| 1 | 2 | 5 | 6 |
3
| | | | |
4
+--------+----------+---------+--------+
5
| 3 | 4 | 7 | 8 |
6
| | | | |
7
+--------+----------+---------+--------+
8
| 9 | 10 | 13 | 14 |
9
| | | | |
10
+--------+----------+---------+--------+
11
| 11 | 12 | 15 | 16 |
12
| | | | |
13
+--------+----------+---------+--------+
Natürlich könntest du auch sagen: Ich mach einfach ein Array von 16
derartigen Polygonlisten. Würde gehen.
Die Organisationsform Quadtree hat den Vorteil, dass man sie leicht
selbst-adaptierbar machen kann: Wenn eine Kachel zu groß ist, dann wird
sie in 4 kleinere Kacheln unterteilt.
Zu groß kann dabei bedeuten:
* In den Welteinheiten zu groß (also zu breit, zu hoch)
* Zu viele Polygone (bei dir wahrscheinlich nicht sinnvoll)
Es gibt eine Menge Open-Source-Programme, die OpenAir-Dateien einlesen
und die Daten als moving map darstellen. Schau da mal rein.
Der QuadTree-Ansatz ist m.E. vielversprechend, wenn du ihn richtig
umsetzt. Ich würde die Lufträume als Listen von Polygonen und diese
wiederum als Listen von Punkten speichern. In jeden Knoten des
QuadTrees kommt eine Liste mit zugehörigen Lufträumen. Der Schlüssel
dürfte darin liegen, dass größere Polygone weiter oben in Richtung
Wurzel des Baumes gespeichert werden, so dass sie mit ihrer bounding box
komplett in dem Fenster liegen, das dem jeweiligen Knoten entspricht.
Die kleineren Polygone sind dann in den Knoten weiter unten, wo die
Fenster entsprechend kleiner werden. Lege eine sinnvolle maximale
Zoom-Stufe fest, die Tiefe des Baumes wähle so, dass die dort enthaltene
Fläche dem in der maximalen Zoomstufe sichtbaren Fenster entspricht.
Damit ist sichergestellt, dass immer alle sichtbaren Linien gezeichnet
werden, wenn du für jede Zoomstufe und Position von der Wurzel des
Baumes ausgehend nach unten zu dem Zielknoten mit dem passenden Fenster
durchgehst.
Du hast allerdings nicht nur gerade Linien, sondern auch Kreisbögen in
deinen Daten. Das macht es etwas komplizierter, ändert aber nichts an
der Datenstruktur. Du musst halt eine Fallunterscheidung machen und für
Fragen wie "was ist die bounding box eines Luftraumes?" verschiedene
Algorithmen implementieren.
Karl Heinz Buchegger schrieb:> Das Problem ist, dass du nach jedem Zoom, jedem Scrollen die Indizierung> neu machen musst.
Wieso? Die jeweiligen Werte liegen doch beim Bewegen des Fensters fest
(Weltkoordinaten), man muss nur was ändern, wenn sich ein Polygon ändert
oder neu dazukommt. Und wie man sowas in einen vorhandenen Index einbaut
ist aus der Datenbanktheorie längst bekannt. Beim Zoomen und Scrollen
bewegt sich das Fenster in der Welt, da ändert sich an den Polygonen
garnichts.
Naja, was solls, ich muss es ja nicht lösen, also warum streiten.
Vergiss den Vorschlag einfach.
Gruss Reinhard
@Reinhard
vieleicht hab ich auch einfach nur nicht verstanden, was genau du mit
> Dazu müsste es helfen, die Polygondatenbank 4fach zu indizieren -> nach Xmin, Xmax, Ymin und Ymax. Das muss man nur einmal machen und> wenn z.B. Ymin > obere Fensterkante
meinst.
Jep, ich hab dich ganz sicher falsch verstanden. Mich hat das
"indizierien" da drinnen verwirrt.
Was du vorschlägst ist ein einfacher Boxtest. Der ist aber sowieso erst
mal Grundvoraussetzung für jegliche 'Optimierung'.
Thread beobachten
Seitenaufteilung abschalten