Fachrat Informatik - Forum

Ü1-A2) Erfasse alle Punkte in der Reihenfolge, wie sie durch eine raumfüllende Kurve durchlaufen werden (z.B. Hilbert- oder Peano-Kurven). Alternativ auch mit einem mäanderförmigen Durchlauf.

Ü2-A2) Sortiere die Punkte nach der aktuellen Unterteilung, wähle immer die Mitte aus und führe das gleiche mit der "rechten und linken" Punktemenge erneut durch. D.h. bei x,y,x,y,... zunächst alle Punkte nach x-Koordinaten sortieren, die Mitte als Knoten in den Baum aufnehmen. Danach die "linke und rechte" Punktmenge nach y-Koordinaten sortieren und wieder die Mitte als Knoten aufnehmen. z.B.: (1,9), (5,6), (5,3), (2,5), (7,9), (3,3)

1.) nach x-sortiert:
(1,2), (2,5), (3,3), (5,{3,6}), (7,9) -> (3,3) als Wurzel
2.) nach y-sortiert:
(2,5), (1,9) -> (2,5) ist linkes Kind von der Wurzel
(5,3), (5,6), (7,9) -> (5,6) ist rechtes Kind von der Wurzel
3.) ...

Ü4-A1) Beim BSP für Punkte wählt man als Segmente die Mittelsenkrechte auf der Verbindungsgeraden zwischen den beiden Punkten. (Eingabereihenfolge beachten!)
D.h. wenn (1,6) eingefügt wird, passiert noch nichts. Wenn dann z.B. (1,0) eingefügt wird, sind (1,6) und (1,0) zu verbinden und die Mittelsenkrechte auf dieser Geraden bildet das Segment. Fügt man dann (2,7) ein, so liegt es im Bereich mit (1,6), so dass man (1,6) mit (2,7) verbindet und wieder die Mittelsenkrechte als neues Segment aufnimmt.

Es gibt "ein System" nachdem man Trenngeraden zieht: Aufgrund der Eingabereihenfolge liegt in einem Bereich (links oder rechts von einem Segment) immer nur ein Punkt, so dass eindeutig festgelegt ist, welche zu verbinden sind.

Beim BSP-Baum für Punkte stehen die eigentlichen Punkte auch erst in den Blättern. Die Knoten enthalten dann immer Mittelsenkrechten als Segmente.

zum KD-Baum (Ü2-A2):
So wie der KD-Baum bei Wikipedia aussieht, scheinen die Knoten nur in den Blättern gespeichert zu werden und nicht in den (inneren) Knoten.

In der Übung wurde auch von dem jeweiligen "Median" gesprochen, der jeweils in den Knoten gespeichert wird (berechnet aus den sortierten Listen, wie es a7K erklärt hat). Ich bin mir aber nicht sicher, wie dieser Median berechnet wird. Laut Wikipedia ist er bei ungerade Elementanzahl einfach das Element an mittlerer Position und bei gerader Elementanzahl die Hälfte der Summe der beiden mittleren Zahlen.
Bsp: x-Liste: ( 1,2,3,4,5,6,7,8 ) => Median=4,5=Eintrag in Knoten. Verfahren rekursiv auf linken und rechten Teil der Liste anwenden...

Ist das auch die Definition, die in GIS2 verwendet wird?

Wie sieht es eigentlich mit Hilfsmitteln in der Klausur aus?

Ich nehme als Median immer floor(n/2). In den Übungen hatte er es mehr oder weniger willkürlich gemacht.

Irgendwo (IMHO Mathe Vorlesung) hieß es mal, dass das Vektorprodukt nur im R³ definiert sei. Aber dennoch trifft man es hier und dort auch mal in der zweiten Dimension, wenn ich nicht irre, ist damit dann die Determinante gemeint. Probier mal aus, ob das passt, und berichte, ob's stimmt (:

Ja, mit der Determinante kommt das hin

Dann will ich auch mal eine Frage in den Raum werfen. Wenn man nen Point-Quadtree hat, bei dem man einen neuen Punkt an verschiedenen Stellen im Baum einfügen kann, dann nimmt man die erste Möglichkeit? Also ich bilde mir zumindest ein, dass man zu solch einer Situation kommen kann: Man füge nacheinander ein: (1,3), (3,7), (5,6), (9,3), (8,2). Meiner Meinung nach passt (8,2) dann sowohl in den dritten Sektor von (1,3), als auch in den vierten Sektor von (9,3). Denkfehler?

so wie ich das verstehe gehört (9, 3) in den dritten Quadranten von (5, 6) und dann kann (8, 2) nur in den dritten Quadranten von (1, 3).

Das hängt ganz davon ab, welchem Sektor du den Punkt (9,3) zuordnest. Also musst du eine Festlegung treffen, welchem Quadranten die Punkte zugeordnet werden, die auf einer Grenzlinie liegen.
Eine mögliche Zuordnung wird z.B. auf dem 3. Übungblatt gemacht.

Nach dieser Zuordnung würde der Punkt (9,3) in den zweiten Quadranten von (1,3) gehören und damit dem dritten Quadranten von (5,6) zugeordnet werden. Fügt man nun (8,2) ein, so stellt man fest, dass (1,3) noch keinen Punkt in seinem dritten Quadranten enthält und kann (8,2) hier einfügen.

Edit: RedKen war schneller;-)

Die Festlegung, die ich kenne, wenn ein Punkt auf einer Linie ist, ist eigentlich immer "nach oben" und "nacht rechts" zuordnen.

Habe sinnloserweise ein Bild gemacht
Freestyle mit einem Malprogramm, also etwas krumm-_-


Habe Anders mal gemailt, als Hilfsmittel für die Klausur sind nur Schreib-und Zeichenwerkzeuge erlaubt.