circleRemoveOverlaps: Filters a set of circles to remove all overlaps

In packcircles: Circle Packing

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

x	A matrix or data frame containing circle x-y centre coordinates and sizes (area or radius).
xysizecols	The integer indices or names of the columns in x for the centre x-y coordinates and sizes of circles. Default is c(1,2,3).
sizetype	The type of size values: either "area" (default) or "radius". May be abbreviated.
tolerance	Controls the amount of overlap allowed. Set to 1 for simple exclusion of overlaps. Values lower than 1 allow more overlap. Values > 1 have the effect of expanding the influence of circles so that more space is required between them. The input value must be > 0.
method	Specifies whether to use linear programming (default) or one of the variants of the heuristic algorithm. Alternatives are: "maxov", "minov", "largest", "smallest", "random", "lparea", "lpnum". See Details for further explanation.

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 for rejection at each iteration:

maxov

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

minov

Choose one of the circle 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.

packcircles documentation built on Sept. 8, 2023, 5:55 p.m.