A SEMI-SMART LAYOUT ALGORITHM FOR FREEFORM VIEWS We desire an algorithm which optimizes the placement of a collection of elements (the set E) of various sizes (and/or weights) so as to minimize overlap while also minimizing memory usage and maximizing speed. 1 REQUIREMENTS We'll discuss the merits and limitations of proposed algorithms based upon their adherence with a general set of requirements, in addition to their memory requirements and speed. The set of requirements we hope to fulfill are: 1. Minimize overlap of elements 2. Support a suggested position for each element 3. Support a suggested radius for each element (in a polar coordinate system) 4. Support addition and removal of elements 5. Support changes in size of elements (both expansion and contraction) 6. Support fixed elements (locked in place) Other considerations include minimizing the total amount of positional change incurred by a given operation on the layout (addition, removal, scaling, etc.). Since the goal is to have a smooth layout in which elements shift (animated) into place, we hope to minimize both the number of elements that need to move and the distance they need to move for any given operation. 2 THE CURRENT ALGORITHM The algorithm currently proposed (although it differs in several key ways from that currently implemented in Sugar) makes use of a weight matrix to make optimal placements, and uses a simple collision detection scheme to handle addition, removal, and scaling of elements. 2.1 The grid The algorithm is built upon a weight matrix which tracks the placement of all elements. This matrix manifests as a 2D integer array containing values in the range [0, 255]. When visualizing the matrix, think instead of an image, where each cell represents a pixel, and the value stored at (x,y) represents the brightness of that pixel. Think of this image as a topographical map of sorts, with bright areas representing peaks and dark areas representing valleys. 2.2 Assigning weights When managing the matrix, we strive to make the weights assigned accurately represent the topology of the elements in the layout. Given an element, e, having dimensions m x n, we create an element matrix of the same dimensions within which which we assign weights to individual cells. The most correct approach (assuming no knowledge about the element other than its dimensions) is to apply weights to the cells of the element matrix in a gaussian fashion, such that the element is represented as a rounded surface, with the middle receiving the highest weight. This method is most consistent with the interpretation of the table as a topographical map, since it results in smooth gradients representing hills and valleys, with the centroid given the highest weight (collisions are "worse" the more they overlap). However, this approach also takes much effort, since the weight of each cell must be calculated. By extreme simplification, we could assign a constant value to each cell. This uniform approach takes no extra calculation, but results in a plateau rather than a hill, which poses problems in placement. A better solution, which takes only trivial calculation, uses a linear gradient. Using the linear model, we can visualize the element as a pyramid rather than a hill, which still maintains the important (for placement) property that there is a delta between two adjacent values. The following example illustrates a sample of the weights for a 5x5 element. Note that the three examples are not normalized (themselves, or with respect to each other). Gaussian Linear Uniform 0 1 2 1 0 1 1 1 1 1 1 1 1 1 1 1 4 6 4 1 1 2 2 2 1 1 1 1 1 1 2 6 9 6 2 1 2 3 2 1 1 1 1 1 1 1 4 6 4 1 1 2 2 2 1 1 1 1 1 1 0 1 2 1 0 1 1 1 1 1 1 1 1 1 1 Finally, we define the total weight of a given element, W_e, to be the sum over the weights of the cells of the element matrix. 2.2 Placement Placement of a new element is relatively straightforward given the weight matrix, since we can think of finding a good placement as rolling the new element into a valley - an area of low weight. We define the weight of a given placement, W_p to be the sum of the weights of the cells of the weight matrix where the element matrix overlaps. In other words, if we have an element of dimensions m x n positioned (with its upper left corner) at (x,y), we sum the cells of the weight matrix (i,j) with i: [y, y + n - 1] and j: [x, x + m - 1]. Placing an element amounts to summing the values of the element matrix with the weight matrix at the corresponding positions. We can also "pick up" an element by subtracting it's element matrix. Rather than finding the truly optimal placement by testing every cell, we instead make a number of trial placements, retaining the best solution found: the lowest value of W_p. The algorithm "short-circuits" if a placement is found such that W_p = 0, since this means there are no collisions at all. Once we have a best fit placement, we calculate (in O(n) time) the set of elements, C, which collide with the newly placed element e (and which are not fixed/locked). The goal is to then "roll" both e and the members of C into best-fit valleys. We do so by calculating the minimum of the weights of the current position and the four positions directly adjacent to each element (left, right, above, and below). Here you can see why we need weight deltas between adjacent cells of the element matrix: without, we can end up in a circumstance where an element is contained completely within another, thus sitting "on the plateau", such that the weight in all directions is equal to the current weight even though we should be trying hard to push the new element outside the containing one. When the current position for each element in C is better than (or equal to) all adjacent positions, we terminate the algorithm. Note also that we do NOT recurse on collision checks; instead, we only attempt to adjust the position of the elements which collide directly with the newly placed element. 2.3 Supporting a suggested position and radius We support suggested positions for elements by skipping the trial step, instead using the passed coordinate as the input to the remainder of the algorithm. Supporting a suggested radius is also relatively simple. By creating a separate trial algorithm which takes a position and a radius, we can limit the trial placements to points on the circle of the appropriate radius. 2.4 Scaling Scaling up is trivial, as we simply subtract the element matrix from the weight matrix, calculate a new element matrix for the new dimensions of the element, and then perform the placement algorithm again using its current location. Scaling down is nearly the same, however we must consider the set of adjacent elements, A, in addition to the set C of colliding elements. This ensures that, as the element shrinks, those around it can roll into the freed space, even if they weren't colliding with the shrinking element. The rest of the process remains the same. Removal, of course, is the same as scaling down, except we don't re-place the removed element. 3 OPTIMIZATIONS OF THE CURRENT ALGORITHM 3.1 Down-sampling Naturally, maintaing the weight matrix has large overhead, especially as the number of pixels increases. We can reduce memory consumption and increase speed by down-sampling the grid, allowing each cell to represent more than a single pixel. Down-sampling comes at the cost of accuracy, since the placement algorithm can only return coordinates on the granularity of the grid. This makes it impossible, for instance, to place an element at exactly (x,y) unless x mod CELL_SIZE and y mod CELL_SIZE are both equal to 0. It may also be possible to test placements without summing over the entire region, since we can assume some amount of continuity in the topology. In other words, we might check every other cell, or every 4th cell, to determine the weight of a given placement, W_p. This could drastically reduce the number of reads into the matrix. 3.2 Quad Trees Quad trees could be used in place of the table of weights. To conceptualize, we recursively divide the area into quads (each node in the tree has 4 children), and the weight of each node is calculated as the sum of the weights of its branches. I'm not entirely certain of the details of this algorithm, or how the boundary conditions are handled, but overall it's a relatively straightforward optimization of the grid algorithm. Placement is much faster, since we can quickly narrow in on the best branch to place in, and the overhead of maintaining a large matrix of values is overcome. 4 OTHER POSSIBLE ALGORITHMS 4.1 A pseudo-spring algorithm I'll spend little time describing this algorithm, as it's relatively simple. The basic concept is similar to the grid algorithm described above, sans grid. No record of the current configuration is retained. Instead, we find a potential placement location by trials, minimizing collisions. We then simply "push" any colliding elements away from the new element by an amount proportional to their sizes and in the direction of the angle between them. Without hacking up a simple version of this, it's hard to tell how well it will behave in practice. It's also unclear to me upon first glance how scaling and removal should be handled. 4.2 "Real" physics Using Box2D as an engine for the layout has been proposed. To do so, we need to determine what type of physical (and, of course, 2D) simulation will result in a system with the desired properties. The most obvious solution is to take advantage of a much faster and more accurate collision detection, adjusting the system to minimize overlap according to its own algorithms. This has the advantage of providing (I suspect) near-zero overlap among ALL elements (not just those colliding with the placed element), since it will recursively perform checks against all elements. However, this also means that it's likely to cause updates across the entire screen for nearly every operation when the screen is somewhat dense, which could have adverse effects on the animation of the elements into their assigned positions. Another alternative would include use of springs, electrically charged particles, or both, though I think these types of systems (which are often used in generating force directed graphs) tend to run on order n-cubed in the number of nodes (elements).