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., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
  24
  25
  26 import types, math
  27 import bbox, path, unit, trafo
  28
  29 class _marker: pass
  30
  31 class BoxCrossError(Exception): pass
  32
  33 class polygon_pt:
  34
  35     def __init__(self, corners=None, center=None):
  36         self.corners = corners
  37         self.center = center
  38         if self.center is None:
  39             self._ensurecenter()
  40
  41     def _ensurecenter(self):
  42         if self.center is None:
  43             self.center = 0, 0
  44             for corn in self.corners:
  45                 self.center = self.center[0] + corn[0], self.center[1] + corn[1]
  46             self.center = self.center[0]/len(self.corners), self.center[1]/len(self.corners)
  47
  48     def path(self, centerradius=None, bezierradius=None, beziersoftness=None):
  49         pathitems = []
  50         if centerradius is not None and self.center is not None:
  51             r = unit.topt(centerradius)
  52             pathitems.append(path.arc_pt(self.center[0], self.center[1], r, 0, 360))
  53             pathitems.append(path.closepath())
  54         if bezierradius is not None or beziersoftness is not None:
  55             raise ValueError("smooth functionality removed; apply smooth deformer on path")
  56         pathitems.append(path.moveto_pt(self.corners[0][0], self.corners[0][1]))
  57         for x, y in self.corners[1:]:
  58             pathitems.append(path.lineto_pt(x, y))
  59         pathitems.append(path.closepath())
  60         return path.path(*pathitems)
  61
  62     def transform(self, *trafos):
  63         for trafo in trafos:
  64             if self.center is not None:
  65                 self.center = trafo.apply_pt(*self.center)
  66             self.corners = [trafo.apply_pt(*point) for point in self.corners]
  67
  68     def reltransform(self, *trafos):
  69         if self.center is not None:
  70             trafos = ([trafo.translate_pt(-self.center[0], -self.center[1])] +
  71                       list(trafos) +
  72                       [trafo.translate_pt(self.center[0], self.center[1])])
  73         self.transform(*trafos)
  74
  75     def successivepointnumbers(self):
  76         return [i and (i - 1, i) or (len(self.corners) - 1, 0) for i in range(len(self.corners))]
  77
  78     def successivepoints(self):
  79         return [(self.corners[i], self.corners[j]) for i, j in self.successivepointnumbers()]
  80
  81     def circlealignlinevector_pt(self, a, dx, dy, ex, ey, fx, fy, epsilon=1e-10):
  82         cx, cy = self.center
  83         gx, gy = ex - fx, ey - fy # direction vector
  84         if gx*gx + gy*gy < epsilon: # zero line length
  85             return None             # no solution -> return None
  86         rsplit = (dx*gx + dy*gy) * 1.0 / (gx*gx + gy*gy)
  87         bx, by = dx - gx * rsplit, dy - gy * rsplit
  88         if bx*bx + by*by < epsilon: # zero projection
  89             return None             # no solution -> return None
  90         if bx*gy - by*gx < 0: # half space
  91             return None       # no solution -> return None
  92         sfactor = math.sqrt((dx*dx + dy*dy) / (bx*bx + by*by))
  93         bx, by = a * bx * sfactor, a * by * sfactor
  94         alpha = ((bx+cx-ex)*dy - (by+cy-ey)*dx) * 1.0 / (gy*dx - gx*dy)
  95         if alpha > 0 - epsilon and alpha < 1 + epsilon:
  96                 beta = ((ex-bx-cx)*gy - (ey-by-cy)*gx) * 1.0 / (gx*dy - gy*dx)
  97                 return beta*dx, beta*dy # valid solution -> return align tuple
  98         # crossing point at the line, but outside a valid range
  99         if alpha < 0:
 100             return 0 # crossing point outside e
 101         return 1 # crossing point outside f
 102
 103     def linealignlinevector_pt(self, a, dx, dy, ex, ey, fx, fy, epsilon=1e-10):
 104         cx, cy = self.center
 105         gx, gy = ex - fx, ey - fy # direction vector
 106         if gx*gx + gy*gy < epsilon: # zero line length
 107             return None             # no solution -> return None
 108         if gy*dx - gx*dy < -epsilon: # half space
 109             return None              # no solution -> return None
 110         if dx*gx + dy*gy > epsilon or dx*gx + dy*gy < -epsilon:
 111             if dx*gx + dy*gy < 0: # angle bigger 90 degree
 112                 return 0 # use point e
 113             return 1 # use point f
 114         # a and g are othorgonal
 115         alpha = ((a*dx+cx-ex)*dy - (a*dy+cy-ey)*dx) * 1.0 / (gy*dx - gx*dy)
 116         if alpha > 0 - epsilon and alpha < 1 + epsilon:
 117             beta = ((ex-a*dx-cx)*gy - (ey-a*dy-cy)*gx) * 1.0 / (gx*dy - gy*dx)
 118             return beta*dx, beta*dy # valid solution -> return align tuple
 119         # crossing point at the line, but outside a valid range
 120         if alpha < 0:
 121             return 0 # crossing point outside e
 122         return 1 # crossing point outside f
 123
 124     def circlealignpointvector_pt(self, a, dx, dy, px, py, epsilon=1e-10):
 125         if a*a < epsilon:
 126             return None
 127         cx, cy = self.center
 128         p = 2 * ((px-cx)*dx + (py-cy)*dy)
 129         q = ((px-cx)*(px-cx) + (py-cy)*(py-cy) - a*a)
 130         if p*p/4 - q < 0:
 131             return None
 132         if a > 0:
 133             alpha = - p / 2 + math.sqrt(p*p/4 - q)
 134         else:
 135             alpha = - p / 2 - math.sqrt(p*p/4 - q)
 136         return alpha*dx, alpha*dy
 137
 138     def linealignpointvector_pt(self, a, dx, dy, px, py):
 139         cx, cy = self.center
 140         beta = (a*dx+cx-px)*dy - (a*dy+cy-py)*dx
 141         return a*dx - beta*dy - px + cx, a*dy + beta*dx - py + cy
 142
 143     def alignvector_pt(self, a, dx, dy, alignlinevector, alignpointvector):
 144         n = math.hypot(dx, dy)
 145         dx, dy = dx / n, dy / n
 146         linevectors = map(lambda (p1, p2), self=self, a=a, dx=dx, dy=dy, alignlinevector=alignlinevector:
 147                                 alignlinevector(a, dx, dy, *(p1 + p2)), self.successivepoints())
 148         for linevector in linevectors:
 149             if type(linevector) is types.TupleType:
 150                 return linevector
 151         for i, j in self.successivepointnumbers():
 152             l1, l2 = linevectors[i], linevectors[j]
 153             if (l1 is not None or l2 is not None) and (l1 == 1 or l1 is None) and (l2 == 0 or l2 is None):
 154                 return alignpointvector(a, dx, dy, *self.successivepoints()[j][0])
 155         return a*dx, a*dy
 156
 157     def circlealignvector_pt(self, a, dx, dy):
 158         return self.alignvector_pt(a, dx, dy, self.circlealignlinevector_pt, self.circlealignpointvector_pt)
 159
 160     def linealignvector_pt(self, a, dx, dy):
 161         return self.alignvector_pt(a, dx, dy, self.linealignlinevector_pt, self.linealignpointvector_pt)
 162
 163     def circlealignvector(self, a, dx, dy):
 164         ndx, ndy = self.circlealignvector_pt(unit.topt(a), dx, dy)
 165         return ndx * unit.t_pt, ndy * unit.t_pt
 166
 167     def linealignvector(self, a, dx, dy):
 168         ndx, ndy = self.linealignvector_pt(unit.topt(a), dx, dy)
 169         return ndx * unit.t_pt, ndy * unit.t_pt
 170
 171     def circlealign_pt(self, *args):
 172         self.transform(trafo.translate_pt(*self.circlealignvector_pt(*args)))
 173         return self
 174
 175     def linealign_pt(self, *args):
 176         self.transform(trafo.translate_pt(*self.linealignvector_pt(*args)))
 177         return self
 178
 179     def circlealign(self, *args):
 180         self.transform(trafo.translate(*self.circlealignvector(*args)))
 181         return self
 182
 183     def linealign(self, *args):
 184         self.transform(trafo.translate(*self.linealignvector(*args)))
 185         return self
 186
 187     def extent_pt(self, dx, dy):
 188         n = math.hypot(dx, dy)
 189         dx, dy = dx / n, dy / n
 190         oldcenter = self.center
 191         if self.center is None:
 192             self.center = 0, 0
 193         x1, y1 = self.linealignvector_pt(0, dx, dy)
 194         x2, y2 = self.linealignvector_pt(0, -dx, -dy)
 195         self.center = oldcenter
 196         return (x1-x2)*dx + (y1-y2)*dy
 197
 198     def extent(self, dx, dy):
 199         return self.extent_pt(dx, dy) * unit.t_pt
 200
 201     def pointdistance_pt(self, x, y):
 202         result = None
 203         for p1, p2 in self.successivepoints():
 204             gx, gy = p2[0] - p1[0], p2[1] - p1[1]
 205             if gx * gx + gy * gy < 1e-10:
 206                 dx, dy = p1[0] - x, p1[1] - y
 207             else:
 208                 a = (gx * (x - p1[0]) + gy * (y - p1[1])) / (gx * gx + gy * gy)
 209                 if a < 0:
 210                     dx, dy = p1[0] - x, p1[1] - y
 211                 elif a > 1:
 212                     dx, dy = p2[0] - x, p2[1] - y
 213                 else:
 214                     dx, dy = x - p1[0] - a * gx, y - p1[1] - a * gy
 215             new = math.hypot(dx, dy)
 216             if result is None or new < result:
 217                 result = new
 218         return result
 219
 220     def pointdistance(self, x, y):
 221         return self.pointdistance_pt(unit.topt(x), unit.topt(y)) * unit.t_pt
 222
 223     def boxdistance_pt(self, other, epsilon=1e-10):
 224         # XXX: boxes crossing and distance calculation is O(N^2)
 225         for p1, p2 in self.successivepoints():
 226             for p3, p4 in other.successivepoints():
 227                 a = (p4[1] - p3[1]) * (p3[0] - p1[0]) - (p4[0] - p3[0]) * (p3[1] - p1[1])
 228                 b = (p2[1] - p1[1]) * (p3[0] - p1[0]) - (p2[0] - p1[0]) * (p3[1] - p1[1])
 229                 c = (p2[0] - p1[0]) * (p4[1] - p3[1]) - (p2[1] - p1[1]) * (p4[0] - p3[0])
 230                 if (abs(c) > 1e-10 and
 231                     a / c > -epsilon and a / c < 1 + epsilon and
 232                     b / c > -epsilon and b / c < 1 + epsilon):
 233                     raise BoxCrossError
 234         result = None
 235         for x, y in other.corners:
 236             new = self.pointdistance_pt(x, y)
 237             if result is None or new < result:
 238                 result = new
 239         for x, y in self.corners:
 240             new = other.pointdistance_pt(x, y)
 241             if result is None or new < result:
 242                 result = new
 243         return result
 244
 245     def boxdistance(self, other):
 246         return self.boxdistance_pt(other) * unit.t_pt
 247
 248     def bbox(self):
 249         return bbox.bbox_pt(min([x[0] for x in self.corners]),
 250                           min([x[1] for x in self.corners]),
 251                           max([x[0] for x in self.corners]),
 252                           max([x[1] for x in self.corners]))
 253
 254
 255 def genericalignequal_pt(method, polygons, a, dx, dy):
 256     vec = None
 257     for p in polygons:
 258         v = method(p, a, dx, dy)
 259         if vec is None or vec[0] * dx + vec[1] * dy < v[0] * dx + v[1] * dy:
 260             vec = v
 261     for p in polygons:
 262         p.transform(trafo.translate_pt(*vec))
 263
 264
 265 def circlealignequal_pt(polygons, *args):
 266     genericalignequal_pt(polygon_pt.circlealignvector_pt, polygons, *args)
 267
 268 def linealignequal_pt(polygons, *args):
 269     genericalignequal_pt(polygon_pt.linealignvector_pt, polygons, *args)
 270
 271 def circlealignequal(polygons, a, *args):
 272     circlealignequal_pt(polygons, unit.topt(a), *args)
 273
 274 def linealignequal(polygons, a, *args):
 275     linealignequal_pt(polygons, unit.topt(a), *args)
 276
 277
 278 def tile_pt(polygons, a, dx, dy):
 279     maxextent = polygons[0].extent_pt(dx, dy)
 280     for p in polygons[1:]:
 281         extent = p.extent_pt(dx, dy)
 282         if extent > maxextent:
 283             maxextent = extent
 284     delta = maxextent + a
 285     d = 0
 286     for p in polygons:
 287         p.transform(trafo.translate_pt(d*dx, d*dy))
 288         d += delta
 289     return delta
 290
 291
 292 def tile(polygons, a, dx, dy):
 293     return tile_pt(polygons, unit.topt(a), dx, dy) * unit.t_pt
 294
 295
 296 class polygon(polygon_pt):
 297
 298     def __init__(self, corners=None, center=None, **args):
 299         corners = [[unit.topt(x) for x in corner] for corner in corners]
 300         if center is not None:
 301             center = unit.topt(center[0]), unit.topt(center[1])
 302         polygon_pt.__init__(self, corners=corners, center=center, **args)
 303
 304
 305 class rect_pt(polygon_pt):
 306
 307     def __init__(self, x, y, width, height, relcenter=(0, 0), abscenter=(0, 0),
 308                        corners=_marker, center=_marker, **args):
 309         if corners != _marker or center != _marker:
 310             raise ValueError
 311         polygon_pt.__init__(self, corners=((x, y),
 312                                          (x + width, y),
 313                                          (x + width, y + height),
 314                                          (x, y + height)),
 315                                 center=(x + relcenter[0] * width + abscenter[0],
 316                                         y + relcenter[1] * height + abscenter[1]),
 317                                 **args)
 318
 319
 320 class rect(rect_pt):
 321
 322     def __init__(self, x, y, width, height, relcenter=(0, 0), abscenter=(0, 0), **args):
 323         rect_pt.__init__(self, unit.topt(x), unit.topt(y), unit.topt(width), unit.topt(height),
 324                                relcenter=relcenter,
 325                                abscenter=(unit.topt(abscenter[0]), unit.topt(abscenter[1])), **args)
 326