Package micycle.pgs

Class PGS_CirclePacking

java.lang.Object
micycle.pgs.PGS_CirclePacking
public final class PGS_CirclePacking extends Object
Circle packings of shapes, subject to varying constraints and patterns of tangencies.

Each method produces a circle packing with different characteristics using a different technique; for this reason input arguments vary across the methods.

The output of each method is a list of PVectors, each representing one circle: (.x, .y) represent the center point and .z represents radius.

Where applicable, packings will include circles that overlap with the shape, rather than only including those circles whose center point lies inside the shape.

Since:
1.1.0
Author:
Michael Carleton

  • Method Summary

    Modifier and Type
    Method
    Description
    static List<processing.core.PVector>
    frontChainPack(processing.core.PShape shape, double radiusMin, double radiusMax)
    Generates a random circle packing of tangential circles with varying radii that overlap the given shape.
    static List<processing.core.PVector>
    frontChainPack(processing.core.PShape shape, double radiusMin, double radiusMax, long seed)
    Generates a random circle packing of tangential circles with varying radii that overlap the given shape.
    static List<processing.core.PVector>
    hexLatticePack(processing.core.PShape shape, double diameter)
    Generates a tiled circle packing consisting of equal-sized circles arranged in a hexagonal lattice bounded by the input shape.
    static List<processing.core.PVector>
    maximumInscribedPack(processing.core.PShape shape, double minRadius, double tolerance)
    Packs maximum inscribed circles within the given shape using the Largest Empty Circle (LEC) algorithm.
    static List<processing.core.PVector>
    maximumInscribedPack(processing.core.PShape shape, int n, double tolerance)
    Packs a specified number of maximum inscribed circles within the given shape using the Largest Empty Circle (LEC) algorithm.
    static List<processing.core.PVector>
    obstaclePack(processing.core.PShape shape, Collection<processing.core.PVector> pointObstacles, double areaCoverRatio)
    Packs circles of varying radii within a given shape, whilst respecting pointal obstacles using the Largest Empty Circle (LEC) algorithm.
    static List<processing.core.PVector>
    repulsionPack(processing.core.PShape shape, double radiusMin, double radiusMax, long seed)
    Generates a random circle packing of circles with varying radii that overlap the given shape.
    static List<processing.core.PVector>
    repulsionPack(processing.core.PShape shape, List<processing.core.PVector> circles)
    Generates a circle packing of a shape using a given collection of (overlapping) circles.
    static List<processing.core.PVector>
    squareLatticePack(processing.core.PShape shape, double diameter)
    Generates a tiled circle packing consisting of equal-sized circles arranged in a square lattice (or grid) bounded by the input shape.
    static List<processing.core.PVector>
    stochasticPack(processing.core.PShape shape, int points, double minRadius, boolean triangulatePoints)
    Generates a random circle packing of the input shape by generating random points one-by-one and calculating the maximum radius a circle at each point can have (such that it's tangent to its nearest circle or a shape vertex).
    static List<processing.core.PVector>
    stochasticPack(processing.core.PShape shape, int points, double minRadius, boolean triangulatePoints, long seed)
    Generates a seeded random circle packing within the input shape.
    static List<processing.core.PVector>
    tangencyPack(org.tinfour.common.IIncrementalTin triangulation, double boundaryRadii)
    Generates a circle packing having a pattern of tangencies specified by a triangulation.
    static List<processing.core.PVector>
    tangencyPack(org.tinfour.common.IIncrementalTin triangulation, double[] boundaryRadii)
    Generates a circle packing having a pattern of tangencies specified by a triangulation.
    static List<processing.core.PVector>
    trinscribedPack(processing.core.PShape shape, int points, int refinements)
    Generates a circle packing of the input shape, using the inscribed circles (or incircles) of triangles from a triangulation of the shape.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Method Details

    • obstaclePack

      public static List<processing.core.PVector> obstaclePack(processing.core.PShape shape, Collection<processing.core.PVector> pointObstacles, double areaCoverRatio)
      Packs circles of varying radii within a given shape, whilst respecting pointal obstacles using the Largest Empty Circle (LEC) algorithm. The method continues to generate circles until the sum of the areas of the circles exceeds a specified proportion of the area of the given shape.
      Parameters:
      shape - The shape within which circles will be packed. The shape should be in the form of PShape.
      pointObstacles - A collection of PVector points representing obstacles, around which circles are packed. Only points contained within the shape are relevant.
      areaCoverRatio - The target ratio of the total area of the circles to the area of the shape. This parameter should be a double between 0 and 1. Circle generation will stop when this ratio is reached.
      Returns:
      A list of PVectors, where each PVector represents a circle. The x and y components of the PVector represent the center of the circle, and the z component represents the radius of the circle.
      Since:
      1.4.0

    • trinscribedPack

      public static List<processing.core.PVector> trinscribedPack(processing.core.PShape shape, int points, int refinements)
      Generates a circle packing of the input shape, using the inscribed circles (or incircles) of triangles from a triangulation of the shape.

      Circles in this packing do not overlap and are contained entirely within the shape. However, not every circle is necessarily tangent to others.

      Parameters:
      shape - the shape from which to generate a circle packing
      points - the number of random points to insert into the triangulation as steiner points. Larger values lead to more circles that are generally smaller.
      refinements - number of times to refine the underlying triangulation. Larger values lead to more circles that are more regularly spaced and sized. 0...3 is a suitable range for this parameter
      Returns:
      A list of PVectors, each representing one circle: (.x, .y) represent the center point and .z represents radius.

    • stochasticPack

      public static List<processing.core.PVector> stochasticPack(processing.core.PShape shape, int points, double minRadius, boolean triangulatePoints)
      Generates a random circle packing of the input shape by generating random points one-by-one and calculating the maximum radius a circle at each point can have (such that it's tangent to its nearest circle or a shape vertex).

      Notably, the points argument defines the number of random point attempts (or circle attempts), and not the number of circles in the final packing output, since a point is rejected if it lies in an existing circle or whose nearest circle is less than minRadius distance away. In other words, points defines the maximum number of circles the packing can have; in practice, the packing will contain somewhat fewer circles.

      Circles in this packing do not overlap and are contained entirely within the shape. However, not every circle is necessarily tangent to other circles (in which case, such a circle will be tangent to a shape vertex).

      Parameters:
      shape - the shape from which to generate a circle packing
      points - number of random points to generate (this is not the number of circles in the packing).
      minRadius - filter (however not simply applied at the end, so affects how the packing operates during packing)
      triangulatePoints - when true, triangulates an initial random point set and uses triangle centroids as the random point set instead; this results in a packing that covers the shape more evenly (particularly when points is small), which is sometimes desirable
      Returns:
      A list of PVectors, each representing one circle: (.x, .y) represent the center point and .z represents radius.

    • stochasticPack

      public static List<processing.core.PVector> stochasticPack(processing.core.PShape shape, int points, double minRadius, boolean triangulatePoints, long seed)
      Generates a seeded random circle packing within the input shape. Circles are created one-by-one by generating random points and calculating the maximum possible radius for a circle at each point, ensuring it is tangent to its nearest circle or shape vertex.

      The points parameter defines the number of random point attempts (or circle attempts), but not the exact number of circles in the final packing output. An attempted point is rejected if it lies within an existing circle or if its nearest circle is less than minRadius distance away.

      Thus, points defines the maximum number of circles the packing can have; in practice, the packing will contain somewhat fewer circles.

      The generated circles in the packing do not overlap and are contained entirely within the shape. However, not every circle is necessarily tangent to other circles; such circles will be tangent to a shape vertex.

      Parameters:
      shape - the shape within which to generate the circle packing
      points - number of random points to generate (not necessarily equal to the number of circles in the packing)
      minRadius - minimum allowed radius for circles in the packing (affects packing generation, not applied as a filter at the end)
      triangulatePoints - when true, triangulates the initial random point set and uses triangle centroids as the random point set instead; results in a more evenly distributed packing (particularly when the number of points is small), which may be desirable
      seed - random seed used to initialize the underlying random number generator
      Returns:
      A list of PVectors, each representing one circle: (.x, .y) represent the center point, and .z represents the radius.

    • frontChainPack

      public static List<processing.core.PVector> frontChainPack(processing.core.PShape shape, double radiusMin, double radiusMax)
      Generates a random circle packing of tangential circles with varying radii that overlap the given shape. The method name references the packing algorithm used (Front Chain Packing), rather than any particular characteristic of the circle packing.

      You can set radiusMin equal to radiusMax for a packing of equal-sized circles using this approach.

      Parameters:
      shape - the shape within which to generate the circle packing
      radiusMin - minimum radius of circles in the packing
      radiusMax - maximum radius of circles in the packing
      Returns:
      A list of PVectors, each representing one circle: (.x, .y) represent the center point and .z represents radius.

    • frontChainPack

      public static List<processing.core.PVector> frontChainPack(processing.core.PShape shape, double radiusMin, double radiusMax, long seed)
      Generates a random circle packing of tangential circles with varying radii that overlap the given shape. The method name references the packing algorithm used (Front Chain Packing), rather than any particular characteristic of the circle packing.

      You can set radiusMin equal to radiusMax for a packing of equal-sized circles using this approach.

      Parameters:
      shape - the shape within which to generate the circle packing
      radiusMin - minimum radius of circles in the packing
      radiusMax - maximum radius of circles in the packing
      seed - random seed used to initialize the underlying random number generator
      Returns:
      A list of PVectors, each representing one circle: (.x, .y) represent the center point and .z represents radius.

    • maximumInscribedPack

      public static List<processing.core.PVector> maximumInscribedPack(processing.core.PShape shape, int n, double tolerance)
      Packs a specified number of maximum inscribed circles within the given shape using the Largest Empty Circle (LEC) algorithm.

      This method finds and returns the maximum inscribed circles up to the specified number (n), starting with the largest circle. It uses a tolerance value to control the accuracy of the LEC algorithm.

      Parameters:
      shape - The input shape to pack maximum inscribed circles within.
      n - The number of maximum inscribed circles to find and pack.
      tolerance - The tolerance value to control the LEC algorithm's accuracy. Higher values yield faster results but lower accuracy. A value of a 1 is good staring point.
      Returns:
      A list of PVector objects representing the centers (.x, .y) and radii (.z) of the maximum inscribed circles.

    • maximumInscribedPack

      public static List<processing.core.PVector> maximumInscribedPack(processing.core.PShape shape, double minRadius, double tolerance)
      Packs maximum inscribed circles within the given shape using the Largest Empty Circle (LEC) algorithm.

      This method finds and returns the maximum inscribed circles with a radius equal to or larger than the specified minimum radius. It uses a tolerance value to control the accuracy of the LEC algorithm.

      Parameters:
      shape - The input shape to pack maximum inscribed circles within.
      minRadius - The minimum allowed radius for the inscribed circles.
      tolerance - The tolerance value to control the LEC algorithm's accuracy. Higher values yield faster results but lower accuracy. A value of a 1 is good staring point.
      Returns:
      A list of PVector objects representing the centers (.x, .y) and radii (.z) of the maximum inscribed circles.

    • tangencyPack

      public static List<processing.core.PVector> tangencyPack(org.tinfour.common.IIncrementalTin triangulation, double boundaryRadii)
      Generates a circle packing having a pattern of tangencies specified by a triangulation.

      This is an implementation of 'A circle packing algorithm' by Charles R. Collins & Kenneth Stephenson.

      Parameters:
      triangulation - represents the pattern of tangencies; vertices connected by an edge inthe triangulation represent tangent circles in thepacking
      boundaryRadii - radius of every circle associated with the boundary/perimeter vertices of the triangulation
      Returns:
      A list of PVectors, each representing one circle: (.x, .y) represent the center point and .z represents radius.

    • tangencyPack

      public static List<processing.core.PVector> tangencyPack(org.tinfour.common.IIncrementalTin triangulation, double[] boundaryRadii)
      Generates a circle packing having a pattern of tangencies specified by a triangulation.

      This is an implementation of 'A circle packing algorithm' by Charles R. Collins & Kenneth Stephenson.

      Parameters:
      triangulation - represents the pattern of tangencies; vertices connected by an edge inthe triangulation represent tangent circles in the packing
      boundaryRadii - list of radii of circles associated with the boundary/perimeter vertices of the triangulation. The list may have fewer radii than the number of boundary vertices; in this case, boundary radii will wrap around the list
      Returns:
      A list of PVectors, each representing one circle: (.x, .y) represent the center point and .z represents radius. The packing is centered on (0, 0) by default.
      Since:
      1.3.0

    • repulsionPack

      public static List<processing.core.PVector> repulsionPack(processing.core.PShape shape, double radiusMin, double radiusMax, long seed)
      Generates a random circle packing of circles with varying radii that overlap the given shape.

      Repulsion-packing involves iterative pair-repulsion, in which overlapping circles move away from each other until there is no overlap. A packing is first computed for the envelope of the shape, and then any circles which do not overlap with the shape are discarded.

      Parameters:
      shape - the shape from which to generate a circle packing
      radiusMin - minimum radius of circles in the packing. the radii parameters can be the same.
      radiusMax - maximum radius of circles in the packing. the radii parameters can be the same.
      seed - for initial circle positions and radii
      Returns:
      A list of PVectors, each representing one circle: (.x, .y) represent the center point and .z represents radius.
      Since:
      1.3.0
      See Also:

    • repulsionPack

      public static List<processing.core.PVector> repulsionPack(processing.core.PShape shape, List<processing.core.PVector> circles)
      Generates a circle packing of a shape using a given collection of (overlapping) circles.

      Circles in the input should be already bounded by the shape (since repulsion does not push lonely circles towards the shape, but only repulses overlapping circles); the intended input is one having circles with lots of overlap (perhaps seeded within a small rectangle), where they may be repulsed from each other to fill the shape.

      Repulsion-packing involves iterative pair-repulsion, in which overlapping circles move away from each other until there is no overlap. A packing is first computed for the envelope of the shape, and then any circles which do not overlap with the shape are discarded.

      Parameters:
      shape - the shape from which to generate a circle packing
      circles - the collection of circles to pack the shape with, specified as PVectors, where .z is the radius (>=1) for each circle
      Returns:
      A list of PVectors, each representing one circle: (.x, .y) represent the center point and .z represents radius.
      Since:
      1.3.0
      See Also:

    • squareLatticePack

      public static List<processing.core.PVector> squareLatticePack(processing.core.PShape shape, double diameter)
      Generates a tiled circle packing consisting of equal-sized circles arranged in a square lattice (or grid) bounded by the input shape.

      Circles are included in the packing if they overlap with the given shape.

      Parameters:
      shape - the shape from which to generate a circle packing
      diameter - diameter of every circle in the packing
      Returns:
      A list of PVectors, each representing one circle: (.x, .y) represent the center point and .z represents radius.
      See Also:

    • hexLatticePack

      public static List<processing.core.PVector> hexLatticePack(processing.core.PShape shape, double diameter)
      Generates a tiled circle packing consisting of equal-sized circles arranged in a hexagonal lattice bounded by the input shape.

      Circles are included in the packing if they overlap with the given shape.

      Parameters:
      shape - the shape from which to generate a circle packing
      diameter - diameter of every circle in the packing
      Returns:
      A list of PVectors, each representing one circle: (.x, .y) represent the center point and .z represents radius.
      See Also: