Skip to main content

Circle packing algorithm for Python

Project description

PyPi version Python compatibility GitHub Workflow Status (branch) Codecov

circlify

Pure Python implementation of a circle packing layout algorithm, inspired by d3js and squarify.

Circles are first arranged with a euristic inspired by the A1.0 of [Huang-2006], then enclosed in a circle created around them using [MSW-1996] algorithm used in [Bostock-2017]. I hope to implement A1.5 at some point in the future but the results are good enough for my use case.

Installation

Using pip:

pip install circlify

or using the source:

git clone git://github.com/elmotec/circlify.git
cd circlify
python setup.py install

The last step may require sudo if you don’t have root access.

Usage

The main function circlify is supported by a small data class circlify.Circle and takes 3 parameters:

  • A list of positive values sorted from largest to smallest.

  • (optional) A target enclosure where the packed circles should fit. It defaults to the unit circle (0, 0, 1).

  • (optional) A boolean indicating if the target enclosure should be appended to the output.

The function returns a list of circlify.Circle whose area is proportional to the corresponding input value.

Example

>>> from pprint import pprint as pp
>>> import circlify as circ
>>> circles = circ.circlify([19, 17, 13, 11, 7, 5, 3, 2, 1], show_enclosure=True)
>>> pp(circles)
[Circle(x=0.0, y=0.0, r=1.0, level=0, ex=None),
 Circle(x=-0.633232604611031, y=-0.47732413442115296, r=0.09460444572843042, level=1, ex={'datum': 1}),
 Circle(x=-0.7720311587589236, y=0.19946176418549022, r=0.13379089020993573, level=1, ex={'datum': 2}),
 Circle(x=-0.43168871955473165, y=-0.6391381648617572, r=0.16385970662353394, level=1, ex={'datum': 3}),
 Circle(x=0.595447603036083, y=0.5168251295666467, r=0.21154197162246005, level=1, ex={'datum': 5}),
 Circle(x=-0.5480911056188739, y=0.5115139053491098, r=0.2502998363185337, level=1, ex={'datum': 7}),
 Circle(x=0.043747233552068686, y=-0.6848366902134195, r=0.31376744998074435, level=1, ex={'datum': 11}),
 Circle(x=0.04298737651230445, y=0.5310431146935967, r=0.34110117996070605, level=1, ex={'datum': 13}),
 Circle(x=-0.3375943908160698, y=-0.09326467617622711, r=0.39006412239133215, level=1, ex={'datum': 17}),
 Circle(x=0.46484095011516874, y=-0.09326467617622711, r=0.4123712185399064, level=1, ex={'datum': 19})]

A simple matplotlib representation. See circlify.bubbles helper function (requires matplotlib):

visualization of circlify circle packing of first 9 prime numbers.

Hierarchical circle packing

Starting with version 0.10, circlify also handle hierarchical input so that:

>>> from pprint import pprint as pp
>>> import circlify as circ
>>> data = [
        0.05, {'id': 'a2', 'datum': 0.05},
        {'id': 'a0', 'datum': 0.8, 'children': [0.3, 0.2, 0.2, 0.1], },
        {'id': 'a1', 'datum': 0.1, 'children': [
            {'id': 'a1_1', 'datum': 0.05}, {'datum': 0.04}, 0.01],
        },
    ]
>>> circles = circ.circlify(data, show_enclosure=True)
>>> pp(circles)
[Circle(x=0.0, y=0.0, r=1.0, level=0, ex=None),
 Circle(x=-0.5658030759977484, y=0.4109778665114514, r=0.18469903125906464, level=1, ex={'datum': 0.05}),
 Circle(x=-0.5658030759977484, y=-0.4109778665114514, r=0.18469903125906464, level=1, ex={'id': 'a2', 'datum': 0.05}),
 Circle(x=-0.7387961250362587, y=0.0, r=0.2612038749637415, level=1, ex={'id': 'a1', 'datum': 0.1, 'children': [{'id': 'a1_1', 'datum': 0.05}, {'datum': 0.04}, 0.01]}),
 Circle(x=0.2612038749637414, y=0.0, r=0.7387961250362586, level=1, ex={'id': 'a0', 'datum': 0.8, 'children': [0.3, 0.2, 0.2, 0.1]}),
 Circle(x=-0.7567888163564135, y=0.1408782365133844, r=0.0616618704777984, level=2, ex={'datum': 0.01}),
 Circle(x=-0.8766762590444033, y=0.0, r=0.1233237409555968, level=2, ex={'datum': 0.04}),
 Circle(x=-0.6154723840806618, y=0.0, r=0.13788013400814464, level=2, ex={'id': 'a1_1', 'datum': 0.05}),
 Circle(x=0.6664952237042414, y=0.33692908734605553, r=0.21174557028487648, level=2, ex={'datum': 0.1}),
 Circle(x=-0.1128831469183017, y=-0.23039288135707192, r=0.29945345726929773, level=2, ex={'datum': 0.2}),
 Circle(x=0.1563193680487183, y=0.304601976765483, r=0.29945345726929773, level=2, ex={'datum': 0.2}),
 Circle(x=0.5533243963620487, y=-0.23039288135707192, r=0.3667540860110527, level=2, ex={'datum': 0.3})]

A simple matplotlib representation. See circlify.bubbles helper function (requires matplotlib):

visualization of circlify nested circle packing for a hierarchical input.

Relative size of circles in hierachy

The area of the circles are proportional to the values passed in input only if the circles are at the same hierarchical level. For instance: circles a1_1 and a2 both have a value of 0.05, yet a1_1 is smaller than a2 because a1_1 is fitted within its parent circle a1 one level below the level of a2. In other words, the level 1 circles a1 and a2 are both proportional to their respective values but a1_1 is proportional to the values on level 2 witin a1.

Invalid input

A warning is issued if a key is not understood. The check is disabled if the program is running with -O or -OO option. One can also disable the warning with the regular logging filters.

For instance:

>>> import logging
>>> import sys
>>> import circlify as circ
>>> data = [ 0.05, {'id': 'a2', 'datum': 0.05, "bogus": {}}]
>>> logging.getLogger().addHandler(logging.StreamHandler(sys.stdout))
>>> _ = circ.circlify(data)
unexpected 'bogus' in input is ignored  # not issued if __debug__ is false
[Huang-2006]

WenQi HUANG, Yu LI, ChuMin LI, RuChu XU, New Heuristics for Packing Unequal Circles into a Circular Container, https://home.mis.u-picardie.fr/~cli/Publis/circle.pdf

[MSW-1996]
  1. Matoušek, M. Sharir, and E. Welzl. A Subexponential Bound For Linear Programming. Algorithmica, 16(4/5):498–516, October/November 1996, http://www.inf.ethz.ch/personal/emo/PublFiles/SubexLinProg_ALG16_96.pdf

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

circlify-0.15.0.tar.gz (11.6 kB view hashes)

Uploaded source

Built Distribution

circlify-0.15.0-py2.py3-none-any.whl (11.4 kB view hashes)

Uploaded py2 py3

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Huawei Huawei PSF Sponsor Microsoft Microsoft PSF Sponsor NVIDIA NVIDIA PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page