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.

Sub arc list and sub arc hash addressing: Generally while we could pick random values of phi between 0 and 2 pi radians and toss any value that falls inside a given arc closure space. On the other hand, as any given sub arc closure space increases there is a greater likelihood of repeatedly randomly generated phi values that are going to fail, and hence potentially increasing computation time by including discards. I've considered overcoming this problem by randomly picking any known sub arc closure and two having a an phi ordered list of closed sub arcs, structuring then a minimal and maximal random phi set to pick from where phi will not phi as a pick value, while still ensuring the random pick phi angle is still intact. This does lead to some data structure organizational issues.

A closed sub arc can actually consists of one or more tangent circles that invariably linked in forming the closure of a given closed sub arc. A closed sub arc is addressed by (minphi, maxphi) ranges on its hash set, and any update to such sub arc, can also change, removing old addressing while updating to new addressing, especially as tangent circle triad is formed between parent, and pre existing tangent circle boundaries relative a new tangent circle changing the boundaries of a sub arc closure, assuming that no further tangent circle packing subdivision is allowed between a new given boundary. In this method, because sub arc closures are likely to under go an evolutionary process by which ancestral closures are likely subsumed into larger sub arc closures, a binary search tree could speed things up in address arranging a subset tangent circle phi (that is, when we want to find the nearest circle neighbor of the given closure, we traverse a phi coordinate addressing binary tree), albeit at the moment I am weighing through whether a tree were likely so needed relative to more brute force iterating a list set that would grow larger over time. A boundary can change only by the condition of the Apollonius problem if furthered subdivision is not allowed, and can also change in the 2 tangent circle problem, and 1 tangent circle problem. In the 2 tangent circle problem the new tangent circle, this can change if the Apollonius problem is neither able to provide a new tangent circle greater than or equal to minimum circle size between other child, parent and new tangent circle (with a hypothetical fourth added). In this case, the new tangent circle is subsumed into the nearest assigning parent closure and boundary conditions of such closure are updated. If on the other hand a subdivision is possible, then the new tangent circle is assigned a distinct sub arc closure set, this closure set can be joined to the old closure set if any new iterations lead to the condition of Apollonius test failure as indicated above. A 1 tangent problem leads to the creation of a new tangent circle with a distinct closure set and is never considered a subset to any existing sub arc closure set.

As in the previous algorithm that I worked on, namely the Gabriel Graph generator, neither having tangent triads obviously leave less conspicuous the generation of polygons. In this case, I may utilize the modified Dijkstra algorithm for path tracing here, for instance.

Update 5/1/15:

So the problem that I have visualized thus far in the algorithm occurs when paths from sub arcs eventually leave the construction of a tangent circle overlapping an existing set. It seems this problem would require some testing algorithm to ensure that vicinity circle neighbors are included in so far as tangent circle construction (where such neighbors weren't readily tangent to our primary Queued tangent circle). Another solution that I have conceived, or likely I imagine someone else has already conceived of this and I have merely re stumbled upon this is an algorithm that goes as follows:

There are several aspects to this construction that change the nature of the circle packing problem here.

Update 5/4/15: Restrictions on Apollonius solution are such that they are no solutions in the nesting circles case for the subdivision type mention in the previous update. Otherwise, random walk instancing does become more complex in terms of checking for circle intersections (or at least I'd need to devise a fast nearest neighbors look up solution here). So I am researching at the moment other methods here, namely with publicly provided code, for instance, furnished by Charles R Collins and Kenneth Stephenson. This method actually employs generating a packing from a triangulated Complex K a circle packing instance. It would appear based upon my rough understanding of this, that this involves approximating from the complex K a best fit, and is an approximating iterated procedure, where best fit is specified by an error amount and a 'target' fit. At the moment I am working on creating something of a random monotone polygon generator, and then potentially from this creating something of a triangulated polygon covering for this.