Sketching Slides [Elektronische Ressource] : interactive creation and automatic solution of constrained document layout problems / Sebastian Christoph Theophil. Gutachter: Hans-Dieter Burkhard ; Markus Hannebauer ; Irfan Essa

Theophil Sebastian Christoph

Sujets

• Informatik

Informations

• Publié par: humboldt-universitat_zu_berlin
• Publié le: 01 janvier 2011
• Nombre de lectures: 18
• Langue: English
• Poids de l'ouvrage: 7 Mo

Extrait

Sketching Slides
Interactive Creation and Automatic Solution of Constrained
Document Layout Problems
DISSERTATION
zur Erlangung des akademischen Grades
doctor rerum naturalium
(Dr. rer. nat.)
im Fach Informatik
eingereicht an der
Mathematisch-Naturwissenschaftlichen Fakultät II
Humboldt-Universität zu Berlin
von
Herrn Dipl.-Inf. Sebastian Christoph Theophil
geboren am 28.11.1979 in Berlin
Präsident der Humboldt-Universität zu Berlin:
Prof. Dr. Dr. h.c. Christoph Markschies
Dekan der Mathematisch-Naturwissenschaftlichen Fakultät II:
Prof. Dr. Peter Frensch
Gutachter:
1. Prof. Dr. Hans-Dieter Burkhard
2. Dr. Markus Hannebauer
3. Prof. Irfan Essa, PhD
eingereicht am: 6.10.2010
Tag der mündlichen Prüfung: 18.2.2011Abstract
The efficiency of desktop publishing is severely limited by the lack of sophisti-
cated automatic document layout systems. State-of-the-art algorithms either
require the input to be written in a description language such as HTML and
ALT X, or to be a manually designed layout template. However, descriptionE
languages are ill-suited to express layout problems with weak semantics and
layout templates shift the burden from the end user to the template designer.
This thesis defines a general layout problem with linear constraints in
simple geometric terms. This problem definition encompasses many well-
researched layout problems, including table layout problems, yellow page
layout problems, and many user interface layout problems.
The first contribution of this thesis is an algorithm that solves this gen-
eral class of layout problems by treating them as equitable resource allo-
cation problems. The available document area is a resource that is dis-
tributed among inter-element gaps. The layout problem is transformed into
a lexicographic min-ordering optimization problem that is solved using linear
programming techniques in real-time. User-generated input problems are fre-
quentlyover-orunder-constrained. Ifthelayoutproblemisover-constrained,
the quality of the solution layout degrades gracefully. The layout algorithm
finds the solution layout with the most equitable distribution of constraint
errors among the soft layout constraints, i.e., the solution closest to the
user’s original intent. Conversely, the layout algorithm detects the under-
constrained subproblems that adversely affect the solution layout. It adds
the minimal number of constraints required to achieve the fully specified
layout problem that is closest to the user’s input.
The second contribution of this thesis is the creation of an intuitive di-
rect manipulation user interface that lets users create the aforementioned
class of general constrained layout problems. It hides the complexity of the
constraint system and avoids the usability problems that have plagued con-
straint drawing applications. It eliminates the need of document description
languages and manually-created layout templates.
The layout algorithm and the user interface have been implemented in
our ICBM system. In the evaluation, we show that the best state-of-the-art
specialized table layout algorithms do not outperform the general ICBM lay-
out algorithm by any significant margin.
Keywords:
Automatic Layout, Constraint Drawing, Interaction, OptimizationZusammenfassung
Die Entwicklung effizienter Desktop Publishing Systeme wird behindert
durch den Mangel an leistungsfähigen, automatischen Layoutalgorithmen.
Aktuelle Algorithmen zum Layout ganzer Dokumente oder einzelner Seiten
erfordern entweder die Formulierung des Layoutproblems in einer formalen
Beschreibungssprache, oder sie benötigen fertige, detaillierte Layouttempla-
tes. Layoutprobleme mit schwacher Semantik lassen sich schlecht in formale
Sprachen umsetzen, Layout Templates verschieben den manuellen Aufwand
nur vom Endnutzer zum Template Designer.
DieseDissertationdefinierteinallgemeines,geometrischesLayoutproblem
mit linearen Constraints. Dieses Problem umfasst verschiedene, gut unter-
suchte Layoutprobleme, z.B. Tabellenlayout, Yellow Page Layout, und User
Interface Layout Probleme.
Das erste Ergebnis dieser Dissertation ist ein Layoutalgorithmus, der das
beschriebene Layoutproblem löst, in dem er es als Ressourcenallokationspro-
bleminterpretiert.DieFlächeeinereinzelnenSeiteisteineRessource,diezwi-
schen den visuellen Elementen einer Seite verteilt wird. Das Layoutproblem
wird in ein lexikographisches min-ordering Optimierungsproblem übersetzt,
das durch lineare Optimierung in Echtzeit gelöst wird. Die Lösungen manuell
erzeugter Layoutprobleme sind häufig über- oder unterbestimmt. Wenn das
Problem überbestimmt ist, also keine gültige Lösung besitzt, muss der Algo-
rithmus die Lösung finden, die am nächsten an der intendierten Lösung ist.
Der Algorithmus erkennt nicht eindeutig definierte Probleme mit unbefriedi-
genden Lösungen und fügt die minimal notwendige Anzahl von Constraints
hinzu um das vom Nutzer beabsichtigte Layout zu erzeugen.
Das zweite Ergebnis dieser Dissertation ist die Entwicklung einer intui-
tiven Benutzerschnittstelle, die es erlaubt, die vorhergehend beschriebenen
Layoutproblemezuerzeugen.SieverbirgtdieKomplexitätdesConstraintsys-
temsundvermeidetdieKomplexitätconstraint-basierterGrafikanwendungen
derVergangenheit.DieseBenutzerschnittstellemachtformaleBeschreibungs-
sprachen und manuell erzeugte Layouttemplates überflüssig.
Der Layoutalgorithmus und die Benutzerschnittstelle wurden als Teil des
ICBM Systems implementiert. Die Evaluation zeigt, dass die besten Tabel-
lenlayoutalgorithmen keine signifikant besseren Ergebnisse produzieren als
der allgemeinere ICBM Layout Algorithmus.
Schlagwörter:
Automatisches Layout, Constraints, Interaktion, OptimierungTo my family, Ines and Sophia.Contents
1 Introduction 3
1.1 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Background 9
2.1 Constraint Satisfaction . . . . . . . . . . . . . . . . . . . . . . 10
2.1.1 One-way Constraint Propagation . . . . . . . . . . . . 11
2.1.2 Multi-Wayt . . . . . . . . . . . 12
2.1.3 Linear Optimization Methods . . . . . . . . . . . . . . 13
2.1.4 Geometric and Non-Linear Constraint Solving . . . . . 16
2.2 Interactive Applications . . . . . . . . . . . . . . . . . . . . . 16
2.2.1 Constraint-Based Drawing . . . . . . . . . . . . . . . . 16
2.2.2 Snap-dragging . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.3 User Interface Toolkits . . . . . . . . . . . . . . . . . . 21
2.2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3 Document Layout . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.1 Task-specific Layout Algorithms . . . . . . . . . . . . . 26
2.3.2 Document Template . . . . . . . . . . . . . 27
2.3.3 Knowledge-based Document Layout . . . . . . . . . . . 28
2.3.4 Random Algorithms . . . . . . . . . . . . . . . . . . . 29
2.3.5 Specifying Complex Layouts . . . . . . . . . . . . . . . 29
2.3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.4 Interface Requirements of an Interactive Layout Application . 32
3 System Overview 35
3.1 The Chore of Manual Document Layout . . . . . . . . . . . . 35
3.2 Interactive Layout of Presentation Slides . . . . . . . . . . . . 37
3.3 The ICBM System . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3.1 User Interaction . . . . . . . . . . . . . . . . . . . . . . 39
3.3.2 Implicit Constraints . . . . . . . . . . . . . . . . . . . 39
3.3.3 Layout Algorithm . . . . . . . . . . . . . . . . . . . . . 40
v3.3.4 Implementation . . . . . . . . . . . . . . . . . . . . . . 41
3.4 Modeling the Application Domain . . . . . . . . . . . . . . . . 41
4 Interaction 47
4.1 The ICBM User Interface . . . . . . . . . . . . . . . . . . . . 47
4.1.1 Defining a Partial Gridline Order . . . . . . . . . . . . 47
4.1.2 Alignment . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.1.3 Removing Alignment Constraints . . . . . . . . . . . . 49
4.1.4 Over-constrained User Input . . . . . . . . . . . . . . . 51
4.1.5 Und Inputs . . . . . . . . . . . . . . . . 51
4.1.6 Designing the Snap Interaction . . . . . . . . . . . . . 52
4.2 Shape Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.2.1 Insertion Modes . . . . . . . . . . . . . . . . . . . . . . 55
4.2.2 Snapping Algorithm . . . . . . . . . . . . . . . . . . . 57
4.2.3 Sn Interior Gridlines . . . . . . . . . . . . . . . 60
4.2.4 Inserting Gridlines . . . . . . . . . . . . . . . . . . . . 62
4.2.5 Merging Snapped Gridlines . . . . . . . . . . . . . . . 65
4.2.6 Splitting Gridlines . . . . . . . . . . . . . . . . . . . . 65
4.3 Interaction with N Shapes . . . . . . . . . . . . . . . . . . . . 68
4.4 Manipulating Shapes . . . . . . . . . . . . . . . . . . . . . . . 69
4.4.1 Dragging Shapes . . . . . . . . . . . . . . . . . . . . . 69
4.4.2 Shape Rotation . . . . . . . . . . . . . . . . . . . . . . 73
4.4.3 Shape Alignment and Position . . . . . . . . . . . . . . 73
4.4.4 Size Constraints . . . . . . . . . . . . . . . . . . . . . . 77
4.4.5 Same Extent Constraints . . . . . . . . . . . . . . . . . 79
4.4.6 Size Constraint Visualization