# Circle Packing

Simple algorithms for circle packing.

R package for circle packing.

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

The function `circleRepelLayout` attempts to arrange a set of circles of specified radii within a rectangle such that there is no-overlap between circles. The algorithm is adapted from an example written in Processing by Sean McCullough (which no longer seems to be available online). It involves iterative pair-repulsion, in which overlapping circles move away from each other. The distance moved by each circle is proportional to the radius of the other to approximate inertia (very loosely), so that when a small circle is overlapped by a large circle, the small circle moves furthest. This process is repeated iteratively until no more movement takes place (acceptable layout) or a maximum number of iterations is reached (layout failure). To avoid edge effects, the bounding rectangle is treated as a toroid. Each circle's centre is constrained to lie within the rectangle but its edges are allowed to extend outside.

The function `circleProgressiveLayout` arranges a set of circles, which are denoted by their sizes, by consecutively placing each circle externally tangent to two previously placed circles while avoiding overlaps. It was adapted from a version written in C by Peter Menzel. The underlying algorithm is described in the paper: Visualization of large hierarchical data by circle packing by Weixin Wang, Hui Wang, Guozhong Dai, and Hongan Wang. Published in Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, 2006, pp. 517-520. ACM.

The function `circleRemoveOverlaps` takes an initial set of overlapping circles and attempts to find a non-overlapping subset or, optionally, a subset with some specified degree of overlap. Circle positions remain fixed. It provides several fast heuristic algorithms to choose from, as well as two based on linear programming. For the latter, package lpSolve must be installed.

The function `circleGraphLayout` is an initial Rcpp port of an algorithm described by Collins 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 in the PADS library.

To install:

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

Share and enjoy!

# NEWS packcircles

Version 0.3.1 2018-01-09

• Fixed a problem where function circleProgressiveLayout sometimes returned a layout with overlapping circles. Thanks to Jeffrey Lewis for reporting and Peter Menzel for code changes.

Version 0.3.0 2017-11-24

• Added `circleRemoveOverlaps` which takes a set of circles and identifies a subset of non-overlapping circles. The function can also be set to allow some degree of overlap or require space between circles. The function uses either a fast heuristic algorithm (several choices) or linear programming (requires package lpSolve).

• Replaced use of `sprintf` with `snprintf` in `pads_circle_pack.cpp` (graph-based circle packing) to address CRAN warning.

Version 0.2.0 2017-04-05

• Added `circleProgressiveLayout` which deterministically places each circle in turn such that it is externally tangent to two previously placed circles while avoiding overlaps.

• Replaced `circleLayout` with a new function `circleRepelLayout`. The original function is retained for backwards compatibility but is deprecated and will be removed in a future release. Important note: the new function accepts circles sizes as either areas or radii. The default is area, unlike `circleLayout` which assumed sizes were radii. The type of size value can be specified using the `sizetype` argument.

• Replaced `circlePlotData` with a new function `circleLayoutVertices`. The original function is retained for backwards compatibility but is deprecated and will be removed in a future release. The new function has a `sizetype` argument to specify whether the input circle sizes are areas or radii. By default, radius is assumed as this matches the output of the layout functions but I realize it's a bit confusing.

• Removed `gridExtra` from suggested packages. Added `ggiraph` (used for vignette).

• Re-wrote the introductory vignette and added a new vignette for `circleProgressiveLayout`.

• Edited function docs and examples.

• Added file for native routine registration as now required by CRAN.

# Reference manual

install.packages("packcircles")

0.3.2 by Michael Bedward, 2 months ago

https://github.com/mbedward/packcircles

Report a bug at https://github.com/mbedward/packcircles/issues

Browse source code at https://github.com/cran/packcircles

Authors: Michael Bedward [aut, cre], David Eppstein [aut] (Author of Python code for graph-based circle packing ported to C++ for this package), Peter Menzel [aut] (Author of C code for progressive circle packing ported to C++ for this package)

Documentation:   PDF Manual