Guest User

circles

a guest
Oct 5th, 2010
1,874
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import math
  2. import random
  3.  
  4. # pretty tuple indices
  5. X = 0
  6. Y = 1
  7. RADIUS = 2
  8.  
  9. # I've never seen good documentation for the following type of parameter and I'm afraid that
  10. # this is no exception. Briefly, after sorting the radii in descending order by size, the list
  11. # is split along SORT_PARAM_1 and the second piece # is randomized. The pieces are then added
  12. #  back together and the list is split along SORT_PARAM_2 and the first piece is
  13. # shuffled. The lists are then added together and returned.
  14.  
  15. SORT_PARAM_1 = .80
  16. SORT_PARAM_2 = .10
  17. # (1, 0) = totally sorted   - appealing border, very dense center, sparse midradius
  18. # (0, 1), (1, 1) = totally randomized  - well packed center, ragged border
  19.  
  20. # these constants control how close our points are placed to each other
  21. RADIAL_RESOLUTION = .4
  22. ANGULAR_RESOLUTION = .4
  23.  
  24. # this keeps the boundaries from touching
  25. PADDING = 0
  26.  
  27. def assert_no_intersections(f):
  28.     def asserter(*args, **kwargs):
  29.         circles = f(*args, **kwargs)
  30.         intersections = 0
  31.         for c1 in circles:
  32.             for c2 in circles:
  33.                 if c1 is not c2 and distance(c1, c2) < c1[RADIUS] + c2[RADIUS]:
  34.                     intersections += 1
  35.                     break
  36.         print "{0} intersections".format(intersections)
  37.         if intersections:
  38.             raise AssertionError('Doh!')
  39.         return circles
  40.     return asserter
  41.  
  42. @assert_no_intersections
  43. def positionCircles(rn):
  44.  
  45.     points = base_points(ANGULAR_RESOLUTION, RADIAL_RESOLUTION)
  46.     free_points = []
  47.     radii = fix_radii(rn)
  48.  
  49.     circles = []
  50.     point_count = 0
  51.     for radius in radii:
  52.         print "{0} free points available, {1} circles placed, {2} points examined".format(len(free_points),
  53.                                                                                           len(circles),
  54.                                                                                           point_count)
  55.         i, L = 0, len(free_points)
  56.         while i < L:
  57.             if available(circles, free_points[i], radius):
  58.                 make_circle(free_points.pop(i), radius, circles, free_points)
  59.                 break  
  60.             else:
  61.                 i += 1  
  62.         else:
  63.             for point in points:
  64.                 point_count += 1
  65.                 if available(circles, point, radius):
  66.                     make_circle(point, radius, circles, free_points)
  67.                     break
  68.                 else:
  69.                     if not contained(circles, point):
  70.                         free_points.append(point)
  71.     return circles
  72.  
  73. def fix_radii(radii):
  74.     radii = sorted(rn, reverse=True)
  75.     radii_len = len(radii)
  76.  
  77.     section1_index = int(radii_len * SORT_PARAM_1)
  78.     section2_index = int(radii_len * SORT_PARAM_2)
  79.  
  80.     section1, section2 = radii[:section1_index], radii[section1_index:]
  81.     random.shuffle(section2)
  82.     radii = section1 + section2
  83.  
  84.     section1, section2 = radii[:section2_index], radii[section2_index:]
  85.     random.shuffle(section1)
  86.     return section1 + section2
  87.  
  88. def make_circle(point, radius, circles, free_points):
  89.     new_circle = point + (radius, )
  90.     circles.append(new_circle)
  91.     i = len(free_points) - 1
  92.     while i >= 0:
  93.         if contains(new_circle, free_points[i]):
  94.             free_points.pop(i)
  95.         i -= 1
  96.                    
  97. def available(circles, point, radius):
  98.     for circle in circles:
  99.         if distance(point, circle) < radius + circle[RADIUS] + PADDING:
  100.             return False
  101.     return True
  102.        
  103.  
  104. def base_points(radial_res, angular_res):
  105.     circle_angle = 2 * math.pi
  106.     r = 0
  107.     while 1:
  108.         theta = 0
  109.         while theta <= circle_angle:
  110.             yield (r * math.cos(theta), r * math.sin(theta))
  111.             r_ = math.sqrt(r) if r > 1 else 1
  112.             theta += angular_res/r_
  113.         r += radial_res    
  114.  
  115.  
  116. def distance(p0, p1):
  117.     return math.sqrt((p0[X] - p1[X])**2 + (p0[Y] - p1[Y])**2)
  118.  
  119.  
  120. def contains(circle, point):
  121.     return distance(circle, point) < circle[RADIUS] + PADDING
  122.  
  123. def contained(circles, point):
  124.     return any(contains(c, point) for c in circles)
RAW Paste Data