pyx/box.py

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