org.jorlib.alg.packing.circlePacking

Class SmallestEnclosingCircleCalculator

java.lang.Object

org.jorlib.alg.packing.circlePacking.SmallestEnclosingCircleCalculator

public class SmallestEnclosingCircleCalculator
extends Object

For a given set of circles C, this class calculates the smallest enclosing circle which encloses all the circles in set C. The circles in C can have varying radii. To emphasize, this class does *NOT* perform circle packing. It merely computes the smallest enclosing circle around a set of circles which have already been fixed.

The implementation of this class is based on:
"A randomized incremental algorithm" in:
Xu, S. Freund, R.M. Sun, J. Solution methodologies for the Smallest Enclosing Circle Problem.
Computational Optimization and Applications, volumne 25, issue 1-3, pp283-292, 2003

Calculating the exact size of the smallest enclosing circle can be computationally expensive. This class also offers an approximation of this value. The approximated radius is guaranteed to be larger or equal to the exact radius. The tighter the circles are packed, the more accurate the approximation becomes.

Examples for circle packing are given here:

• http://mathworld.wolfram.com/CirclePacking.html
• http://en.wikipedia.org/wiki/Circle_packing_in_a_circle
• http://www.packomania.com/

Note from the author: In the aforementioned paper by Xu et. al several methods are compared. The authors report to obtain their best results with their Quadratic programming approach, but we obtained better results with their 'Randomized incremental algorithm'. Further experimenting may be required to determine the fastest method.

To limit the impact caused by rounding issues, this class uses BigDecimals for added precision.

Since:

April 8, 2015

Author:

Joris Kinable

Field Summary

Fields

Modifier and Type	Field and Description
static boolean	DEBUG
static double	PRECISION Precision parameter
static boolean	VALIDATORS_ENABLED

Constructor Summary

Constructors

Constructor and Description
SmallestEnclosingCircleCalculator()

Method Summary

Modifier and Type	Method and Description
void	calcExactContainer(double[] xCors, double[] yCors, double[] radii) Given a set of circles identified by their x-coordinates, y-coordinates and radii, this method calculates the smallest enclosing circle which encloses all the circles provided.
void	calculateApproximateContainer(double[] xCors, double[] yCors, double[] radii) Given a set of circles identified by their x-coordinates, y-coordinates and radii, this method *approximates* the smallest enclosing circle which encloses all the circles provided.
double[]	getContainerPosition() Get the x and y coordinates of the center of the enclosing circle
Point2D	getContainerPositionAsPoint() Get the x and y coordinates of the center of the enclosing circle
double	getRadius() Get the radius of the enclosing circle
void	incrementalCalcContainer(int posCircleToAdd, double[] xCors, double[] yCors, double[] radii, double xCorContainer, double yCorContainer, double radiusContainer) Given are a set of old circles, a circular container which encloses these circles and a new circle.

Methods inherited from class java.lang.Object

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

Field Detail

VALIDATORS_ENABLED

public static final boolean VALIDATORS_ENABLED

See Also:

Constant Field Values

DEBUG

public static final boolean DEBUG

See Also:

Constant Field Values

PRECISION

public static final double PRECISION

Precision parameter

See Also:

Constant Field Values

Constructor Detail

SmallestEnclosingCircleCalculator

public SmallestEnclosingCircleCalculator()

Method Detail

calculateApproximateContainer

public void calculateApproximateContainer(double[] xCors,
                                          double[] yCors,
                                          double[] radii)

Given a set of circles identified by their x-coordinates, y-coordinates and radii, this method *approximates* the smallest enclosing circle which encloses all the circles provided. The circles may overlap and can be of any size. The approximation is calculated as follows. Let N be the number of circles, x_i, y_i, r_i resp the x coordinate, y coordinate, and radius of circles i.

xAVG=\frac{\sum_i x_i}{N}
yAVG=\frac{\sum_i y_i}{N}

R=max_i \sqrt((xAVG-x_i)^2+(yAVG-y_i)^2)+r_i

The container will have its center at (xAVG,yAVG) and has radius R. The denser the packing of the circles, the more accurate the approximation of the container will be. This method is computationally cheap, fast and accurate. The approximated radius is guaranteed to be larger or equal to the exact radius.

Parameters:

xCors - x-coordinates of the circles to be enclosed (can be positive and negative values)

yCors - y-coordinates of the circles to be enclosed (can be positive and negative values)

radii - radii of the circles to be enclosed (must be strictly positive, circles can be of any size)

calcExactContainer

public void calcExactContainer(double[] xCors,
                               double[] yCors,
                               double[] radii)

Given a set of circles identified by their x-coordinates, y-coordinates and radii, this method calculates the smallest enclosing circle which encloses all the circles provided. The circles may overlap and can be of any size.

Parameters:

xCors - x-coordinates of the circles to be enclosed (can be positive and negative values)

yCors - y-coordinates of the circles to be enclosed (can be positive and negative values)

radii - radii of the circles to be enclosed (must be strictly positive, circles can be of any size)

incrementalCalcContainer

public void incrementalCalcContainer(int posCircleToAdd,
                                     double[] xCors,
                                     double[] yCors,
                                     double[] radii,
                                     double xCorContainer,
                                     double yCorContainer,
                                     double radiusContainer)

Given are a set of old circles, a circular container which encloses these circles and a new circle. This method tests whether the new circle fits into the existing container. If yes, the method returns. If not, the method increases the size of the container such that it encloses both the old circles and the new circle. Calculations are performed in an efficient way, thereby starting from the old container. It is much cheaper to invoke this method when a new circle is added, than to invoke the calcContainer(...) method.

Parameters:

posCircleToAdd: - the position of the circle that is being added in the xCors/yCors/radii vectors

xCors: - xCors of placed circles (including the circle that is being added)

yCors: - yCors of placed circles (including the circle that is being added)

radii: - radii of placed circles (including the circle that is being added)

xCorContainer: - xCor of center of existing container

yCorContainer: - yCor of center of existing container

radiusContainer: - : radix of existing container

getRadius

public double getRadius()

Get the radius of the enclosing circle

Returns:

the radius of the enclosing circle

getContainerPosition

public double[] getContainerPosition()

Get the x and y coordinates of the center of the enclosing circle

Returns:

x and y coordinates of the center of the enclosing circle, returned as an array a, where a[0]=x-cor and a[1]=y-cor

getContainerPositionAsPoint

public Point2D getContainerPositionAsPoint()

Get the x and y coordinates of the center of the enclosing circle

Returns:

x and y coordinates of the center of the enclosing circle as a point