Vorlesung Algorithmische Kartografie Randbeschriftung

Transcrição

Vorlesung Algorithmische Kartografie
Randbeschriftung
LEHRSTUHL FÜR ALGORITHMIK I · INSTITUT FÜR THEORETISCHE INFORMATIK · FAKULTÄT FÜR INFORMATIK
Benjamin Niedermann/Martin Nöllenburg
16.06.2015
1
Punktbeschriftung in Landkarten
Randbeschriftungen
Ibis Hotel
Main Station
Kulturspeicher
Hauptbahnhof
Hauptbahnhof West
Hotel Poppular
Juliuspromenade
Escalera
Ulmer Hof
Hotel Urlaub
Barbarossaplatz
Nachteile von internen Beschriftungen
funktioniert nur für dünne“ Punktmengen gut
”
Label verdecken unterliegende Topographie
manche Label müssen ausgeblendet werden
visuelles cluttering
2-1
Randbeschriftungen
Ibis Hotel
Kulturspeicher
Escalera
Ulmer Hof
Hotel Urlaub
Main Station
Hauptbahnhof
Hauptbahnhof West
Hotel Poppular
Juliuspromenade
Barbarossaplatz
Vorteile von Randbeschriftungen
dichte Punktmengen lassen sich beschriften
weniger Überdeckungen der Karte
schnelleres Finden Name → Ort
besser geeignet für Label mit viel Text
2-2
Randbeschriftungen
3-1
Randbeschriftungen
Schleswig-Holstein
Mecklenburg-Vorpommern
Hamburg
Bremen
Niedersachsen
Berlin
Brandenburg
Sachsen-Anhalt
Nordrhein-Westfalen
Sachsen
Thüringen
Hessen
Rheinland-Pfalz
Saarland
Bayern
Baden-Württemberg
3-2
Randbeschriftungen
Schleswig-Holstein
Hamburg
Bremen
Niedersachsen
Berlin
Brandenburg
Sachsen-Anhalt
Sachsen
Nordrhein-Westfalen
Thüringen
Hessen
Saarland
Rheinland-Pfalz
Baden-Württemberg
Bayern
3-3
Randbeschriftungen
Schleswig-Holstein
Lederhaut
Hamburg
Bremen
Niedersachsen
Berlin
Brandenburg
Sachsen-Anhalt
Sachsen
Nordrhein-Westfalen
Thüringen
Hessen
Saarland
Sehnerv
Rheinland-Pfalz
Baden-WürttembergNetzhaut
Bayern
3-4
Aderhaut
Schlemm-Kanal
Irisfortsätze
Hornhaut
Zonulafasern
Iris
Pupille
vordereAugenkammer
Augenkammerhintere
Ziliarkörper
Linse
Glaskörper
http://commons.wikimedia.org/wiki/File:Eye scheme.svg
Arten von Randbeschriftungen
4-1
Einseitiger Fall
Zweiseitiger Fall
Dreiseitiger Fall
Vierseitiger Fall
Arten von Randbeschriftungen
4-2
Einseitiger Fall
Zweiseitiger Fall
Dreiseitiger Fall
Vierseitiger Fall
Problemstellung
Gegeben:
Punkte P = {p1 , . . . , pn } in einem Rechteck R.
Uniforme, achsenparallele, disjunkte Rechtecke L = {`1 , . . . , `n } mit
rechter Seite auf linker Seite von R. Rechtecke aus L heißen Label.
R
Label `1
Label `2
p2
p5
p4
Label `3
Label `4
Label `5
5-1
p1
p3
Problemstellung
Gegeben:
Annahme:
Jedes Label ist groß genug, sodass die Beschreibung eines jeden
Punkts hinein passt.
Es sind genauso viele Label wie Punkte vorhanden.
R
Label `1
Label `2
p2
p5
p4
Label `3
Label `4
Label `5
5-2
p1
p3
Problemstellung
Gegeben:
Definition: Eine Menge L = {λ1 , . . . , λn } an Kurven in R heißt
Zuordnung von L und P , wenn
jede Kurve einen Punkt pi ∈ P mit einem Label `j ∈ L verbindet und
jeder Punkt und jedes Label genau von einer Kurve angebunden wird.
R
Label `1
Label `2
p2
p5
p4
Label `3
Label `4
Label `5
5-3
p1
p3
Problemstellung
Gegeben:
Gesucht: Kreuzungsfreie Zuordnung L von L und P , d.h. die Kurven
in L schneiden sich nicht gegenseitig.
R
Label `1
Label `2
p2
p5
p4
Label `3
Label `4
Label `5
5-4
p1
p3
Problemstellung
Gegeben:
Label `1
Label `2
p2
p5
p4
R Begriffe:
Kurve λi heißt Leader.
Verbindungspunkt von
Leader und Label heißt Port.
Label `3
Label `4
Label `5
5-5
p1
p3
Problemstellung
Gegeben:
Label `1
Label `2
p2
p5
p4
Label `3
Label `4
Label `5
5-6
p1
p3
R Begriffe:
Zwei Varianten:
1. Ports fest vorgegeben.
2. Port auf rechter Seite von
Label frei wählbar.
Problemstellung
Gegeben:
Label `1
Label `2
p2
p5
p4
Label `3
Label `4
Label `5
5-7
p1
p3
R Begriffe:
Zwei Varianten:
Problemstellung
Gegeben:
Annahme: Allgemeine Lage der Punkte in P und der Label in L.
Keine
zweiauf
Punkte
P liegen
aufRechtecke
einer gemeinsamen
rechter
Seite
linker in
Seite
von R.
aus L heißen Label.
vertikalen oder horizontalen Geraden.
Kein Punkt in P liegt auf einer horizontalen Geraden, welche
die obere oder untere Seite eines Labels in L verlängert.
Label `1
Label `2
p2
p5
p4
Label `3
Label `4
Label `5
5-8
p1
p3
R Begriffe:
Zwei Varianten:
Typen von Leadern
Üblich: Leader werden aus Sequenz von Strecken zusammengesetzt.
parallel
Typische Beispiele:
orthogonal
orthogonal
orthogonal
po-Leader
6-1
α
orthogonal
go
na
l
opo-Leader
di
a
parallel
s-Leader
do-Leader
Typen von Leadern
Üblich: Leader werden aus Sequenz von Strecken zusammengesetzt.
parallel
Typische Beispiele:
orthogonal
orthogonal
orthogonal
po-Leader
6-2
α
orthogonal
go
na
l
opo-Leader
di
a
parallel
s-Leader
do-Leader
Zielfunktion
Bewertungsfunktion:
bad : L × P → R
Bewertet Zuordnung von Labeln L und Punkten P .
Optimierungsproblem:
Finde für gegebene Instanz (R, P, L) eine kreuzungsfreie
Zuordnung L, sodass
X
bad(`(λ), p(λ))
λ∈L
unter allen kreuzeungsfreien Zuordnungen minimiert wird.
Notation:
`(λ): Label aus L, das von Leader λ angebunden wird.
p(λ): Punkt aus p, der von Leader λ angebunden wird.
7-1
Zielfunktion
Bewertungsfunktion:
bad : L × P → R
Bewertet Zuordnung von Labeln L und Punkten P .
Optimierungsproblem:
Finde für gegebene Instanz (R, P, L) eine kreuzungsfreie
Zuordnung L, sodass
X
bad(`(λ), p(λ))
λ∈L
unter allen kreuzeungsfreien Zuordnungen minimiert wird.
Notation:
`(λ): Label aus L, das von Leader λ angebunden wird.
p(λ): Punkt aus p, der von Leader λ angebunden wird.
Beispiele für Bewertungsfunktionen?
7-2
Beispiele für Bewertungsfunktionen
Längenminimierung:
Knickminimierung:
Interferenzminimierung mit Karte
8-1
Knickminimierung:
Interferenzminimierung mit Karte
8-2
Begriffe:
Länge einer Zuordnung L: Die Summe der Leader-Längen.
λ(p, `) bezeichnet po-Leader der von p nach ` führt.
Arm
p
8-3
Hand
`
Begriffe:
Länge einer Zuordnung L: Die Summe der Leader-Längen.
λ(p, `) bezeichnet po-Leader der von p nach ` führt.
p
Hand
`
Arm
p
`
aufsteigender Leader
`
8-4
`
p
direkter Leader
absteigender Leader
p
Neuverdrahtung
Satz 1: Für jede Zuordnung L∗ mit po-Leadern und minimaler Länge
gibt es eine kreuzungsfreie Zuordnung L mit po-Leadern selber
Länge. L kann mithilfe von L∗ in O(n2 ) Zeit konstruiert
werden. (Bekos et al. ’07 und Benkert et al. ’09)
9-1
Neuverdrahtung
Beweis:
A) Absteigende und aufsteigende Leader in L∗ schneiden sich nicht.
9-2
Neuverdrahtung
Beweis:
Annahme es gäbe solche Leader:
p0
`
`0
p
9-3
Neuverdrahtung
Beweis:
Annahme es gäbe solche Leader:
p0
p0
`
Neuverdrahtung
`
`0
`0
p
p
Kürzere Gesamtlänge der Leader nach Neuverdrahtung
Minimalität von L∗
9-4
Neuverdrahtung
Beweis:
B) Kein direkter Leader in L∗ kann sowohl einen absteigenden als auch
einen aufsteigenden Leader schneiden.
9-5
Neuverdrahtung
Beweis:
Annahme es gäbe einen solchen Leader:
`0
p00
`
`00
9-6
p0
p
Einziger Fall, denn wegen A) können sich
λ(p0 , `0 ) und λ(p00 , `00 ) nicht schneiden.
Neuverdrahtung
Beweis:
Annahme es gäbe einen solchen Leader:
`0
`0
p00
`
p0
p
Neuverdrahtung
p00
`
`00
`00
Kürzere Gesamtlänge der Leader nach Neuverdrahtung
p0
p
Minimalität von L∗
9-7
Neuverdrahtung
Beweis:
Absteigende Kreuzung : Beteiligung eines absteigenden Leader.
Aufsteigende Kreuzung : Beteiligung eines aufsteigenden Leader.
Menge absteigender Kreuzungen und Menge aufsteigender Kreuzungen
sind somit disjunkt.
9-8
Neuverdrahtung
Beweis:
Idee:
Entferne alle aufsteigenden Kreuzungen L∗ , sodass
die Gesamtlänge der Leader unverändert bleibt und
keine absteigenden Kreuzungen entstehen.
Selbes Vorgehen für absteigende Kreuzungen durch Spiegeln der Instanz.
Kreuzungsfreie Zuordnung L mit gleicher Länge wie L∗ .
9-9
Neuverdrahtung
Fortsetzung Beweis:
Algorithmus zur Entferung aller aufsteigenden Kreuzungen:
Sortiere Label von unten nach oben: `1 , . . . , `n
für i = 1 . . . n tue
Sei λ(p, ì ) Leader in L∗ .
wenn λ(p, ì ) aufsteigender Leader ist dann
Bestimme leader λ(q, `j ) mit linkester Kreuzung mit λ(p, ì ).
Neuverdrahtung: λ(q, ì ) und λ(p, `j ).
`j
ì
`j
ì
q
q
p
10
p
Neuverdrahtung
Fortsetzung Beweis:
Algorithmus zur Entferung aller aufsteigenden Kreuzungen:
Sortiere Label von unten nach oben: `1 , . . . , `n
für i = 1 . . . n tue
Sei λ(p, ì ) Leader in L∗ .
wenn λ(p, ì ) aufsteigender Leader ist dann
Bestimme leader λ(q, `j ) mit linkester Kreuzung mit λ(p, ì ).
Neuverdrahtung: λ(q, ì ) und λ(p, `j ).
Zeige für Schritt i:
1. Gesamtlänge der Leader bleibt erhalten.
2. Aufsteigende Kreuzungen entstehen nur oberhalb von Arm von λ(p, ì ).
3. Es entstehen keine absteigenden Kreuzungen.
4. Laufzeit beträgt O(n) Zeit.
Beweis durch Induktion über i: siehe Tafel.
10
Neuverdrahtung
Satz kann auch auf do-Leader angepasst werden.
11
Sweep-Line-Verfahren
Jetzt: Verfahren für Minimierung der Leader-Längen in O(n log n) Zeit.
Vorgehen in zwei Phasen:
1. Teile Instanz in unabhängige Teilinstanzen auf.
2. Löse Teilinstanzen mithilfe eines Sweep-Line-Verfahrens.
12
Jetzt: Verfahren für Minimierung der Leader-Längen in O(n log n) Zeit.
Vorgehen in zwei Phasen:
1. Teile Instanz in unabhängige Teilinstanzen auf.
2. Löse Teilinstanzen mithilfe eines Sweep-Line-Verfahrens.
Unterteile hierzu Instanz in Streifen
induziert durch Punkte in P und
horizontale Seiten der Label.
12
1. Phase: Teile Instanz in unabhängige Teilinstanzen auf.
Traversiere Streifen von unten nach oben und bestimme folgende
Anzahlen für jeden Streifen σ:
paσ =#Punkte oberhalb von σ inkl.
Punkte auf oberer Kante von σ.
àσ =#Label oberhalb von σ inkl.
Label die σ schneiden.
pbσ =#Punkte unterhalb von σ inkl.
Punkte auf unterer Kante von σ.
`bσ =#Label unterhalb von σ inkl.
13
Ein Streifen σ heißt:
absteigend, falls paσ > àσ
aufsteigend, falls pbσ > `bσ
neutral, in allen anderen Fällen.
13
13
13
13
13
13
13
13
13
2. Phase: Löse Teilinstanzen mithilfe eines Sweep-Line-Verfahrens.
14
}
} absteigende Instanz: inklusive der Grenzen
}
}
}
neutrale Instanz: exklusive der Grenzen
}
aufsteigende Instanz: inklusive der Grenzen
}
14
Neutrale Instanz: Verbinde Punkte und Label mit horizontaler Strecke.
14
Aufsteigende Instanz: Sweep-Line-Verfahren von unten nach oben.
Sweep-Line stoppt bei unterer Kante der
Label und bei Punkten:
Punkt-Event p:
Füge p zu einer nach x-Koordinanten
sortierten Warteliste W hinzu.
Label-Event `:
Entferne Punkt p aus W , der am
weitesten links liegt. Verbinde p mit `
mittels kürzesten Leader.
14
Punkt-Event p:
Label-Event `:
14
Punkt-Event p:
Label-Event `:
14
Punkt-Event p:
Label-Event `:
14
Punkt-Event p:
Label-Event `:
14
Punkt-Event p:
Label-Event `:
14
Punkt-Event p:
Label-Event `:
14
Punkt-Event p:
Label-Event `:
14
Punkt-Event p:
Label-Event `:
14
Punkt-Event p:
Label-Event `:
Analoges Vorgehen für absteigende
Instanz.
14
15
Lemma 1: Für jede kreuzungsfreie Zuordnung mit minimaler Länge gilt,
dass kein Leader einen neutralen Streifen kreuzt (Übung).
16
Beweis: Sei paσ = àσ . (Analog pbσ = `bσ )
Angenommen es gibt Leader λ, der neutralen Steifen σ kreuzt.
1. Fall: λ ist mit Label ` verbunden, das σ kreuzt.
2. Fall: λ verbindet Punkt p oberhalb von σ mit Label ` unterhalb von σ
3. Fall: λ verbindet Punkt p unterhalb von σ mit Label ` oberhalb von σ
16
`
kürze Leader
um mind. Höhe von σ
`
16
`
kürze Leader
um mind. Höhe von σ
`
p
p Wegen paσ = àσ :
0
∃
Punkt
p
unterhalb von σ, der mit
0
0
`
`
0
Label
`
verbunden, sodass
0
0
p
p
0
`
schneidet σ, oder
`
`
`0 liegt oberhalb von σ.
Kürzere Leader
Vertausche Leader
16
Lemma 2: Für eine Instanz (P, L, R) kann eine kreuzungsfreie
Zuordnung minimaler Länge mithilfe von po-Leadern in
O(n log n) Zeit und O(n) Speicher berechnet werden.
16
Beweis:
1. Zwischen absteigenden Streifen σ ↓ und aufsteigenden Streifen σ ↑
befindet sich immer ein neutraler Streifen.
16
Beweis:
16
paσ − àσ ≥ 1 und pbσ < `bσ
pbσ − `bσ ≥ 1 und paσ < àσ
Beweis:
Warum?
16
Beweis:
paσ↓ − àσ↓ ≥ 1
paσ↑ − àσ↑ < 0
16
Beweis:
paσ↓ − àσ↓ ≥ 1
paσ↑ − àσ↑ < 0
16
|(paσ↓ − àσ↓ ) − (paσ↑ − àσ↑ )| ≥ 2
Beweis:
paσ↓ − àσ↓ ≥ 1
paσ↑ − àσ↑ < 0
|(paσ↓ − àσ↓ ) − (paσ↑ − àσ↑ )| ≥ 2
Da Punkte und Label in allgemeiner Lage gilt aber für zwei benachbarte
Streifen σ und σ 0 :
|(paσ − àσ ) − (paσ0 − àσ0 )| ≤ 1
16
Beweis:
paσ↓ − àσ↓ ≥ 1
paσ↑ − àσ↑ < 0
|(paσ↓ − àσ↓ ) − (paσ↑ − àσ↑ )| ≥ 2
Da Punkte und Label in allgemeiner Lage gilt aber für zwei benachbarte
Streifen σ und σ 0 :
|(paσ − àσ ) − (paσ0 − àσ0 )| ≤ 1
σ ↓ und σ ↑ sind nicht benachbart.
16
Beweis:
16
Beweis:
Wegen Lemma 1: In jeder optimalen Lösung werden die Punkte
einer aufsteigenden/absteigenden Instanz S von Leadern
angebunden, die vollständig in S liegen.
16
Beweis:
2. Sei σ unterster Streifen einer aufsteigenden Instanz S. In jeder optimalen
Lösung werden ausschließlich Label oberhalb von σ zur Beschriftung der
Punkte in S verwendet (siehe Tafel). Analog: Absteigende Instanz.
16
Beweis:
2. Sei σ unterster Streifen einer aufsteigenden Instanz S. In jeder optimalen
Lösung werden ausschließlich Label oberhalb von σ zur Beschriftung der
Punkte in S verwendet (siehe Tafel). Analog: Absteigende Instanz.
3. Der Algorithmus berechnet eine solche Zuordnung und diese ist optimal
und kreuzungsfrei (siehe Tafel).
16
16
Satz 2: Die Berechnung einer kreuzungsfreien Zuordnung minimaler
Länge einer Instanz (P, L, R) mit po-Leadern benötigt Laufzeit
O(n log n) Zeit und O(n) Speicher.
16

Vorlesung Algorithmische Kartografie Randbeschriftung

Transcrição

Documentos relacionados

Die Bayern 2-Favoriten: Eine Stunde mit Empfehlungen der Bayern

Sven Tasnadi

Ohne Titel - Magdalena Adriane

Personal Label Printer Starter Paket Personal Label Printer

Kultur, Freizeit, Sport - Museen

Die Bayern 2-Favoriten: Eine Stunde mit Empfehlungen der Bayern

Micrografx Designer 9

Japanische Review auf: http://www7b.biglobe.ne.jp/~mana2567

Bastelvorlage Schafsohren

neue «clean Label» alternativen