CHI 97 Electronic Publications: Late-Breaking/Short Talks
An Automatic Method for Arranging Symbols and Widgets to Reflect their Internal Relations
Johan Hagman
SSKKII
Göteborg University
S-41298 Göteborg, Sweden
+46 31 773 1928
hagman@ling.gu.se
Abstract
The two data visualization techniques cluster analysis and Voronoi tessellation are combined to automatically arrange objects, e.g. the widgets of an interface, so that their positions within a given area reflect their internal relations. The method is illustrated as it arranges three sets of objects.
Keywords
Interface design, data visualization, mapping optimization, multi-dimensionality, cluster analysis, Voronoi diagram.
© 1997 Copyright on this material is held by the authors.
Introduction
"Now, let's arrange these things in a smart way before packing them neatly: these two go together, this a natural set of four, well, maybe five; and that one should be between ... No, like this they won't fit into the square! What if I move that group down here and then swap these ... Isn't there a way to do this automatically?" Yes, there is! This paper presents a method which may help when visualizing data, designing map displays or constructing widget interfaces.
Method
Cluster analysis (CA) [3] and Voronoi tessellation [5] are used to arrange a non-trivially small number of objects within a given space in such a way that closely related objects appear close to each other and the final result fulfills the requirements of symmetry. The result of combining these techniques is a type of data visualization which not only facilitates the mental grasping of complex relations between objects, but may also function as an outline for their placing in e.g. interface design. The input is either a table (objects*parameters) or an already prepared similarity matrix (objects*objects). The algorithm for weighted clustering is robust and allows input with missing data. The result of the last step is a balanced Voronoi diagram (VD). The process is illustrated by the following experiments.
Experiments
From a wide range of applications we choose three examples to illustrate how this method works and what it yields.
International Marine Signal Flags
The marine signal flags were clustered with respect to their colors and the configuration was Voronoi-tessellated as shown by Figure 1. The state of the VD in Figure 2, in the process of balancing, is already sufficient to suggest the arrangement of the flags in Figure 3. Flags with similar color combinations group themselves in continuous clusters.
Figures 1 and 2. Cluster configuration based on
color similarity between flags and its VD which is
later balanced to suggest the layout of Figure 3.
Figure 3. Flags ordered by
their colors within a square.
In another run the flags were clustered with patterns given the greatest weight. Figure 4 shows the outcome of this: where horizontal stripes in the upper left corner meet vertical stripes in the lower left corner we have diagonal stripes and check patterns; the monochrome flags in the lower right corner pass to patterns based on one and two diagonals in the upper right corner, from there it continues in other both orthogonally and diagonally symmetric patterns of "conquadratic" rectangles and crosses. Trying to distribute 26 flags evenly within the square we get a 5*5 matrix plus an extra flag in one of the columns.
Figure 4. Flags ordered by
their patterns within a square.
Letters and Digits Defined by a Matrix
The data here define 26 letters and 9 digits by an 5*7 pixel matrix. The plane in this case is also set to the proportions 5*7 which makes possible an even distribution of the 35 characters after the CA and VD steps (Figures 5-7). To show the maintenance of the clustering tendency the nearest neighbors of 'M' and '8' are indicated by grey shades: the lighter, the higher the number of equally activated pixels.
Figures 5-7. Letters and digits ordered by pixel similarity.
Buttons Representing Countries
This experiment is an apparent example of interface design. The objects are European countries connected to the World Wide Web and in this case no CA was done as they are arranged already in a useful way by their geographical positions. The button plate in Figure 8 was thus designed using the balanced VD based on the geometrical centroids of the countries. We see how each country must compromise regarding how many of its "real" neighbors it can be put next to. Again, the square root of their number is not an integer and therefore the button distribution cannot be totally even.
Figure 8. Country buttons, part of a WWW interface.
Concluding Remarks and Future Work
Using weighted CA and balanced VDs to optimally arrange symbols and widgets, earlier touched upon in [1,2], gives promising results as in the three new experiments reported here. Future work will explore how alternative techniques perform compared to or in combination with these. Special interest is directed to [6] and self-organizing maps [4]. We imagine a future combined in- and output device: a plate which replaces both the screen and the keyboard. Its keys and widgets are customizable projections onto a touch-screen which might be arranged using a method similar to this one.
Acknowledgements
This work was funded by NUTEK, the Swedish National Board for Industrial and Technical Development. I thank my colleague Lars Erik Holmquist for valuable comments.
References
1. Hagman, J., "Combining cluster analysis and Voronoi diagrams in data visualization and widget design" in Proc. of Edugraphics & Compugraphics '95 (ed. H.P. Santo), Graph. Sc. Promotions & Publ., 1995, 182-191.
2. Hagman, J., "Where data visualization and design meet", in Proc. of the Int'nal Conf. on Knowledge Transfer '96, (ed. A. Behrooz), Univ. of London, UK, 1996, 507-512.
3. Jain, A.K., and Dubes, R.C. Algorithms for Clustering Data, Prentice Hall Advanced Reference Series, 1988.
4. Lin, X. "Searching and browsing on map displays", ASIS'95 (http://www.uky.edu/~xlin/asis95.htm), 1995.
5. Okabe, A., Boots, B.N., and Sugihara, K. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, Wiley, 1992.
6. Shneiderman, B. "Tree visualizations with Tree-maps: a 2D space-filling approach", ACM Transactions on Graphics, Vol. 11, No. 1, 1992, 92-99.
CHI 97 Electronic Publications: Late-Breaking/Short Talks
