Creates layouts with overlapping circles

[JeffreyBLewis]

When I pass packCircles the following set of areas:

656
1
41
240
17
10
85

the returned SVG includes overlapping and fully enclosed circles. I have also posted a similar report at mbedward/packcircles#2.

[pmenzel]

I modified the code according to the fix for the same bug in D3-hierarchy.
Hope it works now properly, could you please test it on the other problematic
inputs that you had?
thanks

[JeffreyBLewis]

Thanks. Here is little python test script that generates the sort of data that was causing trouble before and now does not:

import sys
from subprocess import call
from lxml import etree
from numpy.random import exponential as rexp
def overlap(a,b):
     """Check for overlap of two circles"""
     dx = a[0] - b[0]
     dy = a[1] - b[1]
     dr = a[2] + b[2]
     dist = dx*dx + dy*dy
     return( dist  <  (dr*dr - 1e-2) )

def anyOverlap(a,b):
     """Check if circle a overlaps any circle in list of circles b"""
     for bb in b:
        if overlap(a,bb): 
             return True
     return False

def checkSVG(fn):
     svg = open(fn,"r").read()
     tree = etree.fromstring(svg)

     circles = []
     for cc in tree.findall(".//{http://www.w3.org/2000/svg}circle"):
          circle = [float(cc.get('cx')),float(cc.get('cy')),float(cc.get('r'))]
          if anyOverlap(circle,circles):
               return True
          circles.append(circle)
     return False

def test_pack(n=50,scale=1):
     open("test.dat","w").write("\n".join([str(int(round(1000.0*x))+1) for x in rexp(scale,n)]))
     call("../packCircles -i test.dat > test.svg",shell=True)
     return checkSVG("test.svg")

if __name__ == "__main__":
     print "Checking canonical test case...",
     open("test2.dat","w").write("\n".join([str(x) for x in [656, 1, 41, 240, 17, 10, 85]]))
     call("../packCircles -i test2.dat > test2.svg",shell=True)
     print checkSVG("test2.svg") and "fail" or "pass"
     print ""

     print "Trying 1000 randomly generated sets of areas:"
     failures = 0
     for it in range(1000):
          if test_pack(5,1):
               sys.stdout.write('f'),
               failures += 1
               #break
          else:
               sys.stdout.write('p')
          if (it+1)%78==0:
               sys.stdout.write('\n')
     print "\n\nTotal Failures found = %i" % failures

[pmenzel]

great, I also tried it and got no failures!