When I first blogged about force-based algorithms, my focus was firmly on charting and graphing; specifically, producing aesthetically-pleasing diagrams consisting of nodes and connectors. Force-based algorithms have many other applications in computer science, from graphics to simulations to problem-solving and beyond. In this post, i’m going to look at the application of a force-based algorithm to the task of arranging images in a tessellating pattern.

The forces in play

As with my force-directed diagram algorithm, this force-based algorithm requires at least two forces to be in play; if there is no opposing force, then the layout would either collapse or ‘fly away’ from the viewport. In this case, the dominant force is a pulling force that acts towards the middle of the screen; regardless of where an image tile is situated, it will be dragged towards the center point. In this way, the force is much like a localised gravitational field (although it does not strengthen as objects approach the point). The opposing force is that of collision; when one image tile would otherwise cross into the bounds of another, a reaction force is applied in the opposite direction (some of the energy is absorbed during the collision, making it only partially elastic).

Furthermore, when a collision occurs, image tiles are not permitted to overlap. Instead, one of three things will happen:

• The tile will slide against the horizontal edge of the colliding tile (towards the center)
• The tile will slide against the vertical edge of the colliding tile (towards the center)
• The tile will remain in its original position

The choice of action will be determined according to whether the tile’s path is unobstructed.

Together, these forces encourage the image tiles to reach a stable configuration, in which they are clustered together with minimal gaps between them.

The algorithm

LET center_screen represent the middle of the screen
LET damping represent the factor by which velocity decreases between iterations
LET absorbance represent the factor by which energy is absorbed during a collision

INITIALISE the each image tile with a random (or uniformly-distributed) placement

REPEAT
    FOR EACH image tile:
        LET net_force equal zero
        LET pulling_force act at the angle formed between the image tile and center_screen

        SET net_force = net_force + pulling_force
        SET velocity{i} = (velocity{i-1} * damping) + net_force
        SET position{i} = position{i-1} + velocity{i}

        IF a collision occurs
            LET reaction_force act at the angle formed between the colliding image tiles

            SET net_force = (net_force * absorbance) + reaction_force
            SET velocity{i} = (velocity{i-1} * damping) + net_force

            LET proposed_horizontal represent the coordinate (position{i}.x, position{i-1}.y)
            LET proposed_vertical represent the coordinate (position{i-1}.x, position{i}.y)

            IF proposed_horizontal collides with no other image tile
                SET position{i} = proposed_horizontal
            ELSE IF proposed_vertical collides with no other image tile
                SET position{i} = proposed_vertical
            ELSE
                SET position{i} = position{i-1}
            END IF
        END IF
    END FOR EACH
UNTIL (total displacement drops below threshold) OR (maximum iterations reached)

The force, velocity and position variables are represented using vectors. Collisions take into account the entire bounds of each tile (implemented using Rectangle.IntersectsWith() in .NET).

The initial placement of the image tiles is significant; they must be placed in such a manner that they do not overlap. The implementation offers two initial arrangement types; random (in which positions are completely randomised), or uniform (where image tiles are assigned to positions on a uniform grid).

The implementation

The algorithm is implemented in the ImageCollage class. Each instance of ImageCollage holds a collection of ImageInfo objects, which represent the image tiles.

ImageCollage:

• Images – Collection of ImageInfo objects.
• Arrange() – Runs the force-based algorithm.
• Distribute() – Responsible for the initial placement of image tiles.
• Render() – Renders the montage using the image files and resulting layout.

ImageInfo:

• Path – Path to the image file.
• OriginalWidth, OriginalHeight – Dimensions of the image, used to preserve the aspect ratio.
• Bounds – The bounds of the image tile (will change during layout).
• Velocity – The velocity of the image tile during the layout algorithm.
• RelativeSize – Controls the size of the image tile with respect to the others on the canvas.

The full implementation can be found on the project page for the Image Collage Generator, where I have developed a complete Windows Forms application around this concept.

The results

The implementation of the force-based algorithm for image tessellation appears to work well. It copes with small numbers of images as well as larger counts (150+ images) without significant degradation in performance or the quality of layout. Further enhancements would be required to cope with very large number of images (500+) – this algorithm was designed with fewer number of images in mind.

In general, uniform initialisation seems to produce fewer gaps than random initialisation; however, the random positioning tends to produce more organic-looking layouts. Depending on the variation in aspect ratio between the images used, one approach may produce better results than the other.

Final words

Be sure to check out the Image Collage Generator to see this force-based algorithm in action. Once again, the force-based approach lends itself well to a task which would otherwise require manual placement. Genetic algorithms may also be an alternative to the force-based approach; tessellation is a problem for which fitness criteria can be clearly evaluated – however, I would wager than a genetic algorithm would take longer to find a solution and would be more computationally-intensive than the force-based approach.

I hope you find this application of force-based algorithms useful. Perhaps you can think of other problems that could be solved in this manner?