You are not logged in.

snoopy

Junior Schreiberling

  • "snoopy" is male
  • "snoopy" started this thread

Posts: 146

Date of registration: Feb 29th 2004

Location: Hannover

Occupation: Informatik

1

Monday, February 19th 2007, 12:23pm

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" is male

Posts: 45

Date of registration: Oct 14th 2002

Location: Hannover

2

Monday, February 19th 2007, 5:12pm

Ü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" is male

Posts: 295

Date of registration: Dec 7th 2004

3

Monday, February 19th 2007, 8:25pm

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

This post has been edited 1 times, last edit by "derSmutje" (Feb 19th 2007, 8:27pm)


Panschk[FP]

Junior Schreiberling

  • "Panschk[FP]" is male

Posts: 148

Date of registration: Oct 21st 2005

Location: H-town

Occupation: Informatik Master

4

Monday, February 19th 2007, 11:33pm

Wie sieht es eigentlich mit Hilfsmitteln in der Klausur aus?

a7K

Trainee

  • "a7K" is male

Posts: 45

Date of registration: Oct 14th 2002

Location: Hannover

5

Tuesday, February 20th 2007, 8:46am

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" is male
  • "snoopy" started this thread

Posts: 146

Date of registration: Feb 29th 2004

Location: Hannover

Occupation: Informatik

6

Tuesday, February 20th 2007, 2:51pm

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!

Posts: 2,571

Date of registration: Oct 9th 2003

7

Tuesday, February 20th 2007, 3:04pm

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]" is male

Posts: 148

Date of registration: Oct 21st 2005

Location: H-town

Occupation: Informatik Master

8

Tuesday, February 20th 2007, 5:09pm

Ja, mit der Determinante kommt das hin :)

Benjamin

Segelnder Alter Hase

  • "Benjamin" is male

Posts: 3,827

Date of registration: Oct 1st 2002

Location: Region Hannover

Occupation: Alumni

9

Tuesday, February 20th 2007, 11:08pm

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" is male

Posts: 105

Date of registration: Nov 15th 2004

Location: Hannover Rock-City

10

Tuesday, February 20th 2007, 11:35pm

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" is male

Posts: 295

Date of registration: Dec 7th 2004

11

Tuesday, February 20th 2007, 11:37pm

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

This post has been edited 1 times, last edit by "derSmutje" (Feb 20th 2007, 11:38pm)


Panschk[FP]

Junior Schreiberling

  • "Panschk[FP]" is male

Posts: 148

Date of registration: Oct 21st 2005

Location: H-town

Occupation: Informatik Master

12

Wednesday, February 21st 2007, 10:41am

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" is male
  • "snoopy" started this thread

Posts: 146

Date of registration: Feb 29th 2004

Location: Hannover

Occupation: Informatik

13

Wednesday, February 21st 2007, 5:14pm

Quoted

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?