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:
install.packages("packcircles")
install_github("mbedward/packcircles")
Share and enjoy!
Version 0.3.1 2018-01-09
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.