Circle Packing Algorithm

Work in progress at the moment.

So far am assembling some potential useful tools that I think can be helpful for graph generation here. Namely, one solving for a tangent circle given two existing circles (already tangent in this case to one another), and the other problem solve for the a fourth tangent circle given three circles (already tangent in relation to one another). This later problem is referred to as the Problem of Apollonius, and a solution were provisioned in 1996 (believe it or not) involving the solving of simultaneously three quadratic equations leading to a linear equations simplification. This in turn plugged back into one of the original quadratics, and solved for r and such r value leading to a determination of the circles x, and y center coordinates. Problem of Apollonius code solutions

You can find further referring information here Further Problem of Apollonius information

Update 4/30/15: For a randomly assigned angle phi, a tangent circle is constructed by the following criteria: If all neighboring tangent circles are within 60 degrees (or of desired specification) of a new randomly assigned angle phi, then such tangent circles are considered neighboring and relating angles subtending from the base of the parent(primary circle). If there exist more than two neighboring angles less than 45 degrees(or of desired specification), we choose the minimum closest neighbors of all such angles such that a set of two closest neighboring angles suffice. In this case, phi, is discarded in terms of setting the new tangent circle, but both minimum neighboring tangent circles are used in determining the next (using the Apollonius method). If phi finds no neighboring angle in proximity, then it is called solitary, and its tangent is solved using solveSingleTangent. If there exists only one neighbor to phi, then the solveTwoTangentC method is used.

Further important definitions: A primary(parent) circle for packing construction is filled (done) when one of two conditions have sufficed: One either the maximum allotment of tangent circles have been packed around it, or the set of sub arc closures contains the parent tangent circle itself. A partial closure of the circle occurs when a randomly assign a arc angle parameter to each circle in this case is exceeded. A Tangent circle is always assigned a fixed sub arc mapping where any subtended angle (and corresponding neighboring tangent circle) are placed inside any such sub arc coordinate. Not more than 1 tangent circle can reside in such sub arc coordinate, and when such has occurred, the sub arc is described as closed. A partial sub arc may be given, for instance, a randomly as a parameter ranging from 3 degrees to 10 degrees. Closing a sub arc either by reaching a minimum density angle, or that a minimum tangent circle size is exceeding to the solution of tangent circles for a given subtending phi. Minimum tangent circle size may be fixed globally or assigned randomly within desired range locally to a parent. An iterated test on the arc boundaries may be set in place in closing a sub arc. This is done in minimum size testing, so that for instance, if on the neighboring sub arc, the solution at the next sub arc sequence yields a tangent circle less than a minimum tangent circle requirement, then such sub arc is defined as closed. An iterated process of testing is complete until finding that on a given neighboring sub arc boundary relative an original tangent boundary, to a given directional sub arc maximum one finds a subtending angle that produces a sufficiently large enough tangent circle. Also one may need incorporate a apollonius test on sub arc (where for original neighboring relation rules extending this to a maximum of pi radians or 180 degrees in so far as defining neighbors and constructing a corresponding tangent circle). A failed test for instance yield that between both such neighbors all subarcs are closed.

A maximum allotment of tangent circles will be described as the maximum possible tangent circles assigned to a primary parent circle.  Packing density of the primary parent has been described above.  Closure results when 360/minarcangle sub arc segments have reached maximum density, or have been closed.

Packing method for random assignments: Initialize the Graph with a parent circle randomly assigned to a given size within desired specification. The coordinate value of this circle will be fixed at origin (0,0) for now.

A Queue system Q may be constructed for packing where any new tangent circle is added to the Q and any finished packing on a Q circle is discarded from the list (by criteria indicated above).

Construction stops in the Q when the graph of desired tangent circle node has filled (overlapped a construction fill area), or potentially a node quota terminates any further work done on the node. That is the first condition states that once we can no longer add new tangent circles and we have exhausted from the queue all existing tangent circles, then the algorithm is complete, or, as in the second condition, we have reached a desired graph quota and the algorithm terminates.

This leads to one final rule graph boundaries rule. Namely that a sub arc is closed when the tangent point extends outside of a boundary range. Note: however new tangent circles can extend outside of a given graph boundary range, but a contact tangent point between circles cannot.