new_geometry.py

   1
   2 def intersection(l1, l2):
   3     a1, b1, c1 = points_to_line(*l1)
   4     a2, b2, c2 = points_to_line(*l2)
   5     delim = float(a1 * b2 - b1 * a2)
   6     x = (b1 * c2 - c1 * b2) / delim
   7     y = (c1 * a2 - a1 * c2) / delim
   8     return x, y
   9
  10 def points_to_line((x1, y1), (x2, y2)):
  11     return (y2 - y1, x1 - x2, x2 * y1 - x1 * y2)
  12
  13 def fill(l1, l2, lh, n):
  14     if n == 0:
  15         return []
  16     l11, l12 = l1
  17     l21, l22 = l2
  18     lh1, lh2 = lh
  19     lmt = intersection((lh1, l21), (lh2, l11))
  20     lmb = intersection((lh1, l22), (lh2, l12))
  21     lm = (intersection((l11, l21), (lmt, lmb)),
  22           intersection((l12, l22), (lmt, lmb)))
  23     if n == 1:
  24         return [lm]
  25     if n % 2 == 1:
  26         lhc = intersection(lh, lm)
  27         return (fill(l1, lm, (lh1, lhc), n / 2) +
  28                 [lm] +
  29                 fill(lm, l2, (lhc, lh2), n / 2))
  30     elif n == 2:
  31         # TODO fine tune this
  32         nlt = intersection((lh1, l21), (l11, l22))
  33         nlb = intersection((lh1, l22), (l12, l21))
  34         nrt = intersection((lh2, l11), (l12, l21))
  35         nrb = intersection((lh2, l12), (l11, l22))
  36         nl = (intersection((l11, l21), (nlt, nlb)),
  37               intersection((l12, l22), (nlt, nlb)))
  38         nr = (intersection((l11, l21), (nrt, nrb)),
  39               intersection((l12, l22), (nrt, nrb)))
  40         return [nl, nr]
  41
  42 def expand_right(grid, middle):
  43     return expand(grid[-2], grid[-1],
  44                   (intersection(middle, grid[-2]),
  45                    (intersection(middle, grid[-1]))))
  46
  47 def expand_left(grid, middle):
  48     return expand(grid[1], grid[0],
  49                   (intersection(middle, grid[1]),
  50                    (intersection(middle, grid[0]))))
  51
  52 def expand(l1, l2, lh):
  53     l11, l12 = l1
  54     l21, l22 = l2
  55     lh1, lh2 = lh
  56     nt = intersection((l12, lh2), (l11, l21))
  57     nb = intersection((l11, lh2), (l12, l22))
  58     return (nt, nb)