packcircles: Simple algorithms for circle packing

Description

This package provides several algorithms to find non-overlapping arrangements of circles:

circleRepelLayout

Arranges circles within a bounding rectangle by pairwise repulsion.

circleProgressiveLayout

Arranges circles in an unbounded area by progressive placement. This is a very efficient algorithm that can handle large numbers of circles.

circleGraphLayout

Finds an arrangement of circles conforming to a graph specification.

Author(s)

Maintainer: Michael Bedward michael.bedward@gmail.com

Authors:

• David Eppstein david.eppstein@gmail.com (Author of Python code for graph-based circle packing ported to C++ for this package)

• Peter Menzel pmenzel@gmail.com (Author of C code for progressive circle packing ported to C++ for this package)

See Also

Useful links:

• https://github.com/mbedward/packcircles

• Report bugs at https://github.com/mbedward/packcircles/issues

Abundance of bacteria

Description

Names and abundances of bacterial taxa as measured in a study of biofilms.

Usage

bacteria

Format

## 'bacteria' A data frame with 167 rows and 3 columns:

value

measured abundance

colour

preferred colour for display

label

taxon name

Find an arrangement of circles satisfying a graph of adjacencies

Description

Attempts to derive an arrangement of circles satisfying prior conditions for size and adjacency. Unlike the circleRepelLayout function, this is a deterministic algorithm. Circles are classified as either internal or external. Viewing the pattern of adjacencies as a triangulated mesh, external circles are those on the boundary. In the version of the algorithm implemented here, the radii of external circles are provided as inputs, while the radii of internal circles are derived as part of the output arrangement.

Usage

circleGraphLayout(internal, external)

Arguments

Details

The internal argument specifies circle adjacencies (ie. tangencies). The format is an concise representation of graph edges, and consists of a list of vectors: one per internal circle. In each vector the first element is the ID value of the internal circle and the remaining values are IDs of neighbouring circles, which may be either internal or external.

The external argument is a data.frame which specifies the radii of external circles. Internal circle radii should not be specified as they are derived as part of the fitting algorithm. The function will issue an error if any internal circle IDs are present in the external data.

Value

A data.frame with columns for circle ID, centre X and Y ordinate, and radius.

The output arrangement as a data.frame with columns for circle ID, centre X and Y ordinates, and radius. For external circles the radius will equal input values.

Note

Please treat this function as experimental.

References

C.R. Collins & K. Stephenson (2003) An algorithm for circle packing. Computational Geometry Theory and Applications 25:233-256.

Examples

## Simple example with two internal circles surrounded by
## four external circles. Internal circle IDs are 1 and 2.
internal <- list( c(1, 3, 4, 5), c(2, 3, 4, 6) )

## Uniform radius for external circles
external <- data.frame(id=3:6, radius=1.0)

## Generate the circle packing
packing <- circleGraphLayout(internal, external)

Arranges circles by iterative pair-wise repulsion within a bounding rectangle

Description

This function is deprecated and will be removed in a future release. Please use circleRepelLayout instead.

Usage

circleLayout(xyr, xlim, ylim, maxiter = 1000, wrap = TRUE, weights = 1)

Arguments

Value

A list with components:

layout

A 3-column matrix or data.frame (centre x, centre y, radius).

niter

Number of iterations performed.

Note

This function assumes that circle sizes are expressed as radii whereas the default for circleRepelLayout is area.

See Also

circleRepelLayout

Generate a set of circle vertices suitable for plotting

Description

Given a matrix or data frame for a circle layout, with columns for centre X and Y coordinates and circle sizes, this function generates a data set of vertices which can then be used with ggplot or base graphics functions. If any of the size values in the input data are zero, negative or missing (NA or NULL), the corresponding circles will not be generated. This can be useful when displaying alternative subsets of circles.

Usage

circleLayoutVertices(
  layout,
  npoints = 25,
  xysizecols = 1:3,
  sizetype = c("radius", "area"),
  idcol = NULL
)

Arguments

Value

A data frame with columns: id, x, y; where id is the unique integer identifier for each circle. If no size values in the input layout data are positive, a data frame with zero rows will be returned.

Note

Input sizes are assumed to be radii. This is slightly confusing because the layout functions circleRepelLayout and circleProgressiveLayout treat their input sizes as areas by default. To be safe, you can always set the sizetype argument explicitly for both this function and layout functions.

See Also

circleVertices

Examples

xmax <- 100
ymax <- 100
rmin <- 10
rmax <- 20
N <- 20

## Random centre coordinates and radii
layout <- data.frame(id = 1:N,
                     x = runif(N, 0, xmax), 
                     y = runif(N, 0, ymax), 
                     radius = runif(N, rmin, rmax))

## Get data for circle vertices
verts <- circleLayoutVertices(layout, idcol=1, xysizecols=2:4,
                              sizetype = "radius")

## Not run: 
library(ggplot2)

