src/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 or n == 8:
  31         nlt = intersection((lh1, l21), (l11, l22))
  32         nlb = intersection((lh1, l22), (l12, l21))
  33         nrt = intersection((lh2, l11), (l12, l21))
  34         nrb = intersection((lh2, l12), (l11, l22))
  35         nl = (intersection((l11, l21), (nlt, nlb)),
  36               intersection((l12, l22), (nlt, nlb)))
  37         nr = (intersection((l11, l21), (nrt, nrb)),
  38               intersection((l12, l22), (nrt, nrb)))
  39         if n == 2:
  40             return [nl, nr]
  41         elif n == 8:
  42             return (fill(l1, nl,
  43                          (intersection(l1, lh),
  44                           intersection(nl, lh)), 2) +
  45                     [nl] +
  46                     fill(nl, nr,
  47                          (intersection(nl, lh),
  48                           intersection(nr, lh)), 2) +
  49                     [nr] +
  50                     fill(nr, l2,
  51                          (intersection(nr, lh),
  52                           intersection(l2, lh)), 2))
  53
  54 def expand_right(grid, middle):
  55     return expand(grid[-2], grid[-1],
  56                   (intersection(middle, grid[-2]),
  57                    (intersection(middle, grid[-1]))))
  58
  59 def expand_left(grid, middle):
  60     return expand(grid[1], grid[0],
  61                   (intersection(middle, grid[1]),
  62                    (intersection(middle, grid[0]))))
  63
  64 def expand(l1, l2, lh):
  65     l11, l12 = l1
  66     l21, l22 = l2
  67     lh1, lh2 = lh
  68     nt = intersection((l12, lh2), (l11, l21))
  69     nb = intersection((l11, lh2), (l12, l22))
  70     return (nt, nb)