Repository files navigation

R package for circle packing. Algorithms to find arrangements of non-overlapping circles

This package provides functions to find non-overlapping arrangements of circles.

The functioncircleRepelLayout attempts to arrange a set of circles of specifiedradii within a rectangle such that there is no-overlap between circles.The algorithm is adapted from an example written in Processing by SeanMcCullough (which no longer seems to be available online). It involvesiterative pair-repulsion, in which overlapping circles move away from eachother. The distance moved by each circle is proportional to the radius of theother to approximate inertia (very loosely), so that when a small circle isoverlapped by a large circle, the small circle moves furthest. This processis repeated iteratively until no more movement takes place (acceptablelayout) or a maximum number of iterations is reached (layout failure). Toavoid edge effects, the bounding rectangle is treated as a toroid. Eachcircle's centre is constrained to lie within the rectangle but its edges areallowed to extend outside.

The functioncircleProgressiveLayout arranges a set of circles, which aredenoted by their sizes, by consecutively placing each circle externally tangentto two previously placed circles while avoiding overlaps. It was adapted from aversion written in C by Peter Menzel.The underlying algorithm is described in the paper:Visualization of largehierarchical data by circle packing byWeixin Wang et al. (2006).

The functioncircleRemoveOverlaps takes an initial set of overlapping circlesand attempts to find a non-overlapping subset or, optionally, a subset with somespecified degree of overlap. Circle positions remain fixed. It provides severalfast heuristic algorithms to choose from, as well as two based on linearprogramming. For the latter, package lpSolve must be installed.

The functioncircleGraphLayout is an initial Rcpp port of an algorithm described byCollins and Stephenson (2003)to find an arrangement of circles which corresponds to a graph of desired circle tangencies.The implementation is based on a Python version by David Eppstein (see CirclePack.py inthePADS library.

To install:

• the latest released version:install.packages("packcircles")
• the latest development version (usually the same):remotes::install_github("mbedward/packcircles")

See also:

Theggcirclepack packagewhich makes it easier to add circles created with at least one of thepackcirclesfunctions to ggplot2 graphs.

Share and enjoy!