Problem Description
The project consists in the implementation of a function to display a set of graphics in the most compact way, while respecting some given priorities between them. The idea is that this function might be useful especially in the development of web pages, to display images in a limited area.
Priority constraints are used to specify if some images have to be displayed before any others and can be stated in several different ways: as numeric scores or as pair-wise constraints, associated to every image or just to few of them.
As the problem is very wide, we decided to set some bounds. First of all the user must provide a maximum width for the enclosing rectangle that will contain all the graphics objects, moreover the function will work only with images, at least in its first version. Nevertheless, we wanted the algorithm to still be valid for any graphics. Because of that we tried to do as least assumptions as possible on the data that the function takes as input. For example, the algorithm does not allow input scaling/cropping as those operations, though very useful in images visualization, can compromise plots visualization.
In the current implementation the function takes as input three arguments: a list of images, a set of constraints between them and the maximum width allowed for the final packing; plus few options to customize the final output (like image padding, background color..). As output, the function returns a Graphics object that contains all input images, horizontally ordered to respect given priority constraints. The total area of the enclosing rectangle is the minimum area that avoids images overlappings and constraints violations, however there are no optimality guarantees so it might exist a smaller enclosing rectangle than the one returned by the function for a certain given input.
The algorithm is designed to address the problem in two consecuitve steps:
- solve the one dimensional version of the problem, that is process priority constraints and find all possibile orderings of images that do not violate any constraint
- use the solution from the previous step to solve the two dimensional version of the problem. In the 2D version the algorithm takes into account also images dimensions, not only priorirty contraints, and tries to find a way to pack them in the minimum area enclosing rectangle.
1D PROBLEM: priority constraints management
In the one dimensional version of the general problem only priority constraints are taken into account. As mentioned earlier, constraints can be stated in several different forms:
- compatibility graph: a DirectedEdge connects two images A -> B if A must be displayed before image B in the final output
- list of pairs of images:{ {imgA ,imgB } , ...} that is interpreted as a list of edges of a compatibility graph
- scores: { imgA->4.5, imgB ->98} the higher the score, the higher the priority
Every type of constraint can involve all input images or concern only part of them. Nevertheless constraints usually do not define a total order for the input images, but rather some partially ordered sets (POSETs). So, the first step of the algorithm is the creation of POSETs, starting from the lists of images and constraints.
Direct Acyclic Graph (DAG) construction
In the case of constraints stated using a compatibility graph (or a list of pairs of images) it is important to check if there are infeasible constraints, that is if the graph contains any loop. If loops are detected the function silently deals with them instead of returning some error message. Loops are broken one by one using an iterative procedure. In particular, for every edge in the graph we count the number of loops it is part of and we cut off from the graph the edge that appears in the most cycles. In that way we hope to break more than one loop at a time, thus speeding up the computation. The procedure is iterated until there are no more loops and the final graph is actually a Direct Acyclic Graph (DAG).
How to derive a partial / total order from the constraints
Starting from a DAG we want to order images in a way that satisfies all the constraints. In that sense, the key idea is that every Hamiltonian path on the graph is a valid order of images. Unfortunately the DAG might not be connected and thus it might be impossible to find such path. Nevertheless it is always possible to group vertices into sets, that can be used to automatically create permutations of vertices that respect also the priority constraints.
Starting from a DAG we want to order images in a way that satisfies all the constraints. In that sense, the key idea is that every Hamiltonian path on the graph is a valid order of images. Unfortunately the DAG might not be connected and thus it might be impossible to find such path. Nevertheless it is always possible to group vertices into sets, that can be used to automatically create permutations of vertices that respect also the priority constraints.
Scores processing
If constraints are provided as scores we apply the following policy: score equal to zero means no priority constraint has been given for that image, so it can be placed wherever in the final ordering, while images having scores greater than zero must be poisitioned in the final ordering so that every image that follows has a lower score. Scores are scaled in the discrete interval {0,..,10} and images are grouped into the same set if they have the same score after the scaling.
2D PROBLEM: encapsulate images in the minimum area enclosing rectangle
The two dimensional version of the problem is just using the POSETs to find the minimum area enclosing rectangle that contains all the images and respects both priority and maximum width constraints. Without the constraints, this problem can be considered as an instance of a rectangle packing problem. The rectangle packing problem is an NP-Hard problem, which means that it does not exist a polynomial algorithm to solve it.
An optimal algorithm to solve the 2D problem
Even if it is an NP-Hard problem it is possible to find an optimal solution, though it will take longer than settling for a greedy solution. An optimal algorithm is the one linked in the references. Its basic idea is to start from an enclosing rectangle of infinite width and iteratively reduce its dimensions until the minimum area enclosing rectangle is found. The algorithm though is quite complex and its convergence rate most likely is quite slow, even if it can be improved using some hacks.
The greedy algorithm
The algorithm implemented by smartGraphicsGrid function is not optimal, anyway I think it represents a good trade-off between performances and quality of the solution. A lower bound to the quality of the returned greedy solution can be computed as: Total[MapThread[Times[#1,#2]&,{imagesWidths,imagesHeights}]]; that is the sum of the areas of all images. This lower bound is computed without taking into account any constraint so it is not very thigh to the optimal solution, nevertheless it provides a fast and easy to compute estimate of the output quality.
Here is the pseudo code of how the greedy algorithm works:
- compute the POSETs
- Organize images in rows inside the enclosing rectangle:
- select the next group of images that can be positioned in the enclosing rectangle and that does not violate any constraint (use the POSETs to find it out)
- among those images select only those that can fit in the free space of the current row, that is if imageWidth <=( rowWidth - Total[ widths[[imagesInRow]] ]); if no image fits then start a new line
- randomly pick one among the images that best fit in the free space
- repeat until all images have been positioned After that the final packing has been computed, a sequence of steps are performed in order to make the result more appealing. In the original packing all images are grouped on the top left corner of the enclosing rectangles. While after the final steps images are centered in each row width and height.
Options provided
By default images are packed without any space between them, anyway the user might set the "Padding" and the "PaddingColor" options to create a frame of a specific dimension and color around all images. Another option that will be implemented soon is the possibility to change the default background color of the enclosing rectangle.
Conclusions
The function smartGraphicsGrid is able to compute a good packing of a set of images, given a group of partial order constraints between them. Currently the algorithm is not able to find the optimal solution of the problem, though the approximation is quite good, and its implementation only support images. However the algorithm has been designed to work with any type of graphics, so in the future it will be possible to extend the input types supported by the function.
Future improvements
- implement a user interface that allows the user to make the compatibility graph by clicking on pairs of images consecutively
- support dynamic rearrangement of images if the user moves or scale one of them in the final output
- change the algorithm so that it works with lists/associations based on images rather than on indexes of images in the input list
- change the code so that the function supports every graphics object
OUTPUT EXAMPLE
Enclosing rectangle: 1680.x2538. MAX WIDTH:1700
28.3088% bigger than the minimum enclosing rectangle (if no constraints)
