close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Interactive Visual Classification
with Euler Diagrams
Gennaro Cordasco,
Rosario De Chiara
Andrew Fish*
Università degli Studi di
Salerno, Italy
University of Brighton,
UK
*funded by UK EPSRC grant EP/E011160:
Visualization with Euler Diagrams.
Overview
• Classification Problem
– related Euler Diagram applications
• Diagram Abstraction Problem
• Concepts needed
– e.g. weakly reducible, marked points, …
• On-line algorithms
– complexity analysis
• EulerVC application demo
Andrew Fish, University of Brighton, UK
2
Classification Problem
• Resource classification is often challenging for
users, and commonly hierarchical
classifications are not sufficient for their needs.
• Free-form tagging approaches provide a flat
space, utilising different tagging and
visualisation mechanisms.
• What about using non-hierarchical
classification structures, and what about the
use of (Euler) diagrams…?
Andrew Fish, University of Brighton, UK
3
Related Euler Diagram Applications
• LHS [Inria]: Visualizing the numbers of documents matching a
query from a library database, facilitating query modifications.
• RHS [Salerno]: File organisation with VennFS allows the user to
draw Euler Diagrams in order to organize files within categories.
Andrew Fish, University of Brighton, UK
4
The main problem
• To compute the set of zones
associated to a given
collection of curves
• Zones are not so easy to
describe, they can be nonconvex, non-simply
connected,…
• How to update the zone set
when we add curves?
Andrew Fish, University of Brighton, UK
5
Euler Diagram Example
LHS: A concrete diagram with 4 contours (simple
closed curves in plane) and 6 zones (regions inside
a set of contours and outside the rest).
A
B
C
{A,B}
D
{B}
{B,C}
{C}
{D}
∅
RHS: Depicts the abstract diagram/set system, which
is the abstraction of the LHS:
d= {A,B,C,D}, {∅,{B},{C},{D},{A,B},{B,C}} 
6
Euler Diagram Problems: static
Generation
Abstract ED/ Set System
Concrete ED
Abstraction
Andrew Fish, University of Brighton, UK
7
Euler Diagram Problems: dynamic
Generation
Abstract ED
Concrete ED
Transformations
Transformations
Abstraction
Andrew Fish, University of Brighton, UK
8
Euler Diagram Problems: dynamic
Wellformedness conditions
Generation
Abstract ED
Concrete ED
Transformations
Transformations
Abstraction
Andrew Fish, University of Brighton, UK
9
ED wellformedness conditions
• contours are simple closed curves,
each with a single, unique label;
• contours meet transversely (so no
tangential meetings or concurrency)
and at most two contours meet at a
single point;
• zones cannot be disconnected
– i.e. each minimal region is a zone.
• Or, if you prefer… wellformed Euler
diagrams can be thought of as
“simple Euler diagrams”; i.e.
simple Venn diagrams where some
regions of intersection can be
empty/missing”.
Andrew Fish, University of Brighton, UK
10
Fast Diagram Interpretation
Given a wellformed concrete Euler diagram d:
1. compute the abstract Euler diagram for d
A
B
4 Zones:
{A}
{A,B}
{B}
∅
Andrew Fish, University of Brighton, UK
11
Fast Diagram Interpretation
Given a wellformed concrete Euler diagram d:
1. compute the abstract Euler diagram for d
2. evaluate if the addition of a new contour or removal of an
existing contour yields a wellformed diagram (and update
the abstract diagram accordingly).
A
A
C
B
C
Andrew Fish, University of Brighton, UK
B
12
Fast Diagram Interpretation
• On-line approach
– We consider the diagram construction using the
natural operations of contour addition/removal.
A
A
B
A
B
B
C
C
Timeline
Andrew Fish, University of Brighton, UK
13
Fast Diagram Interpretation
• On-line approach
– We consider the diagram construction using the
natural operations of contour addition/removal.
– What class of diagrams is this?
A
A
B
A
B
B
C
C
Timeline
Andrew Fish, University of Brighton, UK
14
Weakly reducible Euler Diagrams
• Reducible Venn diagrams [e.g. see Ruskey 97]
– the removal of one of its curves yields a Venn diagram
• Reducible Euler diagrams
– the removal of one of its curves yields a WF Euler
diagram
• Completely reducible Euler diagrams
– There is a sequence of curve removals that yields the
empty ED through WF diagrams (or a sequence of curve
additions from the empty ED).
• Weakly reducible Euler diagrams
– There is a sequence of curve removals and additions
that yields the empty ED through WF diagrams.
Andrew Fish, University of Brighton, UK
15
Weakly reducible Euler Diagrams
WF Euler diagrams
Reducible
?
?
Weakly Reducible
Completely Reducible
Andrew Fish, University of Brighton, UK
16
Weakly reducible Euler Diagrams
WF Euler diagrams
Reducible
?
?
Weakly Reducible
Completely Reducible
Andrew Fish, University of Brighton, UK
17
Weakly reducible Euler Diagrams
WF Euler diagrams
Reducible
?
?
Weakly Reducible
Link to Proof
Completely Reducible
Andrew Fish, University of Brighton, UK
18
Weakly reducible Euler Diagrams
WF Euler diagrams
Reducible
?
?
Weakly Reducible
Link to Proof
Completely Reducible
Andrew Fish, University of Brighton, UK
19
Wellformedness online verification
• Theorem 1: Let d = C, Z, be a weakly reducible Euler
diagram, then |Z| = ip(d) + cc(d) + 1 where
– cc(d) denotes the number of components
– ip(d) denotes number of intersection points
1 component
6 intersection points
1+6+1=8 zones
2 component
2 intersection points
2+2+1=5 zones
3 component
4 intersection points
3+4+1=8 zones
20
Wellformedness online verification
• Theorem 1: Let d = C, Z, be a weakly reducible Euler
diagram, then |Z| = ip(d) + cc(d) + 1 where
– cc(d) denotes the number of components
– ip(d) denotes number of intersection points
• Proof: by induction for single component case
– Use that the addition of a new contour
generates x > 1 intersection points splitting the
new contour into x segments, each of which
splits a different zone (otherwise the component
was not connected) and so we have x new zones.
Andrew Fish, University of Brighton, UK
A
21
Wellformedness online verification
• Theorem 1: Let d = C, Z, be a weakly reducible Euler
diagram, then |Z| = ip(d) + cc(d) + 1 where
– cc(d) denotes the number of components
– ip(d) denotes number of intersection points
• Corollary of Proof: The addition of a simple closed
curve A to a weakly reducible diagram d which
only meets d in transverse intersections at points
which are not intersection points of d yields a
WF Euler diagram iff d+A satisfies the
“zones condition” above.
Andrew Fish, University of Brighton, UK
A
22
Wellformedness online verification
• Theorem 1: Let d = C, Z, be a weakly reducible Euler
diagram, then |Z| = ip(d) + cc(d) + 1 where
– cc(d) denotes the number of components
– ip(d) denotes number of intersection points
• Corollary of Proof: The addition of a simple closed
curve A to a weakly reducible diagram d which
only meets d in transverse intersections at points
which are not intersection points of d yields a
WF Euler diagram iff d+A satisfies the
“zones condition” above.
• The point(s):
A
– We have enough points to “mark” the zone set
– Can check wellformedness after curve addition by counting
Andrew Fish, University of Brighton, UK
23
Euler Diagram Abstraction
For our interface, we want both:
– Quick construction method
– Quick interpretation method
So, we consider the use of ellipses.
Given two ellipses A and B, one can quickly find:
– their intersection points (in particular, since in a wellformed
diagram tangential points are not allowed, we will have 0, 2 or 4
intersection points);
– their relationship (that is, if they overlap, if one is contained in the
other or if they are disjoint)
Andrew Fish, University of Brighton, UK
24
Marked Points
• We can represent each zone of d using a single marked
point; that is, we associate to each zone z  Z(d) a single
point m( x)  R2 such that m( x)  cl ( z ) where cl(z) is the
closure of z.
C
E
D
A
B
Andrew Fish, University of Brighton, UK
25
Marked Points
• We can represent each zone of d using a single marked
point; that is, we associate to each zone z  Z(d) a single
point m( x)  R2 such that m( x)  cl ( z ) where cl(z) is the
closure of z.
C
E
D
A
B
Andrew Fish, University of Brighton, UK
26
Marked Points
• We can represent each zone of d using a single marked
point; that is, we associate to each zone z  Z(d) a single
point m( x)  R2 such that m( x)  cl ( z ) where cl(z) is the
closure of z.
C
E
D
A
B
Andrew Fish, University of Brighton, UK
27
Marked Points
• We can represent each zone of d using a single marked
point; that is, we associate to each zone z  Z(d) a single
point m( x)  R2 such that m( x)  cl ( z ) where cl(z) is the
closure of z.
C
E
D
A
B
Andrew Fish, University of Brighton, UK
28
Marked Points
• We can represent each zone of d using a single marked
point; that is, we associate to each zone z  Z(d) a single
point m( x)  R2 such that m( x)  cl ( z ) where cl(z) is the
closure of z.
C
E
D
A
B
Andrew Fish, University of Brighton, UK
29
Marked Points
• We can represent each zone of d using a single marked
point; that is, we associate to each zone z  Z(d) a single
point m( x)  R2 such that m( x)  cl ( z ) where cl(z) is the
closure of z.
C
E
D
A
B
Andrew Fish, University of Brighton, UK
30
Marked Points
• We can represent each zone of d using a single marked
point; that is, we associate to each zone z  Z(d) a single
point m( x)  R2 such that m( x)  cl ( z ) where cl(z) is the
closure of z.
C
E
D
A
B
Andrew Fish, University of Brighton, UK
And we can update
this set of marked
points
appropriately upon
the addition or
removal of curves.
31
Ellipse Addition
d is a wellformed diagram
d
C
d +E is a wellformed diagram
D
E
E
A
Draw a
new
contour E
Compute
E's
relationshi
p with d
Update
covered
Zones
Cont(E)
Over(E)
Inter(E)
E
Update
Marked
Points
Is d +E
wellformed ?
yes
B
Generate
new Zones
E
Andrew Fish, University of Brighton, UK
no
Add E to d
Reject A
Compute
Split zones
E
32
Ellipse Addition
d is a wellformed diagram
d
C
d +E is a wellformed diagram
D
E
E
A
Draw a
new
contour E
Compute
E's
relationshi
p with d
Update
covered
Zones
Cont(E)
Over(E)
Inter(E)
E
Update
Marked
Points
Is d +E
wellformed ?
yes
B
Generate
new Zones
Zd={, {A}, {B}, {C}, {A,B}, {A,C}, {B,C}, {C,D}, {A,B,C}}
E
Andrew Fish, University of Brighton, UK
no
Add E to d
Reject A
Compute
Split zones
E
33
Ellipse Addition
d is a wellformed diagram
d is a wellformed diagram
d
C
d +E is a wellformed diagram
D
E
E
A
Draw a
new
contour E
Compute
E's
relationshi
p with d
Update
covered
Zones
Cont(E)
Over(E)
Inter(E)
E
Update
Marked
Points
Is d +E
wellformed ?
yes
B
Generate
new Zones
Zd={, {A}, {B}, {C}, {A,B}, {A,C}, {B,C}, {C,D}, {A,B,C}}
E
Andrew Fish, University of Brighton, UK
no
Add E to d
Reject A
Compute
Split zones
E
34
Ellipse Addition
Compute E's relationship with d
d is a wellformed diagram
d
C
E
A
x2
d +E is a wellformed diagram
D
E
x1
E
Draw a
new
contour E
x3
x6
x5
Compute
E's
relationshi
p with d
Update
covered
Zones
x4
Cont(E)
Over(E)
Inter(E)
E
Update
Marked
Points
Is d +E
wellformed ?
yes
B
Generate
new Zones
Zd={,{A},{B},{C},{A,B},{A,C},{B,C},{C,D},{A,B,C}}
Cont(E)=
Over(E)={A,B,C}
Inter(E)={x1,x2,x3,x4,x5,x6}
E
Andrew Fish, University of Brighton, UK
no
Add E to d
Reject A
Compute
Split zones
E
35
Ellipse Addition
Zd={,{A},{B},{C},{A,B},{A,C},{B,C},{C,D},{A,B,C}}
Cont(E)=
Over(E)={A,B,C}
Inter(E)={x1,x2,x3,x4,x5,x6}
Is d +E wellformed ?
d is a wellformed diagram
d
C
E
A
x2
d +E is a wellformed diagram
D
E
x1
E
Draw a
new
contour E
x3
x6
x5
Compute
E's
relationshi
p with d
Update
covered
Zones
x4
Cont(E)
Over(E)
Inter(E)
E
Update
Marked
Points
Is d +E
wellformed ?
yes
B
Generate
new Zones
E
By using
Thm 1
Andrew Fish, University of Brighton, UK
no
Add E to d
Reject A
Compute
Split zones
E
36
Ellipse Addition
Zd={,{A},{B},{C},{A,B},{A,C},{B,C},{C,D},{A,B,C}}
Cont(E)=
Over(E)={A,B,C}
Inter(E)={x1,x2,x3,x4,x5,x6}
Each arc splits
exactly one zone
Compute Split zones
d is a wellformed diagram
d
C
E
A
x2
d +E is a wellformed diagram
D
E
x1
E
Draw a
new
contour E
x3
x6
x5
Compute
E's
relationshi
p with d
Update
covered
Zones
x4
Cont(E)
Over(E)
Inter(E)
E
Update
Marked
Points
Is d +E
wellformed ?
yes
B
Generate
new Zones
E
Andrew Fish, University of Brighton, UK
no
Add E to d
Reject A
Compute
Split zones
E
37
Ellipse Addition
Zd={,{A},{B},{C},{A,B},{A,C},{B,C},{C,D},{A,B,C}}
Cont(E)=
Over(E)={A,B,C}
Inter(E)={x1,x2,x3,x4,x5,x6}
Each arc splits
exactly one zone
Compute Split zones
d is a wellformed diagram
d
C
E
A
x2
d +E is a wellformed diagram
D
E
x1
E
Draw a
new
contour E
x3
x6
x5
Compute
E's
relationshi
p with d
Update
covered
Zones
x4
Cont(E)
Over(E)
Inter(E)
E
Update
Marked
Points
Is d +E
wellformed ?
yes
B
Generate
new Zones
Split Zones={, {C}, {B,C},{B},{A,B},{A}}
E
Andrew Fish, University of Brighton, UK
no
Add E to d
Reject A
Compute
Split zones
E
38
Ellipse Addition
Zd={,{A},{B},{C},{A,B},{A,C},{B,C},{C,D},{A,B,C}}
Cont(E)=
Over(E)={A,B,C}
Inter(E)={x1,x2,x3,x4,x5,x6}
Generate new zones
d is a wellformed diagram
d
C
E
A
x2
d +E is a wellformed diagram
D
E
x1
E
Draw a
new
contour E
x3
x6
x5
Compute
E's
relationshi
p with d
Update
covered
Zones
x4
Cont(E)
Over(E)
Inter(E)
E
Update
Marked
Points
Is d +E
wellformed ?
yes
B
Generate
new Zones
Split Zones={, {C}, {B,C},{B},{A,B},{A}}
New Zones={{E}, {C,E}, {B,C,E}, {B,E}, {A,B,E}, {A,E}}
E
Andrew Fish, University of Brighton, UK
no
Add E to d
Reject A
Compute
Split zones
E
39
Ellipse Addition
Zd={,{A},{B},{C},{A,B},{A,C},{B,C},{C,D},{A,B,C}}
Cont(E)=
Over(E)={A,B,C}
Inter(E)={x1,x2,x3,x4,x5,x6}
Update marked points
d
C
E
A
x1
x2
d is a wellformed diagram
D
d +E is a wellformed diagram
y1
y2
E
x3
E
Draw a
new
contour E
x6
x5
Compute
E's
relationshi
p with d
Update
covered
Zones
x4
Cont(E)
Over(E)
Inter(E)
E
Update
Marked
Points
B
Is d +E
wellformed ?
yes
Points x2 and x3 are swapped with y1 and y2,
respectively. For instance, y1 previously
marking {C} in d now marks {C,E}, whilst {C}
is marked by x2.
Generate
new Zones
E
Andrew Fish, University of Brighton, UK
no
Add E to d
Reject A
Compute
Split zones
E
40
Ellipse Addition
Zd={,{A},{B},{C},{A,B},{A,C},{B,C},{C,D},{A,B,C}}
Cont(E)=
Over(E)={A,B,C}
Inter(E)={x1,x2,x3,x4,x5,x6}
Update covered zones
d
C
E
A
x1
x2
D
d +E is a wellformed diagram
y1
y2
y3
d is a wellformed diagram
E
x3
E
Draw a
new
contour E
x6
x5
Compute
E's
relationshi
p with d
Update
covered
Zones
y4
x4
Cont(E)
Over(E)
Inter(E)
E
Update
Marked
Points
B
Is d +E
wellformed ?
yes
Zones {A,C} and {A,B,C} are not split and their
marking points, y3 and y4, are in interior(E),
so these zones need to be updated and
become {A,C,E} and {A,B,C,E}.
Generate
new Zones
E
Andrew Fish, University of Brighton, UK
no
Add E to d
Reject A
Compute
Split zones
E
41
Ellipse Addition
d+E is a wellformed diagram
d is a wellformed diagram
C
E
d +E is a wellformed diagram
D
E
E
A
Draw a
new
contour E
Compute
E's
relationshi
p with d
Update
covered
Zones
Cont(E)
Over(E)
Inter(E)
E
Update
Marked
Points
Is d +E
wellformed ?
yes
B
Generate
new Zones
Zd+E={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E},
{C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}}
E
Andrew Fish, University of Brighton, UK
no
Add E to d
Reject A
Compute
Split zones
E
42
Ellipse Addition
d+E is a wellformed diagram
d is a wellformed diagram
d
C
E
A
x2
d +E is a wellformed diagram
D
E
x1
E
Draw a
new
contour E
x3
x6
x5
Compute
E's
relationshi
p with d
Update
covered
Zones
x4
Cont(E)
Over(E)
Inter(E)
E
Update
Marked
Points
Is d +E
wellformed ?
yes
B
Generate
new Zones
Zd+E={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E},
{C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}}
Skip Ellipse Deletion
E
Andrew Fish, University of Brighton, UK
no
Add E to d
Reject A
Compute
Split zones
E
43
Ellipse Removal
d=d+E
d is a wellformed diagram
CC
C
E
d -C is a wellformed diagram
D
CC
A
Remove a
contour C
Compute C's
relationship
with d-C
Update
covered
Zones
C
Cont(E)
Over(E)
Inter(E)
Update
Is d - C
Marked
wellformed ?
Points
yes
no
B
Merge
Zones
Zd={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E},
{C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}}
C
Andrew Fish, University of Brighton, UK
Remove C
Reject A
from d
Compute
Split zones
C
44
Ellipse Removal
d=d+E
d is a wellformed diagram
d
CC
C
E
A
x2
d -C is a wellformed diagram
D
CC
x1
Remove a
contour C
x3
x6
x5
Compute C's
relationship
with d-C
Update
covered
Zones
x4
C
Cont(E)
Over(E)
Inter(E)
Update
Is d - C
Marked
wellformed ?
Points
yes
no
B
Merge
Zones
Zd={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E},
{C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}}
C
Andrew Fish, University of Brighton, UK
Remove C
Reject A
from d
Compute
Split zones
C
45
Ellipse Removal
d is a wellformed diagram
d is a wellformed diagram
CC
C
E
d -C is a wellformed diagram
D
CC
A
Remove a
contour C
Compute C's
relationship
with d-C
Update
covered
Zones
C
Cont(E)
Over(E)
Inter(E)
Update
Is d - C
Marked
wellformed ?
Points
yes
no
B
Merge
Zones
Zd={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E},
{C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}}
C
Andrew Fish, University of Brighton, UK
Remove C
Reject A
from d
Compute
Split zones
C
46
Ellipse Removal
Compute C’s relationship with d-C
d is a wellformed diagram
CC
C
z2
E
d -C is a wellformed diagram
D
CC
z1
A
Remove a
contour C
z6
z3
z5
Compute C's
relationship
with d-C
Update
covered
Zones
z4
C
Cont(E)
Over(E)
Inter(E)
Update
Is d - C
Marked
wellformed ?
Points
yes
no
B
Merge
Zones
Zd={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E},
{C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}}
Cont(C)=∅
Over(C)={A,B,E}
Inter(C)={z1,z2,z3,z4,z5,z6}
C
Andrew Fish, University of Brighton, UK
Remove C
Reject A
from d
Compute
Split zones
C
47
Ellipse Removal
Zd={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E},
{C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}}
Cont(C)=∅
Over(C)={A,B,E}
Inter(C)={z1,z2,z3,z4,z5,z6}
Is d-C wellformed?
d is a wellformed diagram
CC
C
z2
E
d -C is a wellformed diagram
D
CC
z1
A
Remove a
contour C
z6
z3
z5
Compute C's
relationship
with d-C
Update
covered
Zones
z4
C
Cont(E)
Over(E)
Inter(E)
Update
Is d - C
Marked
wellformed ?
Points
yes
no
B
Merge
Zones
C
Remove C
Reject A
from d
Compute
Split zones
C
Only disconnected zones
need to be checked.
Andrew Fish, University of Brighton, UK
48
Ellipse Removal
Zd={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E},
{C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}}
Cont(C)=∅
Over(C)={A,B,E}
Inter(C)={z1,z2,z3,z4,z5,z6}
Each arc splits
exactly one zone
Compute Split zones
d is a wellformed diagram
CC
C
z2
E
d -C is a wellformed diagram
D
CC
z1
A
Remove a
contour C
z6
z3
z5
Compute C's
relationship
with d-C
Update
covered
Zones
z4
C
Cont(E)
Over(E)
Inter(E)
Update
Is d - C
Marked
wellformed ?
Points
yes
no
B
Merge
Zones
Split Zones={ ,{B}, {E}, {A,E}, {B,E}, {A,B,E}}
C
Andrew Fish, University of Brighton, UK
Remove C
Reject A
from d
Compute
Split zones
C
49
Ellipse Removal
Zd={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E},
{C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}}
Cont(C)=∅
Over(C)={A,B,E}
Inter(C)={z1,z2,z3,z4,z5,z6}
Each arc splits
exactly one zone
Merge zones
d is a wellformed diagram
CC
C
z2
E
d -C is a wellformed diagram
D
CC
z1
A
Remove a
contour C
z6
z3
z5
z4
Compute C's
relationship
with d-C
Update
covered
Zones
C
Cont(E)
Over(E)
Inter(E)
Update
Is d - C
Marked
wellformed ?
Points
yes
no
B
Merge
Zones
C
Andrew Fish, University of Brighton, UK
Remove C
Reject A
from d
Compute
Split zones
C
50
Ellipse Removal
Zd={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E},
{C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}}
Cont(C)=∅
Over(C)={A,B,E}
Inter(C)={z1,z2,z3,z4,z5,z6}
Remove marked points that belong to C
d is a wellformed diagram
CC
C
z2
E
d -C is a wellformed diagram
D
CC
z1
A
Remove a
contour C
z6
z3
z5
z4
Compute C's
relationship
with d-C
Update
covered
Zones
C
Cont(E)
Over(E)
Inter(E)
Update
Is d - C
Marked
wellformed ?
Points
yes
no
B
Merge
Zones
C
Andrew Fish, University of Brighton, UK
Remove C
Reject A
from d
Compute
Split zones
C
51
Ellipse Removal
Zd={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E},
{C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}}
Cont(C)=∅
Over(C)={A,B,E}
Inter(C)={z1,z2,z3,z4,z5,z6}
Remove marked points that belong to C
d is a wellformed diagram
CC
C
E
d -C is a wellformed diagram
D
CC
A
Remove a
contour C
Compute C's
relationship
with d-C
Update
covered
Zones
C
Cont(E)
Over(E)
Inter(E)
Update
Is d - C
Marked
wellformed ?
Points
yes
no
B
Merge
Zones
C
Andrew Fish, University of Brighton, UK
Remove C
Reject A
from d
Compute
Split zones
C
52
Ellipse Removal
Zd={, {A}, {B}, {C}, {E}, {A,B}, {A,E}, {B,C}, {B,E},
{C,D}, {C,E}, {A,B,E}, {A,C,E}, {B,C,E}, {A,B,C,E}}
Cont(C)=∅
Over(C)={A,B,E}
Inter(C)={z1,z2,z3,z4,z5,z6}
Update covered zones
d is a wellformed diagram
CC
C
E
d -C is a wellformed diagram
D
CC
A
Remove a
contour C
Compute C's
relationship
with d-C
Update
covered
Zones
C
Cont(E)
Over(E)
Inter(E)
Update
Is d - C
Marked
wellformed ?
Points
yes
no
B
Merge
Zones
Zone {C,D} is not split by C and its marked
point is in interior(C), so it needs to be
updated and it becomes {D}.
C
Andrew Fish, University of Brighton, UK
Remove C
Reject A
from d
Compute
Split zones
C
53
Ellipse Removal
d-C is a wellformed diagram
d is a wellformed diagram
CC
E
d -C is a wellformed diagram
D
CC
A
Remove a
contour C
Compute C's
relationship
with d-C
Update
covered
Zones
C
Cont(E)
Over(E)
Inter(E)
Update
Is d - C
Marked
wellformed ?
Points
yes
no
B
Merge
Zones
Zd-C={, {A}, {B}, {E}, {D}, {A,B}, {A,E}, {B,E}, {A,B,E},}
C
Andrew Fish, University of Brighton, UK
Remove C
Reject A
from d
Compute
Split zones
C
54
Complexity
• Ellipse addition and removal algorithms are
similar and their complexity is
Andrew Fish, University of Brighton, UK
55
Complexity
d is a wellformed diagram
O(|Z|)
O(|C|)
d +E is a wellformed diagram
E
E
Draw a
new
contour E
Compute
E's
relationshi
p with d
Update
covered
Zones
O(|C|)
O(|C|)
Cont(E)
Over(E)
Inter(E)
E
Update
Marked
Points
Is d +E
wellformed ?
yes
Generate
new Zones
E
O(|C|)
For each
other curve,
compute
intersection
points with E;
if curve C
disjoint then
check if
marked point
for C is in
interior (E)
no
Add E to d
Reject A
Compute
Split zones
E
O(|C| log |C|)
56
Complexity
d is a wellformed diagram
O(|Z|)
O(|C|)
d +E is a wellformed diagram
E
E
Draw a
new
contour E
Compute
E's
relationshi
p with d
Update
covered
Zones
O(|C|)
O(|C|)
Cont(E)
Over(E)
Inter(E)
E
Update
Marked
Points
Is d +E
wellformed ?
yes
Generate
new Zones
E
O(|C|)
no
Add E to d
Reject A
Compute
Split zones
Check no
tangential/triple
points created.
Check WF using
the number of
intersection
points of E with
other curves
(Thm 1)
E
O(|C| log |C|)
57
Complexity
d is a wellformed diagram
O(|Z|)
O(|C|)
d +E is a wellformed diagram
E
E
Draw a
new
contour E
Compute
E's
relationshi
p with d
Update
covered
Zones
O(|C|)
O(|C|)
Cont(E)
Over(E)
Inter(E)
E
Update
Marked
Points
Is d +E
wellformed ?
yes
Generate
new Zones
E
O(|C|)
no
Add E to d
Reject A
Compute
Split zones
E
a) Each arc splits
exactly 1 zone
b) # arcs = O(|C|)
c) Consecutive
arcs split zones
which differ by
one exactly
contour, so we
order the
points of
inter(E).
O(|C| log |C|)
58
Complexity
d is a wellformed diagram
O(|Z|)
O(|C|)
d +E is a wellformed diagram
E
E
Draw a
new
contour E
Compute
E's
relationshi
p with d
Update
covered
Zones
O(|C|)
O(|C|)
Cont(E)
Over(E)
Inter(E)
E
Update
Marked
Points
Is d +E
wellformed ?
yes
Generate
new Zones
Add E to split
zones
E
O(|C|)
no
Add E to d
Reject A
Compute
Split zones
E
O(|C| log |C|)
59
Complexity
d is a wellformed diagram
O(|Z|)
O(|C|)
d +E is a wellformed diagram
E
E
Draw a
new
contour E
Compute
E's
relationshi
p with d
Update
covered
Zones
O(|C|)
O(|C|)
Cont(E)
Over(E)
Inter(E)
E
Update
Marked
Points
Is d +E
wellformed ?
yes
Iterate through
Inter(E) and
perform set
membership check
O(|C|)
Generate
new Zones
E
no
Add E to d
Reject A
Compute
Split zones
E
O(|C| log |C|)
60
Iterate through
non-split zone set
and check if their
marked point is
in interior(E)
Complexity
d is a wellformed diagram
O(|Z|)
O(|C|)
d +E is a wellformed diagram
E
E
Draw a
new
contour E
Compute
E's
relationshi
p with d
Update
covered
Zones
O(|C|)
O(|C|)
Cont(E)
Over(E)
Inter(E)
E
Update
Marked
Points
Is d +E
wellformed ?
yes
Generate
new Zones
E
O(|C|)
no
Add E to d
Reject A
Compute
Split zones
E
O(|C| log |C|)
61
A naive approach
d is an Euler diagram
f(|C|) = time
needed to check if
a given zone is
present in d + E
O(1)
Draw a
new
contour
E
O(|Z|f(|C|))
E
A new
contour
is added
Check
Zones
E
Duplicate
each zone
O(|Z|)
O(|Z|f(|C|))
62
EulerVC
• As a proof of concept we have implemented
the algorithms as general purpose Java
library
– And used it to build a small application which
allows users to use Euler Diagrams to classify
internet bookmarks on their desktop, or on
Delicious…
Andrew Fish, University of Brighton, UK
63
“Delicious is a social bookmarking web
service for storing, sharing, and
discovering web bookmarks” (from Wikipedia)
– Users can tag each of their bookmarks with
freely chosen index terms
Andrew Fish, University of Brighton, UK
64
Bookmark
Tags
Andrew Fish, University of Brighton, UK
65
EulerVC: skip slides; demo tool
66
EulerVC
Andrew Fish, University of Brighton, UK
67
EulerVC
Andrew Fish, University of Brighton, UK
68
EulerVC
Andrew Fish, University of Brighton, UK
69
EulerVC
Andrew Fish, University of Brighton, UK
70
EulerVC
Andrew Fish, University of Brighton, UK
71
EulerVC
Andrew Fish, University of Brighton, UK
72
EulerVC
Andrew Fish, University of Brighton, UK
73
EulerVC
Andrew Fish, University of Brighton, UK
74
EulerVC
Andrew Fish, University of Brighton, UK
75
EulerVC
Andrew Fish, University of Brighton, UK
76
EulerVC
Andrew Fish, University of Brighton, UK
77
EulerVC
Andrew Fish, University of Brighton, UK
78
EulerVC
Andrew Fish, University of Brighton, UK
79
EulerVC
Andrew Fish, University of Brighton, UK
80
EulerVC
81
Conclusion
• Algorithms developed to solve the on-line diagram
abstraction problem.
• EulerVC application constructed useful for:
– User classification of resources (requires user testing…)
– Exploratory research of diagram properties like weak
reducibility (see Symmetric Venn(5) with Ellipses)
• Future plans:
–
–
–
–
Handle NWF cases by extending the use of marked pts
General resource handling (web pages, photos, files...)
Integration with EulerView idea (for larger scale)
Investigate diagram classes
Andrew Fish, University of Brighton, UK
82
Blank
Andrew Fish, University of Brighton, UK
83
1/--страниц
Пожаловаться на содержимое документа