Vorlesung Geoinformation IWS 01/02

Musterlösung für die Probeklausur vom 16.1.2002

3..*

Masche

begrenzt

2Kante

2

2..*

begrenzt

Knoten

Punkt

2

Geometrie

1

1

vl-Kantenr-Kante1

11

1

Lösung der Aufgabe 1:

Die Erweiterung des Diagramms auf „Winged Egde“ besteht in zwei Beziehungen, nr-Kante und vl-Kante, zwischen der Klasse Kante. Jede Kante hat einen Verweis auf ihre nr-Kante (nächste Kante im Umring der rechten Masche) und auf ihre vl-Kante (vorherige Kante im Umring der linken Masche). Jede Kante hat genau eine vl- und genau eine nr-Kante und ist zugleich nur einmal vl- bzw. nr- Kante einer anderen Kante; daher sind die Multiplizitäten an der Beziehung jeweils „1“.

Es ist hier nicht notwendig, neue Klassen einzuführen; der Unterschied zwischen der Knoten-Kanten-Struktur und „Winged Edge“ liegt in der Hinzufügung von Beziehungen zwischen existierenden Objekten.

A

B C

D

Lösung der Aufgabe 2:

Es liegt keine Landkarte vor, da

• der Knoten A ein isolierter Knoten ist,

• die Kante B auf beiden Seiten dieselbe Masche hat. Hier liegt ein „Undershoot“ vor: die Kante L ist zu kurz geraten; ein Maschenumring ist nicht geschlossen (alternative Erklärungen: B ist trennende Kante, ein Knoten inzident zu B ist trennender Knoten, oder ein Knoten inzident zu B hat einen Grad von 1)

• die Kante C eine trennende Kante ist (alternative Erklärung: die Masche, in der C liegt, ist nicht top. Äquivalent zu einer offenen Kreisscheibe),

• die Kante D einen Schnittpunkt mit einer anderen Kante bildet, der kein Knoten ist. Hier liegt ein „Overshoot“ vor: die Kante ist zu lang geraten.

a) b) c) d)

A

A

A

A

B

B

B

B

Lösung der Aufgabe 3:

a) ist topologisch zusammenhängend, da die Kante, die zu der Menge (Rand) gehört, die Teilmengen A und B miteinander verbindet. Jede Zerlegung der Punktmenge in zwei Teilmengen erfüllt die Definition: entweder enthält eine Teilmenge einen Punkt nahe zu der anderen Teilmenge, oder umgekehrt.

b) ist ebenfalls top. zusammenhängend; der Berührungspunkt von A und B gehört zu der Menge, da die Teilmenge B geschlossen ist (dass A offen ist, spielt hier keine Rolle)

c) ist top. Zusammenhängend; der Berührungspunkt von A und B gehört zu der Menge, da die Teilmengen A und B geschlossen sind.

d) ist dagegen nicht top. zusammenhängend: Man kann die Punktmenge disjunkt in A und B zerlegen, so dass weder A einen Punkt nahe zu B enthält, noch B einen Punkt nahe zu A enthält. Der Berührungspunkt von A und B gehört nicht zu der Menge, da beide offen sind. Man kommt von A nicht nach B, da die „Grenze“ nicht zu der Menge gehört: man kommt zwar beliebig nahe an die Grenze heran (sowohl von A als auch von B), aber nicht darüber hinweg.

Lösung der Aufgabe 4:

Es liegt keine Landkarte vor, da

• die Kante ae eine trennende Kante ist (bzw. a ein trennender Knoten). Die „Masche“ A ist nicht äquivalent zu der offenen Kreisscheibe, da sie keinen einfachen Umring hat; somit ist A keine Masche. (Anmerkung: jeder einzelne der vier Erklärungen ist für sich alleine schon richtig.)

• das Rechteck fgih eine „Aussparung“ in der „Masche“ B (grau) ist; B ist nicht topologisch äquivalent zu einer offenen Kreisscheibe und somit keine Masche.

• die Kante dj eine trennende Kante ist. Alternative Erklärung: die Aggregation aller inneren Maschen (A, B, C, D) ist nicht topologisch äquivalent zu einer offenen Kreisscheibe, da sie aus zwei Teilen (A, B,C einerseits, D andererseits) besteht.

Die Tabelle ist auf der nächsten Folie wiedergegeben; in der Tabelle zeigt sich der Fehler „trennende Kante“ dadurch, dass auf beiden Seiten einer Kante dieselbe Masche (A bzw. Außen) liegt; bei Landkarten müssen beide Maschen verschieden sein.

a

b

c

def g

h i

j

k

l

ab bd

dcca

dj

Außen

AB

C Dae

Tabelle (Knoten-Kanten-Struktur) zu Aufgabe 4:

Kante Anfangsknoten Endknoten linke Masche rechte Masche

ab a b Außen A

bd b d Außen B

dc d c Außen B

ca c a Außen A

ae a e A A

bc b c B A

fg f g B C

gi g i B C

ih i h B C

hf h f B C

dj d j Außen Außen

jk j k Außen D

kl k l Außen D

lj l j Außen D

A

E

Q

N

L

K

J

R

I

B

C

P

M

G

O

D

FH

34

5

2

7

41

3

2

49

4

2

5

2 3

4

111

3

9

54

11

9

7

5

75

5

4

7

63

1112

11

11

Lösung der Aufgabe 5:

Der optimale Weg ist A J K L N O Q R E D C B I M H P F G (unten rot bzw. dicker)

und hat die „Länge“ 54.

Eine Vorgehensweise, die (nicht nur) in diesem Beispiel gut funktioniert ist die folgende:

• gehe zunächst außen rum (d.h. von A nach D)

• gehe dann die inneren Knoten entlang, und zwar so:

• bilde den Schwerpunkt der konvexen Hülle (d.h. des Polygons des äußeren Wegs)

• Konstruiere eine Kante (blau bzw. gestrichelt) durch diesen Schwerpunkt und den Ausgangspunkt A

• sortiere die inneren Knoten nach aufsteigender Winkel-differenz zwischen blau und der Kante zwischen dem Schwerpunkt und dem Knoten (grün bzw. gepunktet)

• durchlaufe diese Knoten entsprechend der Sortierung.

A

E

Q

N

L

K

J

R

I

B

C

P

M

G

O

D

FH

34

5

2

7

41

3

2

49

4

2

5

2 3

4

111

3

9

54

11

9

7

5

75

5

4

7

63

1112

11

11

Lösung der Aufgabe 5:

Alternativ ist der Weg ist A J K L N M I H P F G B C D E R Q O (unten rot bzw. dicker) optimal; er hat ebenfalls die „Länge“ 54.