pyx/box.py

   1 #!/usr/bin/env python
   2 #
   3 #
   4 # Copyright (C) 2002-2003 Jörg Lehmann <joergl@users.sourceforge.net>
   5 # Copyright (C) 2002-2003 André Wobst <wobsta@users.sourceforge.net>
   6 #
   7 # This file is part of PyX (http://pyx.sourceforge.net/).
   8 #
   9 # PyX is free software; you can redistribute it and/or modify
  10 # it under the terms of the GNU General Public License as published by
  11 # the Free Software Foundation; either version 2 of the License, or
  12 # (at your option) any later version.
  13 #
  14 # PyX is distributed in the hope that it will be useful,
  15 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 # GNU General Public License for more details.
  18 #
  19 # You should have received a copy of the GNU General Public License
  20 # along with PyX; if not, write to the Free Software
  21 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  22
  23
  24 import types, re, math, string, sys
  25 import bbox, path, unit, trafo, helper
  26
  27
  28 class BoxCrossError(Exception): pass
  29
  30 class _polygon:
  31
  32     def __init__(self, corners=None, center=None):
  33         self.corners = corners
  34         self.center = center
  35
  36     def path(self, centerradius=None, bezierradius=None, beziersoftness=1):
  37         pathels = []
  38         if centerradius is not None and self.center is not None:
  39             r = unit.topt(unit.length(centerradius, default_type="v"))
  40             pathels.append(path._arc(self.center[0], self.center[1], r, 0, 360))
  41             pathels.append(path.closepath())
  42         if bezierradius is None:
  43             pathels.append(path._moveto(self.corners[0][0], self.corners[0][1]))
  44             for x, y in self.corners[1:]:
  45                 pathels.append(path._lineto(x, y))
  46             pathels.append(path.closepath())
  47         else:
  48             # curved box plotting by Michael Schindler
  49             l = len(self.corners)
  50             x = beziersoftness
  51             r = unit.topt(bezierradius)
  52             for i in range(l):
  53                 c = self.corners[i]
  54                 def normed(*v):
  55                     n = math.sqrt(v[0] * v[0] + v[1] * v[1])
  56                     return v[0] / n, v[1] / n
  57                 d1 = normed(self.corners[(i - 1 + l) % l][0] - c[0],
  58                             self.corners[(i - 1 + l) % l][1] - c[1])
  59                 d2 = normed(self.corners[(i + 1 + l) % l][0] - c[0],
  60                             self.corners[(i + 1 + l) % l][1] - c[1])
  61                 dc = normed(d1[0] + d2[0], d1[1] + d2[1])
  62                 f = 0.375 * x * r
  63                 g = 1.25 * f + math.sqrt(1.5625 * f * f + f * r / 6.0)
  64                 e = f * math.sqrt(0.5 + 0.5 * (d1[0] * d2[0] + d1[1] * d2[1]))
  65                 e = c[0] + e * dc[0], c[1] + e * dc[1]
  66                 f1 = c[0] + f * d1[0], c[1] + f * d1[1]
  67                 f2 = c[0] + f * d2[0], c[1] + f * d2[1]
  68                 g1 = c[0] + g * d1[0], c[1] + g * d1[1]
  69                 g2 = c[0] + g * d2[0], c[1] + g * d2[1]
  70                 d1 = c[0] + r * d1[0], c[1] + r * d1[1]
  71                 d2 = c[0] + r * d2[0], c[1] + r * d2[1]
  72                 if i:
  73                     pathels.append(path._lineto(*d1))
  74                 else:
  75                     pathels.append(path._moveto(*d1))
  76                 pathels.append(path._curveto(*(g1 + f1 + e)))
  77                 pathels.append(path._curveto(*(f2 + g2 + d2)))
  78             pathels.append(path.closepath())
  79         return path.path(*pathels)
  80
  81     def transform(self, *trafos):
  82         for trafo in trafos:
  83             if self.center is not None:
  84                 self.center = trafo._apply(*self.center)
  85             self.corners = [trafo._apply(*point) for point in self.corners]
  86
  87     def reltransform(self, *trafos):
  88         if self.center is not None:
  89             trafos = ([trafo._translate(-self.center[0], -self.center[1])] +
  90                       list(trafos) +
  91                       [trafo._translate(self.center[0], self.center[1])])
  92         self.transform(*trafos)
  93
  94     def successivepointnumbers(self):
  95         return [i and (i - 1, i) or (len(self.corners) - 1, 0) for i in range(len(self.corners))]
  96
  97     def successivepoints(self):
  98         return [(self.corners[i], self.corners[j]) for i, j in self.successivepointnumbers()]
  99
 100     def _circlealignlinevector(self, a, dx, dy, ex, ey, fx, fy, epsilon=1e-10):
 101         cx, cy = self.center
 102         gx, gy = ex - fx, ey - fy # direction vector
 103         if gx*gx + gy*gy < epsilon: # zero line length
 104             return None             # no solution -> return None
 105         rsplit = (dx*gx + dy*gy) * 1.0 / (gx*gx + gy*gy)
 106         bx, by = dx - gx * rsplit, dy - gy * rsplit
 107         if bx*bx + by*by < epsilon: # zero projection
 108             return None             # no solution -> return None
 109         if bx*gy - by*gx < 0: # half space
 110             return None       # no solution -> return None
 111         sfactor = math.sqrt((dx*dx + dy*dy) / (bx*bx + by*by))
 112         bx, by = a * bx * sfactor, a * by * sfactor
 113         alpha = ((bx+cx-ex)*dy - (by+cy-ey)*dx) * 1.0 / (gy*dx - gx*dy)
 114         if alpha > 0 - epsilon and alpha < 1 + epsilon:
 115                 beta = ((ex-bx-cx)*gy - (ey-by-cy)*gx) * 1.0 / (gx*dy - gy*dx)
 116                 return beta*dx, beta*dy # valid solution -> return align tuple
 117         # crossing point at the line, but outside a valid range
 118         if alpha < 0:
 119             return 0 # crossing point outside e
 120         return 1 # crossing point outside f
 121
 122     def _linealignlinevector(self, a, dx, dy, ex, ey, fx, fy, epsilon=1e-10):
 123         cx, cy = self.center
 124         gx, gy = ex - fx, ey - fy # direction vector
 125         if gx*gx + gy*gy < epsilon: # zero line length
 126             return None             # no solution -> return None
 127         if gy*dx - gx*dy < -epsilon: # half space
 128             return None              # no solution -> return None
 129         if dx*gx + dy*gy > epsilon or dx*gx + dy*gy < -epsilon:
 130             if dx*gx + dy*gy < 0: # angle bigger 90 degree
 131                 return 0 # use point e
 132             return 1 # use point f
 133         # a and g are othorgonal
 134         alpha = ((a*dx+cx-ex)*dy - (a*dy+cy-ey)*dx) * 1.0 / (gy*dx - gx*dy)
 135         if alpha > 0 - epsilon and alpha < 1 + epsilon:
 136             beta = ((ex-a*dx-cx)*gy - (ey-a*dy-cy)*gx) * 1.0 / (gx*dy - gy*dx)
 137             return beta*dx, beta*dy # valid solution -> return align tuple
 138         # crossing point at the line, but outside a valid range
 139         if alpha < 0:
 140             return 0 # crossing point outside e
 141         return 1 # crossing point outside f
 142
 143     def _circlealignpointvector(self, a, dx, dy, px, py, epsilon=1e-10):
 144         if a*a < epsilon:
 145             return None
 146         cx, cy = self.center
 147         p = 2 * ((px-cx)*dx + (py-cy)*dy)
 148         q = ((px-cx)*(px-cx) + (py-cy)*(py-cy) - a*a)
 149         if p*p/4 - q < 0:
 150             return None
 151         if a > 0:
 152             alpha = - p / 2 + math.sqrt(p*p/4 - q)
 153         else:
 154             alpha = - p / 2 - math.sqrt(p*p/4 - q)
 155         return alpha*dx, alpha*dy
 156
 157     def _linealignpointvector(self, a, dx, dy, px, py):
 158         cx, cy = self.center
 159         beta = (a*dx+cx-px)*dy - (a*dy+cy-py)*dx
 160         return a*dx - beta*dy - px + cx, a*dy + beta*dx - py + cy
 161
 162     def _alignvector(self, a, dx, dy, alignlinevector, alignpointvector):
 163         n = math.sqrt(dx * dx + dy * dy)
 164         dx, dy = dx / n, dy / n
 165         linevectors = map(lambda (p1, p2), self=self, a=a, dx=dx, dy=dy, alignlinevector=alignlinevector:
 166                                 alignlinevector(a, dx, dy, *(p1 + p2)), self.successivepoints())
 167         for linevector in linevectors:
 168             if type(linevector) is types.TupleType:
 169                 return linevector
 170         for i, j in self.successivepointnumbers():
 171             l1, l2 = linevectors[i], linevectors[j]
 172             if (l1 is not None or l2 is not None) and (l1 == 1 or l1 is None) and (l2 == 0 or l2 is None):
 173                 return alignpointvector(a, dx, dy, *self.successivepoints()[j][0])
 174         return a*dx, a*dy
 175
 176     def _circlealignvector(self, a, dx, dy):
 177         return self._alignvector(a, dx, dy, self._circlealignlinevector, self._circlealignpointvector)
 178
 179     def _linealignvector(self, a, dx, dy):
 180         return self._alignvector(a, dx, dy, self._linealignlinevector, self._linealignpointvector)
 181
 182     def circlealignvector(self, a, dx, dy):
 183         return map(unit.t_pt, self._circlealignvector(unit.topt(a), dx, dy))
 184
 185     def linealignvector(self, a, dx, dy):
 186         return map(unit.t_pt, self._linealignvector(unit.topt(a), dx, dy))
 187
 188     def _circlealign(self, *args):
 189         self.transform(trafo._translate(*self._circlealignvector(*args)))
 190         return self
 191
 192     def _linealign(self, *args):
 193         self.transform(trafo._translate(*self._linealignvector(*args)))
 194         return self
 195
 196     def circlealign(self, *args):
 197         self.transform(trafo.translate(*self.circlealignvector(*args)))
 198         return self
 199
 200     def linealign(self, *args):
 201         self.transform(trafo.translate(*self.linealignvector(*args)))
 202         return self
 203
 204     def _extent(self, dx, dy):
 205         n = math.sqrt(dx * dx + dy * dy)
 206         dx, dy = dx / n, dy / n
 207         oldcenter = self.center
 208         if self.center is None:
 209             self.center = 0, 0
 210         x1, y1 = self._linealignvector(0, dx, dy)
 211         x2, y2 = self._linealignvector(0, -dx, -dy)
 212         self.center = oldcenter
 213         return (x1-x2)*dx + (y1-y2)*dy
 214
 215     def extent(self, dx, dy):
 216         return unit.t_pt(self._extent(dx, dy))
 217
 218     def _pointdistance(self, x, y):
 219         result = None
 220         for p1, p2 in self.successivepoints():
 221             gx, gy = p2[0] - p1[0], p2[1] - p1[1]
 222             if gx * gx + gy * gy < 1e-10:
 223                 dx, dy = p1[0] - x, p1[1] - y
 224             else:
 225                 a = (gx * (x - p1[0]) + gy * (y - p1[1])) / (gx * gx + gy * gy)
 226                 if a < 0:
 227                     dx, dy = p1[0] - x, p1[1] - y
 228                 elif a > 1:
 229                     dx, dy = p2[0] - x, p2[1] - y
 230                 else:
 231                     dx, dy = x - p1[0] - a * gx, y - p1[1] - a * gy
 232             new = math.sqrt(dx * dx + dy * dy)
 233             if result is None or new < result:
 234                 result = new
 235         return result
 236
 237     def pointdistance(self, x, y):
 238         return unit.t_pt(self._pointdistance(unit.topt(x), unit.topt(y)))
 239
 240     def _boxdistance(self, other, epsilon=1e-10):
 241         # XXX: boxes crossing and distance calculation is O(N^2)
 242         for p1, p2 in self.successivepoints():
 243             for p3, p4 in other.successivepoints():
 244                 a = (p4[1] - p3[1]) * (p3[0] - p1[0]) - (p4[0] - p3[0]) * (p3[1] - p1[1])
 245                 b = (p2[1] - p1[1]) * (p3[0] - p1[0]) - (p2[0] - p1[0]) * (p3[1] - p1[1])
 246                 c = (p2[0] - p1[0]) * (p4[1] - p3[1]) - (p2[1] - p1[1]) * (p4[0] - p3[0])
 247                 if (abs(c) > 1e-10 and
 248                     a / c > -epsilon and a / c < 1 + epsilon and
 249                     b / c > -epsilon and b / c < 1 + epsilon):
 250                     raise BoxCrossError
 251         result = None
 252         for x, y in other.corners:
 253             new = self._pointdistance(x, y)
 254             if result is None or new < result:
 255                 result = new
 256         for x, y in self.corners:
 257             new = other._pointdistance(x, y)
 258             if result is None or new < result:
 259                 result = new
 260         return result
 261
 262     def boxdistance(self, other):
 263         return unit.t_pt(self._boxdistance(other))
 264
 265     def bbox(self):
 266         return bbox.bbox(min([x[0] for x in self.corners]),
 267                          min([x[1] for x in self.corners]),
 268                          max([x[0] for x in self.corners]),
 269                          max([x[1] for x in self.corners]))
 270
 271
 272 def _genericalignequal(method, polygons, a, dx, dy):
 273     vec = None
 274     for p in polygons:
 275         v = method(p, a, dx, dy)
 276         if vec is None or vec[0] * dx + vec[1] * dy < v[0] * dx + v[1] * dy:
 277             vec = v
 278     for p in polygons:
 279         p.transform(trafo._translate(*vec))
 280
 281
 282 def _circlealignequal(polygons, *args):
 283     _genericalignequal(_polygon._circlealignvector, polygons, *args)
 284
 285 def _linealignequal(polygons, *args):
 286     _genericalignequal(_polygon._linealignvector, polygons, *args)
 287
 288 def circlealignequal(polygons, a, *args):
 289     _circlealignequal(polygons, unit.topt(a), *args)
 290
 291 def linealignequal(polygons, a, *args):
 292     _linealignequal(polygons, unit.topt(a), *args)
 293
 294
 295 def _tile(polygons, a, dx, dy):
 296     maxextent = polygons[0]._extent(dx, dy)
 297     for p in polygons[1:]:
 298         extent = p._extent(dx, dy)
 299         if extent > maxextent:
 300             maxextent = extent
 301     d = 0
 302     for p in polygons:
 303         p.transform(trafo._translate(d*dx, d*dy))
 304         d += maxextent + a
 305
 306
 307 def tile(polygons, a, dx, dy):
 308     _tile(polygons, unit.topt(a), dx, dy)
 309
 310
 311 class polygon(_polygon):
 312
 313     def __init__(self, corners=None, center=None, **args):
 314         corners = [[unit.topt(x) for x in corner] for corner in corners]
 315         if center is not None:
 316             center = map(unit.topt, center)
 317         _polygon.__init__(self, corners=corners, center=center, **args)
 318
 319
 320 class _rect(_polygon):
 321
 322     def __init__(self, x, y, width, height, relcenter=(0, 0), abscenter=(0, 0),
 323                        corners=helper.nodefault, center=helper.nodefault, **args):
 324         if corners != helper.nodefault or center != helper.nodefault:
 325             raise ValueError
 326         _polygon.__init__(self, corners=((x, y),
 327                                          (x + width, y),
 328                                          (x + width, y + height),
 329                                          (x, y + height)),
 330                                 center=(x + relcenter[0] * width + abscenter[0],
 331                                         y + relcenter[1] * height + abscenter[1]),
 332                                 **args)
 333
 334
 335 class rect(_rect):
 336
 337     def __init__(self, x, y, width, height, relcenter=(0, 0), abscenter=(0, 0), **args):
 338         _rect.__init__(self, unit.topt(x), unit.topt(y), unit.topt(width), unit.topt(height),
 339                              relcenter=relcenter, abscenter=(unit.topt(abscenter[0]), unit.topt(abscenter[1])), **args)
 340