Sie sind nicht angemeldet.

snoopy

Junior Schreiberling

  • »snoopy« ist männlich
  • »snoopy« ist der Autor dieses Themas

Beiträge: 146

Registrierungsdatum: 29.02.2004

Wohnort: Hannover

Beruf: Informatik

1

19.02.2007, 12:23

GIS2-Fragen

Übung 1, Aufgabe 2: Was wollten die da hören? Meine Antwort wohl nicht ...

Übung 2, Aufgabe 2: Einen balancierten kd-Baum kann man doch nur hinbekommen, wenn man nicht nur an den Punkten teilt, sondern beliebig? Das kam im Skript leider etwas kurz.

Übung 4, Aufgabe 1: Binary Space Partitioning für Punkte.
Dort steht Raumaufteilung "Schnittgeraden mit Orientierung". Was denn für Schnittgeraden? Sollen Punkte Geraden bilden oder was schneiden? In den Übungsfolien gibt es nur Trenngeraden oder feste Ausrichtung.

BSP Trenngeraden: Gibt es dort ein System zwischen Welchen Punkten man Trenngeraden zieht? Die Folien sehen so unsysthematisch aus: A-B, A-C, D-E, ...

a7K

Trainee

  • »a7K« ist männlich

Beiträge: 45

Registrierungsdatum: 14.10.2002

Wohnort: Hannover

2

19.02.2007, 17:12

Ü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.
"Wie Sie in meine Fahrgemeinschaft gekommen sind, werde ich nie erfahren..."

derSmutje

Alter Hase

  • »derSmutje« ist männlich

Beiträge: 295

Registrierungsdatum: 07.12.2004

3

19.02.2007, 20:25

KD-Baum

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?
/join #inf

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »derSmutje« (19.02.2007, 20:27)


Panschk[FP]

Junior Schreiberling

  • »Panschk[FP]« ist männlich

Beiträge: 148

Registrierungsdatum: 21.10.2005

Wohnort: H-town

Beruf: Informatik Master

4

19.02.2007, 23:33

Wie sieht es eigentlich mit Hilfsmitteln in der Klausur aus?

a7K

Trainee

  • »a7K« ist männlich

Beiträge: 45

Registrierungsdatum: 14.10.2002

Wohnort: Hannover

5

20.02.2007, 08:46

Ich nehme als Median immer floor(n/2). In den Übungen hatte er es mehr oder weniger willkürlich gemacht.
"Wie Sie in meine Fahrgemeinschaft gekommen sind, werde ich nie erfahren..."

snoopy

Junior Schreiberling

  • »snoopy« ist männlich
  • »snoopy« ist der Autor dieses Themas

Beiträge: 146

Registrierungsdatum: 29.02.2004

Wohnort: Hannover

Beruf: Informatik

6

20.02.2007, 14:51

Eine Frage zum Skript, steht so auch in der Fassung von sos1981: Ist das Vektorprodukt nicht nur im R³ definiert? Wie kann man denn dann bitte damit im 2D den Abstand Punkt-Gerade berechnen? Wie soll das denn bitte gehen?

||d|| = (|(P-A)x(B-A)|) / ||B-A||

Markus

the one and only Unterstrich!

Beiträge: 2 571

Registrierungsdatum: 09.10.2003

7

20.02.2007, 15:04

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 (:
Charmant sein? Hab ich längst aufgegeben. Glaubt mir doch eh keiner...

Panschk[FP]

Junior Schreiberling

  • »Panschk[FP]« ist männlich

Beiträge: 148

Registrierungsdatum: 21.10.2005

Wohnort: H-town

Beruf: Informatik Master

8

20.02.2007, 17:09

Ja, mit der Determinante kommt das hin :)

Benjamin

Segelnder Alter Hase

  • »Benjamin« ist männlich

Beiträge: 3 827

Registrierungsdatum: 01.10.2002

Wohnort: Region Hannover

Beruf: Alumni

9

20.02.2007, 23:08

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?
Es gibt nur eine bessere Sache als auf dem Wasser zu sein: Noch mehr auf dem Wasser sein.

RedKen

Trainee

  • »RedKen« ist männlich

Beiträge: 105

Registrierungsdatum: 15.11.2004

Wohnort: Hannover Rock-City

10

20.02.2007, 23:35

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).
ich sitz' am Puls der Zeit und schneid' und schneid' und schneid'...

derSmutje

Alter Hase

  • »derSmutje« ist männlich

Beiträge: 295

Registrierungsdatum: 07.12.2004

11

20.02.2007, 23:37

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;-)
/join #inf

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »derSmutje« (20.02.2007, 23:38)


Panschk[FP]

Junior Schreiberling

  • »Panschk[FP]« ist männlich

Beiträge: 148

Registrierungsdatum: 21.10.2005

Wohnort: H-town

Beruf: Informatik Master

12

21.02.2007, 10:41

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 :P
Freestyle mit einem Malprogramm, also etwas krumm-_-


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

snoopy

Junior Schreiberling

  • »snoopy« ist männlich
  • »snoopy« ist der Autor dieses Themas

Beiträge: 146

Registrierungsdatum: 29.02.2004

Wohnort: Hannover

Beruf: Informatik

13

21.02.2007, 17:14

Zitat

Original von a7K
Ü4-A1) Beim BSP für Punkte wählt man als Segmente die Mittelsenkrechte auf der Verbindungsgeraden zwischen den beiden Punkten. (Eingabereihenfolge beachten!)

Richtung/Orientierung der Mittelsenkrechten wählt man willkürlich?

Waren eigentlich alle Übungsfoliensätze wirklich in der Übung dran? Manche passen überhaupt nicht zu den Übungsaufgaben.

Hat er in der letzten Übung was zur Klausur angedeutet?

Sind diese Themen alle Klausurstoff? Puffer/Skelett, Schnitt, Inklusion?