## Draw circles annotated with their IDs
ggplot() + 
  geom_polygon(data = verts, aes(x, y, group = id), 
               fill = "grey90", 
               colour = "black") +
               
  geom_text(data = layout, aes(x, y, label = id)) + 
  
  coord_equal() +
  theme_bw()

## End(Not run)

Generate a set of circle vertices suitable for plotting

Description

This function is deprecated and will be removed in a future release. Please use circleLayoutVertices instead.

Usage

circlePlotData(layout, npoints = 25, xyr.cols = 1:3, id.col = NULL)

Arguments

Value

A data frame with columns: id, x, y; where id is the unique integer identifier for each circle.

See Also

circleLayoutVertices circleVertices

Progressive layout algorithm

Description

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.

Usage

circleProgressiveLayout(x, sizecol = 1, sizetype = c("area", "radius"))

Arguments

Details

Based on an algorithm 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 doi:10.1145/1124772.1124851

The implementation here was adapted from a version written in C by Peter Menzel: https://github.com/pmenzel/packCircles.

Value

A data frame with columns: x, y, radius. If any of the input size values were non-positive or missing, the corresponding rows of the output data frame will be filled with NAs.

Examples

areas <- sample(c(4, 16, 64), 100, rep = TRUE, prob = c(60, 30, 10))
packing <- circleProgressiveLayout(areas)

## Not run: 

# Graph the result with ggplot
library(ggplot2)

dat.gg <- circleLayoutVertices(packing)

ggplot(data = dat.gg, aes(x, y, group = id)) +
  geom_polygon(colour = "black", fill = "grey90") +
  coord_equal() +
  theme_void()


## End(Not run)

Filters a set of circles to remove all overlaps

Description

Given an initial set of circles, this function identifies a subset of non-overlapping circles using a simple heuristic algorithm. Circle positions remain fixed.

Usage

circleRemoveOverlaps(
  x,
  xysizecols = 1:3,
  sizetype = c("area", "radius"),
  tolerance = 1,
  method = c("maxov", "minov", "largest", "smallest", "random", "lparea", "lpnum")
)

Arguments

Details

The method argument specifies whether to use the heuristic algorithm or linear programming. The following options select the heuristic algorithm and specify how to choose an overlapping circle to remove at each iteration:

maxov

Choose one of the circles with the greatest number of overlaps.

minov

Choose one of the circles with the least number of overlaps.

largest

Choose one of the largest circles.

smallest

Choose one of the smallest circles.

random

Choose a circle at random.

At each iteration the number of overlaps is checked for each candidate circle and any non-overlapping circles added to the selected subset. Then a single overlapping circle is chosen, based on the method being used, from among the remainder and marked as rejected. Iterations continue until all circles have been either selected or rejected. The 'maxov' option (default) generally seems to perform best at maximizing the number of circles retained. The other options are provided for comparison and experiment. Beware that some can perform surprisingly poorly, especially 'minov'.

Two further options select linear programming:

lparea

Maximise the total area of circles in the subset.

lpnum

Maximise the total number of circles in the subset.

The 'lpSolve' package must be installed to use the linear programming options. These options will find an optimal subset, but for anything other than a small number of initial circles the running time can be prohibitive.

Value

A data frame with centre coordinates and radii of selected circles.

Note

This function is experimental and will almost certainly change before the next package release. In particular, it will probably return something other than a data frame.

Arranges circles by iterative pair-wise repulsion within a bounding rectangle

Description

This function takes a set of circles, defined by a data frame of initial centre positions and radii, and uses iterative pair-wise repulsion to try to find a non-overlapping arrangement where all circle centres lie inside a bounding rectangle. If no such arrangement can be found within the specified maximum number of iterations, the last attempt is returned.

Usage

circleRepelLayout(
  x,
  xlim,
  ylim,
  xysizecols = c(1, 2, 3),
  sizetype = c("area", "radius"),
  maxiter = 1000,
  wrap = TRUE,
  weights = 1
)

Arguments

Details

The algorithm is adapted from a demonstration app written in the Processing language by Sean McCullough (no longer available online). Each circle in the input data is compared to those following it. If two circles overlap, they are moved apart such that the distance moved by each is proportional to the radius of the other, loosely simulating inertia. So when a small circle is overlapped by a larger circle, the small circle moves furthest. This process is repeated until no more movement takes place (acceptable layout) or the maximum number of iterations is reached (layout failure).

To avoid edge effects, the bounding rectangle can be treated as a toroid by setting the wrap argument to TRUE. With this option, a circle moving outside the bounds re-enters at the opposite side.

Value

A list with components:

layout

A 3-column matrix or data frame (centre x, centre y, radius).

niter

Number of iterations performed.

Generate vertex coordinates for a circle

Description

Generates vertex coordinates for a circle given its centre coordinates and radius.

Usage

circleVertices(xc, yc, radius, npoints = 25)

Arguments

Value

A 2-column matrix of X and Y values. The final row is a copy of the first row to create a closed polygon, so the matrix has npoints + 1 rows.

See Also

circleLayoutVertices