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 _poly:
  31
  32     def __init__(self, corners=None, center=None, trafo=None):
  33         self.corners = corners
  34         self.center = center
  35         if trafo is not None:
  36             self.transform(trafo)
  37
  38     def path(self, centerradius=None):
  39         # TODO: - supply curved box plotting (Michael Schindler)
  40         pathels = []
  41         if centerradius is not None and self.center is not None:
  42             r = unit.topt(unit.length(centerradius, default_type="v"))
  43             pathels.append(path._arc(self.center[0], self.center[1], r, 0, 360))
  44             pathels.append(path.closepath())
  45         pathels.append(path._moveto(self.corners[0][0], self.corners[0][1]))
  46         for x, y in self.corners[1:]:
  47             pathels.append(path._lineto(x, y))
  48         pathels.append(path.closepath())
  49         return path.path(*pathels)
  50
  51     def transform(self, trafo):
  52         if self.center is not None:
  53             self.center = trafo._apply(*self.center)
  54         self.corners = [trafo._apply(*point) for point in self.corners]
  55
  56     def successivepointnumbers(self):
  57         return [i and (i - 1, i) or (len(self.corners) - 1, 0) for i in range(len(self.corners))]
  58
  59     def successivepoints(self):
  60         return [(self.corners[i], self.corners[j]) for i, j in self.successivepointnumbers()]
  61
  62     def _circlealignlinevector(self, a, dx, dy, ex, ey, fx, fy, epsilon=1e-10):
  63         cx, cy = self.center
  64         gx, gy = ex - fx, ey - fy # direction vector
  65         if gx*gx + gy*gy < epsilon: # zero line length
  66             return None             # no solution -> return None
  67         rsplit = (dx*gx + dy*gy) * 1.0 / (gx*gx + gy*gy)
  68         bx, by = dx - gx * rsplit, dy - gy * rsplit
  69         if bx*bx + by*by < epsilon: # zero projection
  70             return None             # no solution -> return None
  71         if bx*gy - by*gx < 0: # half space
  72             return None       # no solution -> return None
  73         sfactor = math.sqrt((dx*dx + dy*dy) / (bx*bx + by*by))
  74         bx, by = a * bx * sfactor, a * by * sfactor
  75         alpha = ((bx+cx-ex)*dy - (by+cy-ey)*dx) * 1.0 / (gy*dx - gx*dy)
  76         if alpha > 0 - epsilon and alpha < 1 + epsilon:
  77                 beta = ((ex-bx-cx)*gy - (ey-by-cy)*gx) * 1.0 / (gx*dy - gy*dx)
  78                 return beta*dx - cx, beta*dy - cy # valid solution -> return align tuple
  79         # crossing point at the line, but outside a valid range
  80         if alpha < 0:
  81             return 0 # crossing point outside e
  82         return 1 # crossing point outside f
  83
  84     def _linealignlinevector(self, a, dx, dy, ex, ey, fx, fy, epsilon=1e-10):
  85         cx, cy = self.center
  86         gx, gy = ex - fx, ey - fy # direction vector
  87         if gx*gx + gy*gy < epsilon: # zero line length
  88             return None             # no solution -> return None
  89         if gy*dx - gx*dy < -epsilon: # half space
  90             return None              # no solution -> return None
  91         if dx*gx + dy*gy > epsilon or dx*gx + dy*gy < -epsilon:
  92             if dx*gx + dy*gy < 0: # angle bigger 90 degree
  93                 return 0 # use point e
  94             return 1 # use point f
  95         # a and g are othorgonal
  96         alpha = ((a*dx+cx-ex)*dy - (a*dy+cy-ey)*dx) * 1.0 / (gy*dx - gx*dy)
  97         if alpha > 0 - epsilon and alpha < 1 + epsilon:
  98             beta = ((ex-a*dx-cx)*gy - (ey-a*dy-cy)*gx) * 1.0 / (gx*dy - gy*dx)
  99             return beta*dx - cx, beta*dy - cy # valid solution -> return align tuple
 100         # crossing point at the line, but outside a valid range
 101         if alpha < 0:
 102             return 0 # crossing point outside e
 103         return 1 # crossing point outside f
 104
 105     def _circlealignpointvector(self, a, dx, dy, px, py, epsilon=1e-10):
 106         if a*a < epsilon:
 107             return None
 108         cx, cy = self.center
 109         p = 2 * ((px-cx)*dx + (py-cy)*dy)
 110         q = ((px-cx)*(px-cx) + (py-cy)*(py-cy) - a*a)
 111         if p*p/4 - q < 0:
 112             return None
 113         if a > 0:
 114             alpha = - p / 2 + math.sqrt(p*p/4 - q)
 115         else:
 116             alpha = - p / 2 - math.sqrt(p*p/4 - q)
 117         return alpha*dx - cx, alpha*dy - cy
 118
 119     def _linealignpointvector(self, a, dx, dy, px, py):
 120         cx, cy = self.center
 121         beta = (a*dx+cx-px)*dy - (a*dy+cy-py)*dx
 122         return a*dx - beta*dy - px, a*dy + beta*dx - py
 123
 124     def _alignvector(self, a, dx, dy, alignlinevector, alignpointvector):
 125         linevectors = map(lambda (p1, p2), self=self, a=a, dx=dx, dy=dy, alignlinevector=alignlinevector:
 126                                 alignlinevector(a, dx, dy, *(p1 + p2)), self.successivepoints())
 127         for linevector in linevectors:
 128             if type(linevector) is types.TupleType:
 129                 return linevector
 130         for i, j in self.successivepointnumbers():
 131             l1, l2 = linevectors[i], linevectors[j]
 132             if (l1 is not None or l2 is not None) and (l1 == 1 or l1 is None) and (l2 == 0 or l2 is None):
 133                 return alignpointvector(a, dx, dy, *self.successivepoints()[j][0])
 134         return a*dx, a*dy
 135
 136     def _circlealignvector(self, a, dx, dy):
 137         return self._alignvector(a, dx, dy, self._circlealignlinevector, self._circlealignpointvector)
 138
 139     def _linealignvector(self, a, dx, dy):
 140         return self._alignvector(a, dx, dy, self._linealignlinevector, self._linealignpointvector)
 141
 142     def circlealignvector(self, a, dx, dy):
 143         return map(unit.t_pt, self._circlealignvector(unit.topt(a), dx, dy))
 144
 145     def linealignvector(self, a, dx, dy):
 146         return map(unit.t_pt, self._linealignvector(unit.topt(a), dx, dy))
 147
 148     def _circlealign(self, *args):
 149         self.transform(trafo._translate(*self._circlealignvector(*args)))
 150         return self
 151
 152     def _linealign(self, *args):
 153         self.transform(trafo._translate(*self._linealignvector(*args)))
 154         return self
 155
 156     def circlealign(self, *args):
 157         self.transform(trafo.translate(*self.circlealignvector(*args)))
 158         return self
 159
 160     def linealign(self, *args):
 161         self.transform(trafo.translate(*self.linealignvector(*args)))
 162         return self
 163
 164     def _extent(self, dx, dy):
 165         x1, y1 = self._linealignvector(0, dx, dy)
 166         x2, y2 = self._linealignvector(0, -dx, -dy)
 167         return (x1-x2)*dx + (y1-y2)*dy
 168
 169     def extent(self, dx, dy):
 170         return unit.t_pt(self._extent(dx, dy))
 171
 172     def _pointdistance(self, x, y):
 173         result = None
 174         for p1, p2 in self.successivepoints():
 175             gx, gy = p2[0] - p1[0], p2[1] - p1[1]
 176             if gx * gx + gy * gy < 1e-10:
 177                 dx, dy = p1[0] - x, p1[1] - y
 178             else:
 179                 a = (gx * (x - p1[0]) + gy * (y - p1[1])) / (gx * gx + gy * gy)
 180                 if a < 0:
 181                     dx, dy = p1[0] - x, p1[1] - y
 182                 elif a > 1:
 183                     dx, dy = p2[0] - x, p2[1] - y
 184                 else:
 185                     dx, dy = x - p1[0] - a * gx, y - p1[1] - a * gy
 186             new = math.sqrt(dx * dx + dy * dy)
 187             if result is None or new < result:
 188                 result = new
 189         return result
 190
 191     def pointdistance(self, x, y):
 192         return unit.t_pt(self._pointdistance(unit.topt(x), unit.topt(y)))
 193
 194     def _boxdistance(self, other, epsilon=1e-10):
 195         # XXX: boxes crossing and distance calculation is O(N^2)
 196         for p1, p2 in self.successivepoints():
 197             for p3, p4 in other.successivepoints():
 198                 a = (p4[1] - p3[1]) * (p3[0] - p1[0]) - (p4[0] - p3[0]) * (p3[1] - p1[1])
 199                 b = (p2[1] - p1[1]) * (p3[0] - p1[0]) - (p2[0] - p1[0]) * (p3[1] - p1[1])
 200                 c = (p2[0] - p1[0]) * (p4[1] - p3[1]) - (p2[1] - p1[1]) * (p4[0] - p3[0])
 201                 if (abs(c) > 1e-10 and
 202                     a / c > -epsilon and a / c < 1 + epsilon and
 203                     b / c > -epsilon and b / c < 1 + epsilon):
 204                     raise BoxCrossError
 205         result = None
 206         for x, y in other.corners:
 207             new = self._pointdistance(x, y)
 208             if result is None or new < result:
 209                 result = new
 210         for x, y in self.corners:
 211             new = other._pointdistance(x, y)
 212             if result is None or new < result:
 213                 result = new
 214         return result
 215
 216     def boxdistance(self, other):
 217         return unit.t_pt(self._boxdistance(other))
 218
 219     #TODO: bbox method missing
 220     def bbox(self):
 221         return bbox.bbox(min([x[0] for x in self.corners]),
 222                          min([x[1] for x in self.corners]),
 223                          max([x[0] for x in self.corners]),
 224                          max([x[1] for x in self.corners]))
 225
 226
 227 def _linealignequal(polys, *args):
 228     vec = None
 229     for p in polys:
 230         v = p._linealignvector(*args)
 231         if vec is None or vec[0]*vec[0] + vec[1]*vec[1] < v[0]*v[0] + v[1]*v[1]:
 232             vec = v
 233     for p in polys:
 234         p.transform(trafo._translate(*vec))
 235
 236
 237 class poly(_poly):
 238
 239     def __init__(self, corners=None, center=None, **args):
 240         corners = [[unit.topt(x) for x in corner] for corner in corners]
 241         if center is not None:
 242             center = map(unit.topt, center)
 243         _poly.__init__(self, corners=corners, center=center, **args)
 244
 245
 246 class _rect(_poly):
 247
 248     def __init__(self, x, y, width, height, relcenter=(0, 0), abscenter=(0, 0),
 249                        corners=helper.nodefault, center=helper.nodefault, **args):
 250         if corners != helper.nodefault or center != helper.nodefault:
 251             raise ValueError
 252         _poly.__init__(self, corners=((x, y),
 253                                       (x + width, y),
 254                                       (x + width, y + height),
 255                                       (x, y + height)),
 256                              center=(x + relcenter[0] * width + abscenter[0],
 257                                      y + relcenter[1] * height + abscenter[1]),
 258                              **args)
 259
 260
 261 class rect(_rect):
 262
 263     def __init__(self, x, y, width, height, relcenter=(0, 0), abscenter=(0, 0), **args):
 264         _rect.__init__(self, unit.topt(x), unit.topt(y), unit.topt(width), unit.topt(height),
 265                              relcenter=relcenter, abscenter=(unit.topt(center[0]), unit.topt(center[1])), **args)
 266