Commits

Jörg Rädler committed 5ce3406

first commit

  • Participants

Comments (0)

Files changed (19)

+30.03.11
+- version 2.0.4
+- fixed a bug in writeSVG()
+- added optional hole-flag for gpf files to the documentation
+- added Utils.gpfInfo()
+
+29.09.10
+- fixed centerAroundOrigin()
+- updated documentation, merged with the 3.0.x branch
+- included PDF documentation in the dist packages
+
+20.09.10
+- version 2.0.3
+
+17.09.10
+- added the tileBSP() function and an example
+
+07.05.10
+- version 2.0.2
+- changed calculation of orientation to another (better) algorithm
+  (thanks to Jan Nabbefeld)
+- added a patch to get sample points from the polygon
+  (thanks to Thouis (Ray) Jones)
+- several changes to fix potential memory leaks
+  (thanks to Daniel Derrien and others)
+
+14.09.09
+- version 2.0.1
+- bugfix for calculation of orientation and center
+
+02.06.09
+- fork of the 3.0 branch to work with python-3.x
+
+02.06.09
+- version 2.0 final
+- added SierpinskiCarpet to Shapes
+- deleted an old print statement in pdf export
+
+09.03.09
+- version 2.0b2
+- updated documentation
+- works now with latest numpy
+- some bugfixes
+
+15.02.09
+- version 2.0b1
+- lots of changes, most important are:
+    * Polygons can now be subclassed
+    * added a cloneContour method 
+    * moved modules to a package
+    * moved i/o and shapes to separate modules
+    * moved from numeric to numpy
+    * dropped some old stuff, requires a recent python interpreter now (>=2.5)
+- open bugs:
+    * numpy-test doesn't work yet
+
+19.04.07
+- version 1.17
+- bugfix for Python 2.5 / PyMalloc (mixed PyMem_* and PyObject_*)
+
+19.04.06
+- version 1.16
+- small change to work with Python 2.2 again (thanks to Tim Wegener),
+  unittest will not work with 2.2
+
+12.08.05
+- version 1.15
+- fixed one bug introduced in 1.14
+
+11.08.05
+- version 1.14
+- fixed a memory leak when not using Numeric (hopefully)
+
+25.01.05
+- version 1.13
+- added dump/loadXML()
+- added dump/loadBinary()
+
+21.12.04
+- version 1.12
+- switched to gpc 2.32
+
+26.10.04
+- catched errors while opening files for reading or writing
+
+18.10.04
+- added some tests
+
+12.10.04
+- version 1.10
+- started the HISTORY file
+- improved SVG export a lot
+- added support for unittest
+- moved some tests from examples to PolygonTest.py
+- collected and improved other examples -> PolygonExamples.py
+- all examples now produce SVG instead of gnuplot files
+MANIFEST
+HISTORY
+setup.py
+setup.cfg.mingw32
+Polygon/__init__.py
+Polygon/IO.py
+Polygon/Utils.py
+Polygon/Shapes.py
+doc/Polygon.txt
+doc/Polygon.pdf
+doc/Examples.py
+doc/testpoly.gpf
+src/gpc.c
+src/gpc.h
+src/cPolygon.c
+src/PolyUtil.c
+src/PolyUtil.h
+test/Test.py
+# -*- coding: utf-8 -*-
+#       $Id: IO.py 104 2010-11-30 16:41:16Z jraedler $  
+
+"""
+This module provides functions for reading and writing Polygons in different
+formats.
+
+The following write-methods will accept different argument types for the 
+output. If ofile is None, the method will create and return a StringIO-object. 
+If ofile is a string, a file with that name will be created. If ofile is a 
+file, it will be used for writing.
+
+The following read-methods will accept different argument types for the 
+output. An file or StringIO object will be used directly. If the argument is a 
+string, the function tries to read a file with that name. If it fails, it 
+will evaluate the string directly.
+"""
+
+from cPolygon import Polygon
+from types import StringTypes
+try:
+    from cStringIO import StringIO
+except:
+    from StringIO import StringIO
+
+from xml.dom.minidom import parseString, Node
+
+from struct import pack, unpack, calcsize
+
+try:
+    import reportlab
+    hasPDFExport = True
+except:
+    hasPDFExport = False
+
+try:
+    import Imaging
+    hasPILExport = True
+except:
+    hasPILExport = False
+
+
+## some helpers
+
+def __flatten(s):
+    for a in s:
+        for b in a:
+            yield b
+
+
+def __couples(s):
+    for i in range(0, len(s), 2):
+        yield s[i], s[i+1]
+
+
+def __unpack(f, b):
+    s = calcsize(f)
+    return unpack(f, b[:s]), b[s:]
+                        
+
+class __RingBuffer:
+    def __init__(self, seq):
+        self.s = seq
+        self.i = 0
+        self.l = len(seq)
+    def __call__(self):
+        o = self.s[self.i]
+        self.i += 1
+        if self.i == self.l:
+            self.i = 0
+        return o
+
+
+def getWritableObject(ofile):
+    """try to make a writable file-like object from argument"""
+    if ofile is None:
+        return StringIO(), False
+    elif type(ofile) in StringTypes:
+        return open(ofile, 'w'), True
+    elif type(ofile) in (file, StringIO):
+        return ofile, False
+    else:
+        raise Exception("Can't make a writable object from argument!")
+
+
+def getReadableObject(ifile):
+    """try to make a readable file-like object from argument"""
+    if type(ifile) in StringTypes:
+        try:
+            return open(ifile, 'r'), True
+        except:
+            return StringIO(ifile), True
+    elif type(ifile) in (file, StringIO):
+        return ifile, False
+    else:
+        raise Exception("Can't make a readable object from argument!")
+
+
+def decodeBinary(bin):
+    """
+    Create Polygon from a binary string created with encodeBinary(). If the string 
+    is not valid, the whole thing may break!
+
+    :Arguments:
+        - s: string
+    :Returns:
+        new Polygon
+    """
+    nC, b = __unpack('!I', bin)
+    p = Polygon()
+    for i in range(nC[0]):
+        x, b = __unpack('!l', b)
+        if x[0] < 0:
+            isHole = 1
+            s = -2*x[0]
+        else:
+            isHole = 0
+            s = 2*x[0]
+        flat, b = __unpack('!%dd' % s, b)
+        p.addContour(tuple(__couples(flat)), isHole)
+    return p
+
+
+def encodeBinary(p):
+    """
+    Encode Polygon p to a binary string. The binary string will be in a standard 
+    format with network byte order and should be rather machine independant. 
+    There's no redundancy in the string, any damage will make the hole polygon 
+    information unusable.
+
+    :Arguments:
+        - p: Polygon
+    :Returns:
+        string
+    """
+    l = [pack('!I', len(p))]
+    for i, c in enumerate(p):
+        l.append(pack('!l', len(c)*(1,-1)[p.isHole(i)]))
+        l.append(pack('!%dd' %(2*len(c)), *__flatten(c)))
+    return "".join(l)
+            
+
+def writeGnuplot(ofile, polylist):
+    """
+    Write a list of Polygons to a gnuplot file, which may be plotted using the 
+    command ``plot "ofile" with lines`` from gnuplot.
+
+    :Arguments:
+        - ofile: see above
+        - polylist: sequence of Polygons
+    :Returns:
+        ofile object
+    """
+    f, cl = getWritableObject(ofile)
+    for p in polylist:
+        for vl in p:
+            for j in vl:
+                f.write('%g %g\n' % tuple(j))
+            f.write('%g %g\n\n' % tuple(vl[0]))
+    if cl: f.close()
+    return f
+
+
+def writeGnuplotTriangles(ofile, polylist):
+    """
+    Converts a list of Polygons to triangles and write the tringle data to a 
+    gnuplot file, which may be plotted using the command 
+    ``plot "ofile" with lines`` from gnuplot.
+
+    :Arguments:
+        - ofile: see above
+        - polylist: sequence of Polygons
+    :Returns:
+        ofile object
+    """
+    f, cl = getWritableObject(ofile)
+    for p in polylist:
+        for vl in p.triStrip():
+            j = 0
+            for j in range(len(vl)-2):
+                f.write('%g %g \n %g %g \n %g %g \n %g %g\n\n' %
+                        tuple(vl[j]+vl[j+1]+vl[j+2]+vl[j]))
+            f.write('\n')
+    if cl: f.close()
+    f.close()
+
+
+def writeSVG(ofile, polylist, width=None, height=None, fill_color=None,
+                fill_opacity=None, stroke_color=None, stroke_width=None):
+    """
+    Write a SVG representation of the Polygons in polylist, width and/or height 
+    will be adapted if not given. fill_color, fill_opacity, stroke_color and 
+    stroke_width can be sequences of the corresponding SVG style attributes to use.
+
+    :Arguments:
+        - ofile: see above
+        - polylist: sequence of Polygons
+        - optional width: float
+        - optional height: height
+        - optional fill_color: sequence of colors (3-tuples of floats: RGB)
+        - optional fill_opacity: sequence of colors
+        - optional stroke_color: sequence of colors
+        - optional stroke_width: sequence of floats
+    :Returns:
+        ofile object
+    """
+    f, cl = getWritableObject(ofile)
+    pp = [Polygon(p) for p in polylist] # use clones only
+    [p.flop(0.0) for p in pp] # adopt to the SVG coordinate system 
+    bbs = [p.boundingBox() for p in pp]
+    bbs2 = zip(*bbs)
+    minx = min(bbs2[0])
+    maxx = max(bbs2[1])
+    miny = min(bbs2[2])
+    maxy = max(bbs2[3])
+    xdim = maxx-minx
+    ydim = maxy-miny
+    if not (xdim or ydim):
+        raise Error("Polygons have no extent in one direction!")
+    a = ydim / xdim
+    if not width and not height:
+        if a < 1.0:
+            width = 300
+        else:
+            height = 300
+    if width and not height:
+        height = width * a
+    if height and not width:
+        width = height / a
+    npoly = len(pp)
+    fill_color   = __RingBuffer(fill_color   or ('red', 'green', 'blue', 'yellow'))
+    fill_opacity = __RingBuffer(fill_opacity or (1.0,))
+    stroke_color = __RingBuffer(stroke_color or ('black',))
+    stroke_width = __RingBuffer(stroke_width or (1.0,))
+    s = ['<?xml version="1.0" encoding="iso-8859-1" standalone="no"?>',
+         '<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN" "http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd">',
+         '<svg xmlns="http://www.w3.org/2000/svg" width="%d" height="%d">' % (width, height)]
+    for i in range(npoly):
+        p = pp[i]
+        bb = bbs[i]
+        p.warpToBox(width*(bb[0]-minx)/xdim, width*(bb[1]-minx)/xdim,
+                    height*(bb[2]-miny)/ydim, height*(bb[3]-miny)/ydim)
+        subl = ['<path style="fill:%s;fill-opacity:%s;fill-rule:evenodd;stroke:%s;stroke-width:%s;" d="' %
+                (fill_color(), fill_opacity(), stroke_color(), stroke_width())]
+        for c in p:
+            subl.append('M %g, %g %s z ' % (c[0][0], c[0][1], ' '.join([("L %g, %g" % (a,b)) for a,b in c[1:]])))
+        subl.append('"/>')
+        s.append(''.join(subl))
+    s.append('</svg>')
+    f.write('\n'.join(s))
+    if cl: f.close()
+    return f
+
+
+def writeXML(ofile, polylist, withHeader=False):
+    """
+    Write a readable representation of the Polygons in polylist to a XML file. 
+    A simple header can be added to make the file parsable.
+
+    :Arguments:
+        - ofile: see above
+        - polylist: sequence of Polygons
+        - optional withHeader: bool
+    :Returns:
+        ofile object
+    """
+    f, cl = getWritableObject(ofile)
+    if withHeader:
+        f.write('<?xml version="1.0" encoding="iso-8859-1" standalone="no"?>\n')
+    for p in polylist:
+        l = ['<polygon contours="%d" area="%g" xMin="%g" xMax="%g" yMin="%g" yMax="%g">' % ((len(p), p.area())+p.boundingBox())]
+        for i, c in enumerate(p):
+            l.append('  <contour points="%d" isHole="%d" area="%g" xMin="%g" xMax="%g" yMin="%g" yMax="%g">' \
+                % ((len(c), p.isHole(i), p.area(i))+p.boundingBox(i)))
+            for po in c:
+                l.append('    <p x="%g" y="%g"/>' % po)
+            l.append('  </contour>')
+        l.append('</polygon>\n')
+        f.write('\n'.join(l))
+    if cl: f.close()
+    return f
+
+
+def readXML(ifile):
+    """
+    Read a list of Polygons from a XML file which was written with writeXML().
+        
+    :Arguments:
+        - ofile: see above
+    :Returns:
+        list of Polygon objects
+    """
+    f, cl = getReadableObject(ifile)
+    d = parseString(f.read())
+    if cl: f.close()
+    plist = []
+    for pn in d.getElementsByTagName('polygon'):
+        p = Polygon()
+        plist.append(p)
+        for sn in pn.childNodes:
+            if not sn.nodeType == Node.ELEMENT_NODE:
+                continue
+            assert sn.tagName == 'contour'
+            polist = []
+            for pon in sn.childNodes:
+                if not pon.nodeType == Node.ELEMENT_NODE:
+                    continue
+                polist.append((float(pon.getAttribute('x')), float(pon.getAttribute('y'))))
+            assert int(sn.getAttribute('points')) == len(polist)
+            p.addContour(polist, int(sn.getAttribute('isHole')))
+        assert int(pn.getAttribute('contours')) == len(p)
+    return plist
+
+
+if hasPDFExport:
+
+    def writePDF(ofile, polylist, pagesize=None, linewidth=0, fill_color=None):
+        """
+    *This function is only available if the reportlab package is installed!*
+    Write a the Polygons in polylist to a PDF file.
+
+    :Arguments:
+        - ofile: see above
+        - polylist: sequence of Polygons
+        - optional pagesize: 2-tuple of floats
+        - optional linewidth: float
+        - optional fill_color: color
+    :Returns:
+        ofile object
+    """
+        from reportlab.pdfgen import canvas
+        from reportlab.lib.colors import red, green, blue, yellow, black, white
+        if not pagesize:
+            from reportlab.lib.pagesizes import A4
+            pagesize = A4
+        can = canvas.Canvas(ofile, pagesize=pagesize)
+        can.setLineWidth(linewidth)
+        pp = [Polygon(p) for p in polylist] # use clones only
+        bbs = [p.boundingBox() for p in pp]
+        bbs2 = zip(*bbs)
+        minx = min(bbs2[0])
+        maxx = max(bbs2[1])
+        miny = min(bbs2[2])
+        maxy = max(bbs2[3])
+        xdim = maxx-minx
+        ydim = maxy-miny
+        if not (xdim or ydim):
+            raise Error("Polygons have no extent in one direction!")
+        a = ydim / xdim
+        width, height = pagesize
+        if a > (height/width):
+            width = height / a
+        else:
+            height = width * a
+        npoly = len(pp)
+        fill_color   = __RingBuffer(fill_color or (red, green, blue, yellow))
+        for i in range(npoly):
+            p = pp[i]
+            bb = bbs[i]
+            p.warpToBox(width*(bb[0]-minx)/xdim, width*(bb[1]-minx)/xdim,
+                        height*(bb[2]-miny)/ydim, height*(bb[3]-miny)/ydim)
+        for poly in pp:
+            solids = [poly[i] for i in range(len(poly)) if poly.isSolid(i)]
+            can.setFillColor(fill_color())
+            for c in solids:
+                p = can.beginPath()
+                p.moveTo(c[0][0], c[0][1])
+                for i in range(1, len(c)):
+                    p.lineTo(c[i][0], c[i][1])
+                p.close()
+                can.drawPath(p, stroke=1, fill=1)
+            holes = [poly[i] for i in range(len(poly)) if poly.isHole(i)]
+            can.setFillColor(white)
+            for c in holes:
+                p = can.beginPath()
+                p.moveTo(c[0][0], c[0][1])
+                for i in range(1, len(c)):
+                    p.lineTo(c[i][0], c[i][1])
+                p.close()
+                can.drawPath(p, stroke=1, fill=1)
+        can.showPage()
+        can.save()

Polygon/Shapes.py

+# -*- coding: utf-8 -*-
+#       $Id: Shapes.py 91 2010-09-29 18:40:19Z jraedler $  
+
+from cPolygon import Polygon
+from math import sin, cos, pi
+
+
+def Circle(radius=1.0, center=(0.0,0.0), points=32):
+    """
+    Create a polygonal approximation of a circle.
+
+    :Arguments:
+        - optional radius: float
+        - optional center: point (2-tuple of float)
+        - optional points: integer
+    :Returns:
+        new Polygon
+    """
+    p = []
+    for i in range(points):
+        a = 2.0*pi*float(i)/points
+        p.append((center[0]+radius*sin(a), center[1]+radius*cos(a)))
+    return Polygon(p)
+
+
+def Star(radius=1.0, center=(0.0,0.0), beams=16, iradius=0.5):
+    """
+    Create a star shape, iradius is the inner and radius the outer radius.
+
+    :Arguments:
+        - optional radius: float
+        - optional center: point (2-tuple of float)
+        - optional beams: integer
+        - optional iradius: float
+    :Returns:
+        new Polygon
+    """
+    p = []
+    for i in range(beams):
+        a = 2.0*pi*float(i)/beams
+        p.append((center[0]+radius*sin(a), center[1]+radius*cos(a)))
+        b = 2.0*pi*(float(i)+0.5)/beams
+        p.append((center[0]+iradius*sin(b), center[1]+iradius*cos(b)))
+    return Polygon(p)
+
+
+def Rectangle(xl= 1.0, yl=None):
+    """
+    Create a rectangular shape. If yl is not set, a square is created.
+
+    :Arguments:
+        - optional xl: float
+        - optional yl: float
+    :Returns:
+        new Polygon
+    """
+    if yl is None: yl = xl
+    return Polygon(((0.0, 0.0), (xl, 0.0), (xl, yl), (0.0, yl)))
+
+
+def __sierpinskiRec(c, box, level):
+    """
+    recursive function to cut out parts of the sierpinski carpet
+    """
+    if level <= 0:
+        return
+    w = (box[1]-box[0])/3.0
+    for i in range(3):
+        for j in range(3):
+            if i*j == 1:
+                c.addContour(((box[0]+w, box[2]+w), (box[1]-w, box[2]+w), (box[1]-w, box[3]-w), (box[0]+w, box[3]-w)), True)
+            else:
+                xmin = box[0]+i*w
+                xmax = xmin+w
+                ymin = box[2]+j*w
+                ymax = ymin+w
+                __sierpinskiRec(c, (xmin, xmax, ymin, ymax), level-1)
+
+
+def SierpinskiCarpet(width=1.0, level=5):
+    """
+    Create a sierpinski carpet.
+
+    ### DO NOT USE LEVELS > 6 UNLESS YOU KNOW WHAT YOU DO! ###
+
+    :Arguments:
+        - optional width: float (1.0)
+        - optional level: int (5)
+    :Returns:
+        new Polygon
+    """
+    carpet = Rectangle(width)
+    __sierpinskiRec(carpet, carpet.boundingBox(), level)
+    return carpet
+# -*- coding: utf-8 -*-
+#       $Id: Utils.py 98 2010-11-19 13:17:42Z jraedler $  
+
+from cPolygon import Polygon
+from math import sqrt, fabs, floor
+from operator import add
+from collections import defaultdict
+
+
+def fillHoles(poly):
+    """
+    Returns the polygon p without any holes.
+
+    :Arguments:
+        - p: Polygon
+    :Returns:
+        new Polygon
+    """
+    n = Polygon()
+    [n.addContour(poly[i]) for i in range(len(poly)) if poly.isSolid(i)]
+    return n
+
+
+def pointList(poly, withHoles=1):
+    """
+    Returns a list of all points of p.
+
+    :Arguments:
+        - p: Polygon
+    :Returns:
+        list of points
+    """
+    if not withHoles:
+        poly = fillHoles(poly)
+    return reduce(add, [list(c) for c in poly])
+
+
+__left = lambda p: (p[1][0]*p[2][1]+p[0][0]*p[1][1]+p[2][0]*p[0][1]-
+                    p[1][0]*p[0][1]-p[2][0]*p[1][1]-p[0][0]*p[2][1] >= 0)
+def convexHull(poly):
+    """
+    Returns a polygon which is the convex hull of p.
+
+    :Arguments:
+        - p: Polygon
+    :Returns:
+        new Polygon
+    """
+    points = list(pointList(poly, 0))
+    points.sort()
+    u = [points[0], points[1]]
+    for p in points[2:]:
+        u.append(p)
+        while len(u) > 2 and __left(u[-3:]):
+            del u[-2]
+    points.reverse()
+    l = [points[0], points[1]]
+    for p in points[2:]:
+        l.append(p)
+        while len(l) > 2 and __left(l[-3:]):
+            del l[-2]
+    return Polygon(u+l[1:-1])
+
+
+def tile(poly, x=[], y=[], bb=None):
+    """
+    Returns a list of polygons which are tiles of p splitted at the border values 
+    specified in x and y. If you already know the bounding box of p, you may give 
+    it as argument bb (4-tuple) to speed up the calculation.
+
+    :Arguments:
+        - p: Polygon
+        - x: list of floats
+        - y: list of floats
+        - optional bb: tuple of 4 floats
+    :Returns:
+        list of new Polygons
+    """
+    if not (x or y):
+        return [poly] # nothin' to do
+    bb = bb or poly.boundingBox()
+    x = [bb[0]] + [i for i in x if bb[0] < i < bb[1]] + [bb[1]]
+    y = [bb[2]] + [j for j in y if bb[2] < j < bb[3]] + [bb[3]]
+    x.sort()
+    y.sort()
+    cutpoly = []
+    for i in range(len(x)-1):
+        for j in range(len(y)-1):
+            cutpoly.append(Polygon(((x[i],y[j]),(x[i],y[j+1]),(x[i+1],y[j+1]),(x[i+1],y[j]))))
+    tmp = [c & poly for c in cutpoly]
+    return [p for p in tmp if p]
+
+
+def tileEqual(poly, nx=1, ny=1, bb=None):
+    """
+    works like tile(), but splits into nx and ny parts.
+
+    :Arguments:
+        - p: Polygon
+        - nx: integer
+        - ny: integer
+        - optional bb: tuple of 4 floats
+    :Returns:
+        list of new Polygons
+    """
+    bb = bb or poly.boundingBox()
+    s0, s1 = bb[0], bb[2]
+    a0, a1 = (bb[1]-bb[0])/nx, (bb[3]-bb[2])/ny 
+    return tile(poly, [s0+a0*i for i in range(1, nx)], [s1+a1*i for i in range(1, ny)], bb)
+
+
+def warpToOrigin(poly):
+    """
+    Shifts lower left corner of the bounding box to origin.
+
+    :Arguments:
+        - p: Polygon
+    :Returns:
+        None
+    """
+    x0, x1, y0, y1 = poly.boundingBox()
+    poly.shift(-x0, -y0)
+
+
+def centerAroundOrigin(poly):
+    """
+    Shifts the center of the bounding box to origin.
+
+    :Arguments:
+        - p: Polygon
+    :Returns:
+        None
+    """
+    x0, x1, y0, y1 = poly.boundingBox()
+    poly.shift(-0.5*(x0+x1), -0.5*(y0+y1))
+
+
+__vImp = lambda p: ((sqrt((p[1][0]-p[0][0])**2 + (p[1][1]-p[0][1])**2) +
+                     sqrt((p[2][0]-p[1][0])**2 + (p[2][1]-p[1][1])**2)) *
+                    fabs(p[1][0]*p[2][1]+p[0][0]*p[1][1]+p[2][0]*p[0][1]-
+                              p[1][0]*p[0][1]-p[2][0]*p[1][1]-p[0][0]*p[2][1]))
+def reducePoints(cont, n):
+    """
+    Remove points of the contour 'cont', return a new contour with 'n' points.
+    *Very simple* approach to reduce the number of points of a contour. Each point 
+    gets an associated 'value of importance' which is the product of the lengths 
+    and absolute angle of the left and right vertex. The points are sorted by this 
+    value and the n most important points are returned. This method may give 
+    *very* bad results for some contours like symmetric figures. It may even 
+    produce self-intersecting contours which are not valid to process with 
+    this module.
+
+    :Arguments:
+        - contour: list of points
+    :Returns:
+        new list of points
+    """
+    if n >= len(cont):
+        return cont
+    cont = list(cont)
+    cont.insert(0, cont[-1])
+    cont.append(cont[1])
+    a = [(__vImp(cont[i-1:i+2]), i) for i in range(1, len(cont)-1)]
+    a.sort()
+    ind = [x[1] for x in a[len(cont)-n-2:]]
+    ind.sort()
+    return [cont[i] for i in ind]
+
+
+__linVal = lambda p: (p[1][0]-p[0][0])*(p[2][1]-p[0][1])-(p[1][1]-p[0][1])*(p[2][0]-p[0][0])
+def prunePoints(poly):
+    """
+    Returns a new Polygon which has exactly the same shape as p, but unneeded 
+    points are removed. The new Polygon has no double points or points that are 
+    exactly on a straight line.
+
+    :Arguments:
+        - p: Polygon
+    :Returns:
+        new Polygon
+    """
+    np = Polygon()
+    for x in range(len(poly)): # loop over contours
+        c = list(poly[x])
+        c.insert(0, c[-1])
+        c.append(c[1])
+        # remove double points
+        i = 1
+        while (i < (len(c))):
+            if c[i] == c[i-1]:
+                del c[i]
+            else:
+                i += 1
+        # remove points that are on a straight line
+        n = []
+        for i in range(1, len(c)-1):
+            if __linVal(c[i-1:i+2]) != 0.0:
+                n.append(c[i])
+        if len(n) > 2:
+            np.addContour(n, poly.isHole(x))
+    return np
+                
+
+def cloneGrid(poly, con, xl, yl, xstep, ystep):
+    """
+    Create a single new polygon with contours that are made from contour con from 
+    polygon poly arranged in a xl-yl-grid with spacing xstep and ystep.
+
+    :Arguments:
+        - poly: Polygon
+        - con: integer
+        - xl: integer
+        - yl: integer
+        - xstep: float
+        - ystep: float
+    :Returns:
+        new Polygon
+    """
+    p = Polygon(poly[con])
+    for xi in range(xl):
+        for yi in range(yl):
+            p.cloneContour(0, xi*xstep, yi*ystep)
+    return p
+
+
+#
+# following functions are contributed by Josiah Carlson <josiah.carlson@gmail.com>
+#
+# the tileBSP() function is much faster for large polygons and a large number 
+# of tiles than the original tile()
+#
+# background information can be found at:
+#       http://dr-josiah.blogspot.com/2010/08/binary-space-partitions-and-you.html
+# the original code is located here:
+#       http://gist.github.com/560298
+#
+
+def _find_split(count_dict):
+    '''
+    When provided a dictionary of counts for the number of points inside each
+    of the unit grid rows/columns, this function will return the best column
+    choice so as to come closest to cutting the points in half.  It will also
+    return the score, lower being better.
+
+    Returns: (cutoff, score)
+    '''
+    # find the prefix sums
+    tmp = {}
+    for i in xrange(min(count_dict), max(count_dict)+1):
+        tmp[i] = tmp.get(i-1, 0) + count_dict.get(i, 0)
+    by_index = sorted(tmp.items())
+    # the target number of points
+    midpoint = by_index[-1][1] // 2
+    # calculate how far off from the target number each choice would be
+    totals = []
+    for i in xrange(1, len(by_index)):
+        totals.append(abs(by_index[i-1][1] - midpoint))
+    # choose the best target number
+    mi = min(totals)
+    index = totals.index(mi)
+    return by_index[index+1][0], totals[index]
+
+
+def _single_poly(polygon, dim, maxv):
+    for poly in polygon:
+        if max(pt[dim] for pt in poly) > maxv:
+            return False
+    return True
+
+
+def tileBSP(p):
+    """
+    This generator function returns tiles of a polygon. It will be much 
+    more efficient for larger polygons and a large number of tiles than the 
+    original tile() function. For a discussion see:
+        http://dr-josiah.blogspot.com/2010/08/binary-space-partitions-and-you.html
+
+    :Arguments:
+        - p: Polygon
+    :Returns:
+        tiles of the Polygon p on the integer grid
+    """
+    _int = int
+    _floor = floor
+
+    work = [p]
+    while work:
+        # we'll use an explicit stack to ensure that degenerate polygons don't
+        # blow the system recursion limit
+        polygon = work.pop()
+
+        # find out how many points are in each row/column of the grid
+        xs = defaultdict(_int)
+        ys = defaultdict(_int)
+        for poly in polygon:
+            for x,y in poly:
+                xs[_int(_floor(x))] += 1
+                ys[_int(_floor(y))] += 1
+
+        # handle empty polygons gracefully
+        if not xs:
+            continue
+
+        # handle top and right-edge border points
+        mvx = max(max(x for x,y in poly) for poly in polygon)
+        vx = _int(_floor(mvx))
+        if len(xs) > 1 and mvx == vx:
+            xs[vx-1] += xs.pop(vx, 0)
+        mvy = max(max(y for x,y in poly) for poly in polygon)
+        vy = _int(_floor(mvy))
+        if len(ys) > 1 and mvy == vy:
+            ys[vy-1] += ys.pop(vy, 0)
+
+        # we've got a single grid, yield it
+        if len(xs) == len(ys) == 1:
+            yield polygon
+            continue
+
+        # find the split
+        if len(xs) < 2:
+            spx, countx = xs.items()[0]
+            countx *= 3
+        else:
+            spx, countx = _find_split(xs)
+        if len(ys) < 2:
+            spy, county = ys.items()[0]
+            county *= 3
+        else:
+            spy, county = _find_split(ys)
+
+        # get the grid bounds for the split
+        minx = min(xs)
+        maxx = max(xs)
+        miny = min(ys)
+        maxy = max(ys)
+
+        # actually split the polygon and put the results back on the work
+        # stack
+        if (countx < county and not _single_poly(polygon, 0, minx + 1.0)) or _single_poly(polygon, 1, miny + 1.0):
+            work.append(polygon &
+                Polygon([(minx, miny), (minx, maxy+1),
+                         (spx, maxy+1), (spx, miny)]))
+            work.append(polygon &
+                Polygon([(spx, miny), (spx, maxy+1),
+                         (maxx+1, maxy+1), (maxx+1, miny)]))
+        else:
+            work.append(polygon &
+                Polygon([(minx, miny), (minx, spy),
+                         (maxx+1, spy), (maxx+1, miny)]))
+            work.append(polygon &
+                Polygon([(minx, spy), (minx, maxy+1),
+                         (maxx+1, maxy+1), (maxx+1, spy)]))
+
+        # Always recurse on the smallest set, which is a trick to ensure that
+        # the stack size is O(log n) .
+        if work[-2].nPoints() < work[-1].nPoints():
+            work.append(work.pop(-2))
+
+
+def gpfInfo(fileName):
+    """
+    Get information on a gpc/gpf file.
+
+    :Arguments:
+        - fileName: name of the file to read
+    :Returns:
+        - contours: number of contours
+        - holes: number of holes (if contained)
+        - points: total number of points
+        - withHoles: file contains hole-flags
+    """
+    f = open(fileName, 'r')
+    contours = int(f.readline())
+    holes  = 0
+    points = 0
+    withHoles = True
+    for c in range(contours):
+        pp = int(f.readline())
+        x = 0
+        if c == 0:
+            # check for hole-flags
+            try:
+                holes += int(f.readline())
+            except:
+                withHoles = False
+                x = 1
+        else:
+            if withHoles:
+                holes += int(f.readline())
+        [ f.readline() for p in range(pp-x) ]
+        points += pp
+
+    return contours, holes, points, withHoles

Polygon/__init__.py

+# -*- coding: utf-8 -*-
+#       $Id: __init__.py 91 2010-09-29 18:40:19Z jraedler $  
+
+
+# import everything from cPolygon
+from cPolygon import *
+
+# keep namespace clean
+__version__ = version
+__author__  = author
+__license__ = license
+del version, author, license
+
+
+# support functions for pickling and unpickling
+def __createPolygon(contour, hole):
+    """rebuild Polygon from pickled data"""
+    p = Polygon()
+    map(p.addContour, contour, hole)
+    return p
+
+
+def __tuples(a):
+    """map an array or list of lists to a tuple of tuples"""
+    return tuple(map(tuple, a))
+
+
+def __reducePolygon(p):
+    """return pickle data for Polygon """
+    return (__createPolygon, (tuple([__tuples(x) for x in p]), p.isHole()))
+
+
+import copy_reg
+copy_reg.constructor(__createPolygon)
+copy_reg.pickle(Polygon, __reducePolygon)
+del copy_reg
+
+Please look at Polygon.txt or Polygon.pdf in the folder doc.
+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+
+from Polygon import *
+from Polygon.Shapes import Star, Circle, Rectangle, SierpinskiCarpet
+from Polygon.IO import *
+from Polygon.Utils import convexHull, tile, tileEqual, tileBSP, reducePoints, cloneGrid
+import random, math
+
+
+def operationsExample():
+    # create a circle with a hole
+    p1 = Circle(1.0) - Circle(0.5)
+    # create a square
+    p2 = Rectangle(0.7)
+    # shift the square a little bit
+    p2.shift(0.25, 0.35)
+    plist = [p1, p2]
+
+    # addition, the same as logical OR (p1 | p2)
+    p = p1 + p2
+    p.shift(2.5, 0.0)
+    plist.append(p)
+
+    # subtraction
+    p = p1 - p2
+    p.shift(5.0, 0.0)
+    plist.append(p)
+
+    # subtraction
+    p = p2 - p1
+    p.shift(7.5, 0.0)
+    plist.append(p)
+
+    # logical AND
+    p = p2 & p1
+    p.shift(10.0, 0.0)
+    plist.append(p)
+
+    # logical XOR
+    p = p2 ^ p1
+    p.shift(12.5, 0.0)
+    plist.append(p)
+
+    # draw the results of the operations
+    writeSVG('Operations.svg', plist, width=800)
+
+
+def cookieExample():
+    # construct a christmas cookie with the help of the shapes
+    star   = Star(radius=2.0, center=(1.0, 3.0), beams=5, iradius=1.4)
+    circle = Circle(radius=1.0, center=(1.0, 3.0), points=64)
+    cookie = star-circle
+    # shift star and circle to the right to plot all polygons
+    # on one page
+    star.shift(5.0, 0.0)
+    circle.shift(10.0, 0.0)
+    # plot all three to an svg file
+    writeSVG('Cookie.svg', (cookie, star, circle))
+
+    # break a polygon object into a list of polygons by arranging
+    # it on tiles
+    # tile into 3x3 parts
+    plist = tileEqual(cookie, 3, 3)
+    writeSVG('CookieTiled1.svg', plist)
+    # test tile at x = 0.3, 0.5 and y = 2.7, 3.1
+    plist = tile(cookie, [0.3, 0.5], [2.7, 3.1])
+    writeSVG('CookieTiled2.svg', plist)
+
+    # let's simulate an explosion, move all parts away
+    # from the cookie's center, small parts are faster
+    xc, yc = cookie.center()
+    for p in plist:
+        if p:
+            # speed/distance
+            dval = 0.1 / p.area()
+            x, y = p.center()
+            # move the part a little bit
+            p.shift(dval*(x-xc), dval*(y-yc))
+            # and rotate it slightly ;-)
+            p.rotate(0.2*math.pi*(random.random()-0.5))
+    writeSVG('CookieExploded.svg', plist)
+    
+
+def reduceExample():
+    # read Polygon from file
+    p = Polygon('testpoly.gpf')
+    # use ireland only, I know it's contour 0
+    pnew = Polygon(p[0])
+    # number of points
+    l = len(pnew[0])
+    # get shift value to show many polygons in drawing
+    bb = pnew.boundingBox()
+    xs = 1.1 * (bb[1]-bb[0])
+    # list with polygons to plot
+    plist = [pnew]
+    while l > 30:
+        # reduce points to the half
+        l /= 2
+        print 'Reducing contour to %d points' % l
+        pnew = Polygon(reducePoints(pnew[0], l))
+        pnew.shift(xs, 0)
+        plist.append(pnew)
+    # draw the results
+    writeSVG('ReducePoints.svg', plist, height=400)
+    if hasPDFExport:
+        writePDF('ReducePoints.pdf', plist)
+
+
+def moonExample():
+    # a high-resolution, softly flickering moon,
+    # constructed by the difference of two stars ...
+    moon = Star(radius=3, center=(1.0, 2.0), beams=140, iradius=2.90) \
+           - Star(radius=3, center=(-0.3, 2.0), beams=140, iradius=2.90)
+    # plot the moon and its convex hull
+    writeSVG('MoonAndHull.svg', (moon, convexHull(moon)), height=400, fill_opacity=(1.0, 0.3))
+    # test point containment
+    d = ['outside', 'inside']
+    c = moon.center()
+    print 'Did you know that the center of gravitation of my moon is %s?' % d[moon.isInside(c[0], c[1])]
+
+
+def xmlExample():
+    cookie = Star(radius=2.0, center=(1.0, 3.0), beams=5, iradius=1.4)\
+        - Circle(radius=1.0, center=(1.0, 3.0))
+    writeXML('cookie.xml', (cookie, ), withHeader=True)
+    p = readXML('cookie.xml')
+    
+
+def gnuplotExample():
+    cookie = Star(radius=2.0, center=(1.0, 3.0), beams=5, iradius=1.4)\
+        - Circle(radius=1.0, center=(1.0, 3.0))
+    writeGnuplot('cookie.gp', (cookie,))
+    writeGnuplotTriangles('cookieTri.gp', (cookie,))
+
+
+def gridExample():
+    starGrid = cloneGrid(Star(beams=5), 0, 20, 20, 4, 4)
+    starGrid.shift(-50, -50)
+    cookie = Star(radius=30.0, beams=5, iradius=20.0) - Circle(radius=15.0)
+    starCookie = cookie - starGrid
+    writeSVG('StarCookie.svg', (starCookie,))
+    if hasPDFExport:
+        writePDF('StarCookie.pdf', (starCookie,))
+
+
+def sierpinskiExample():
+    for l in range(7):
+        s = SierpinskiCarpet(level=l)
+        print "SIERPINSKI CARPET - Level: %2d - Contours: %7d - Area: %g" % (l, len(s), s.area())
+        writeSVG('Sierpinski_%02d.svg' % l, (s,))
+
+
+def tileBSPExample():
+    # read Polygon from file
+    p = Polygon('testpoly.gpf')
+    print "tileBSP() - may need some time..." ,
+    # generate a list of tiles
+    tiles = list(tileBSP(p))
+    # write results
+    writeSVG('tileBSP.svg', tiles)
+    if hasPDFExport:
+        writePDF('tileBSP.pdf', tiles)
+    print "done!"
+
+
+if __name__ == '__main__':
+    operationsExample()
+    cookieExample()
+    reduceExample()
+    gridExample()
+    moonExample()
+    xmlExample()
+    gnuplotExample()
+    sierpinskiExample()
+    tileBSPExample()
+%PDF-1.3
+%���� ReportLab Generated PDF document http://www.reportlab.com
+% 'BasicFonts': class PDFDictionary 
+1 0 obj
+% The standard fonts dictionary
+<< /F1 2 0 R
+ /F2 3 0 R
+ /F3 4 0 R
+ /F4 9 0 R
+ /F5 11 0 R
+ /F6 19 0 R >>
+endobj
+% 'F1': class PDFType1Font 
+2 0 obj
+% Font Helvetica
+<< /BaseFont /Helvetica
+ /Encoding /WinAnsiEncoding
+ /Name /F1
+ /Subtype /Type1
+ /Type /Font >>
+endobj
+% 'F2': class PDFType1Font 
+3 0 obj
+% Font Helvetica-Bold
+<< /BaseFont /Helvetica-Bold
+ /Encoding /WinAnsiEncoding
+ /Name /F2
+ /Subtype /Type1
+ /Type /Font >>
+endobj
+% 'F3': class PDFType1Font 
+4 0 obj
+% Font Times-Roman
+<< /BaseFont /Times-Roman
+ /Encoding /WinAnsiEncoding
+ /Name /F3
+ /Subtype /Type1
+ /Type /Font >>
+endobj
+% 'Annot.NUMBER1': class PDFDictionary 
+5 0 obj
+<< /A << /S /URI
+ /Type /Action
+ /URI (mailto:joerg@j-raedler.de) >>
+ /Border [ 0
+ 0
+ 0 ]
+ /Rect [ 225.1523
+ 579.5936
+ 308.1023
+ 591.5936 ]
+ /Subtype /Link
+ /Type /Annot >>
+endobj
+% 'Annot.NUMBER2': class PDFDictionary 
+6 0 obj
+<< /A << /S /URI
+ /Type /Action
+ /URI (http://www.j-raedler.de/projects/polygon) >>
+ /Border [ 0
+ 0
+ 0 ]
+ /Rect [ 218.4223
+ 501.5936
+ 394.0423
+ 513.5936 ]
+ /Subtype /Link
+ /Type /Annot >>
+endobj
+% 'Annot.NUMBER3': class PDFDictionary 
+7 0 obj
+<< /A << /S /URI
+ /Type /Action
+ /URI (http://www.cs.man.ac.uk/~toby/alan/software/) >>
+ /Border [ 0
+ 0
+ 0 ]
+ /Rect [ 198.4123
+ 483.5936
+ 399.3323
+ 495.5936 ]
+ /Subtype /Link
+ /Type /Annot >>
+endobj
+% 'Page1': class PDFPage 
+8 0 obj
+% Page dictionary
+<< /Annots [ 5 0 R
+ 6 0 R
+ 7 0 R ]
+ /Contents 89 0 R
+ /MediaBox [ 0
+ 0
+ 595.2756
+ 841.8898 ]
+ /Parent 88 0 R
+ /Resources << /Font 1 0 R
+ /ProcSet [ /PDF
+ /Text
+ /ImageB
+ /ImageC
+ /ImageI ] >>
+ /Rotate 0
+ /Trans <<  >>
+ /Type /Page >>
+endobj
+% 'F4': class PDFType1Font 
+9 0 obj
+% Font Courier
+<< /BaseFont /Courier
+ /Encoding /WinAnsiEncoding
+ /Name /F4
+ /Subtype /Type1
+ /Type /Font >>
+endobj
+% 'Page2': class PDFPage 
+10 0 obj
+% Page dictionary
+<< /Contents 90 0 R
+ /MediaBox [ 0
+ 0
+ 595.2756
+ 841.8898 ]
+ /Parent 88 0 R
+ /Resources << /Font 1 0 R
+ /ProcSet [ /PDF
+ /Text
+ /ImageB
+ /ImageC
+ /ImageI ] >>
+ /Rotate 0
+ /Trans <<  >>
+ /Type /Page >>
+endobj
+% 'F5': class PDFType1Font 
+11 0 obj
+% Font Helvetica-BoldOblique
+<< /BaseFont /Helvetica-BoldOblique
+ /Encoding /WinAnsiEncoding
+ /Name /F5
+ /Subtype /Type1
+ /Type /Font >>
+endobj
+% 'Page3': class PDFPage 
+12 0 obj
+% Page dictionary
+<< /Contents 91 0 R
+ /MediaBox [ 0
+ 0
+ 595.2756
+ 841.8898 ]
+ /Parent 88 0 R
+ /Resources << /Font 1 0 R
+ /ProcSet [ /PDF
+ /Text
+ /ImageB
+ /ImageC
+ /ImageI ] >>
+ /Rotate 0
+ /Trans <<  >>
+ /Type /Page >>
+endobj
+% 'Page4': class PDFPage 
+13 0 obj
+% Page dictionary
+<< /Contents 92 0 R
+ /MediaBox [ 0
+ 0
+ 595.2756
+ 841.8898 ]
+ /Parent 88 0 R
+ /Resources << /Font 1 0 R
+ /ProcSet [ /PDF
+ /Text
+ /ImageB
+ /ImageC
+ /ImageI ] >>
+ /Rotate 0
+ /Trans <<  >>
+ /Type /Page >>
+endobj
+% 'Page5': class PDFPage 
+14 0 obj
+% Page dictionary
+<< /Contents 93 0 R
+ /MediaBox [ 0
+ 0
+ 595.2756
+ 841.8898 ]
+ /Parent 88 0 R
+ /Resources << /Font 1 0 R
+ /ProcSet [ /PDF
+ /Text
+ /ImageB
+ /ImageC
+ /ImageI ] >>
+ /Rotate 0
+ /Trans <<  >>
+ /Type /Page >>
+endobj
+% 'Page6': class PDFPage 
+15 0 obj
+% Page dictionary
+<< /Contents 94 0 R
+ /MediaBox [ 0
+ 0
+ 595.2756
+ 841.8898 ]
+ /Parent 88 0 R
+ /Resources << /Font 1 0 R
+ /ProcSet [ /PDF
+ /Text
+ /ImageB
+ /ImageC
+ /ImageI ] >>
+ /Rotate 0
+ /Trans <<  >>
+ /Type /Page >>
+endobj
+% 'Page7': class PDFPage 
+16 0 obj
+% Page dictionary
+<< /Contents 95 0 R
+ /MediaBox [ 0
+ 0
+ 595.2756
+ 841.8898 ]
+ /Parent 88 0 R
+ /Resources << /Font 1 0 R
+ /ProcSet [ /PDF
+ /Text
+ /ImageB
+ /ImageC
+ /ImageI ] >>
+ /Rotate 0
+ /Trans <<  >>
+ /Type /Page >>
+endobj
+% 'Page8': class PDFPage 
+17 0 obj
+% Page dictionary
+<< /Contents 96 0 R
+ /MediaBox [ 0
+ 0
+ 595.2756
+ 841.8898 ]
+ /Parent 88 0 R
+ /Resources << /Font 1 0 R
+ /ProcSet [ /PDF
+ /Text
+ /ImageB
+ /ImageC
+ /ImageI ] >>
+ /Rotate 0
+ /Trans <<  >>
+ /Type /Page >>
+endobj
+% 'Page9': class PDFPage 
+18 0 obj
+% Page dictionary
+<< /Contents 97 0 R
+ /MediaBox [ 0
+ 0
+ 595.2756
+ 841.8898 ]
+ /Parent 88 0 R
+ /Resources << /Font 1 0 R
+ /ProcSet [ /PDF
+ /Text
+ /ImageB
+ /ImageC
+ /ImageI ] >>
+ /Rotate 0
+ /Trans <<  >>
+ /Type /Page >>
+endobj
+% 'F6': class PDFType1Font 
+19 0 obj
+% Font Helvetica-Oblique
+<< /BaseFont /Helvetica-Oblique
+ /Encoding /WinAnsiEncoding
+ /Name /F6
+ /Subtype /Type1
+ /Type /Font >>
+endobj
+% 'Page10': class PDFPage 
+20 0 obj
+% Page dictionary
+<< /Contents 98 0 R
+ /MediaBox [ 0
+ 0
+ 595.2756
+ 841.8898 ]
+ /Parent 88 0 R
+ /Resources << /Font 1 0 R
+ /ProcSet [ /PDF
+ /Text
+ /ImageB
+ /ImageC
+ /ImageI ] >>
+ /Rotate 0
+ /Trans <<  >>
+ /Type /Page >>
+endobj
+% 'Page11': class PDFPage 
+21 0 obj
+% Page dictionary
+<< /Contents 99 0 R
+ /MediaBox [ 0
+ 0
+ 595.2756
+ 841.8898 ]
+ /Parent 88 0 R
+ /Resources << /Font 1 0 R
+ /ProcSet [ /PDF
+ /Text
+ /ImageB
+ /ImageC
+ /ImageI ] >>
+ /Rotate 0
+ /Trans <<  >>
+ /Type /Page >>
+endobj
+% 'Annot.NUMBER4': class PDFDictionary 
+22 0 obj
+<< /A << /S /URI
+ /Type /Action
+ /URI (http://dr-josiah.blogspot.com/2010/08/binary-space-partitions-and-you.html) >>
+ /Border [ 0
+ 0
+ 0 ]
+ /Rect [ 62.69291
+ 363.5936
+ 392.2729
+ 375.5936 ]
+ /Subtype /Link
+ /Type /Annot >>
+endobj
+% 'Page12': class PDFPage 
+23 0 obj
+% Page dictionary
+<< /Annots [ 22 0 R ]
+ /Contents 100 0 R
+ /MediaBox [ 0
+ 0
+ 595.2756
+ 841.8898 ]
+ /Parent 88 0 R
+ /Resources << /Font 1 0 R
+ /ProcSet [ /PDF
+ /Text
+ /ImageB
+ /ImageC
+ /ImageI ] >>
+ /Rotate 0
+ /Trans <<  >>
+ /Type /Page >>
+endobj
+% 'R24': class PDFCatalog 
+24 0 obj
+% Document Root
+<< /Outlines 26 0 R
+ /PageLabels 101 0 R
+ /PageMode /UseNone
+ /Pages 88 0 R
+ /Type /Catalog >>
+endobj
+% 'R25': class PDFInfo 
+25 0 obj
+<< /Author ()
+ /CreationDate (D:20101121151515-01'00')
+ /Keywords ()
+ /Producer (ReportLab http://www.reportlab.com)
+ /Subject (\(unspecified\))
+ /Title (Polygon \205 a Python package for handling 2D-polygons) >>
+endobj
+% 'R26': class PDFOutlines 
+26 0 obj
+<< /Count 68
+ /First 27 0 R
+ /Last 33 0 R
+ /Type /Outlines >>
+endobj
+% 'Outline.0': class OutlineEntryObject 
+27 0 obj
+<< /Count 1
+ /Dest [ 8 0 R
+ /XYZ
+ 62.69291
+ 705.0236
+ 0 ]
+ /First 28 0 R
+ /Last 28 0 R
+ /Next 29 0 R
+ /Parent 26 0 R
+ /Title (Introduction) >>
+endobj
+% 'Outline.62.0': class OutlineEntryObject 
+28 0 obj
+<< /Dest [ 8 0 R
+ /XYZ
+ 62.69291
+ 300.0236
+ 0 ]
+ /Parent 27 0 R
+ /Title (Platforms and Dependencies) >>
+endobj
+% 'Outline.1': class OutlineEntryObject 
+29 0 obj
+<< /Count 2
+ /Dest [ 8 0 R
+ /XYZ
+ 62.69291
+ 198.0236
+ 0 ]
+ /First 30 0 R
+ /Last 31 0 R
+ /Next 32 0 R
+ /Parent 26 0 R
+ /Prev 27 0 R
+ /Title (Installation) >>
+endobj
+% 'Outline.63.0': class OutlineEntryObject 
+30 0 obj
+<< /Dest [ 8 0 R
+ /XYZ
+ 62.69291
+ 165.0236
+ 0 ]
+ /Next 31 0 R
+ /Parent 29 0 R
+ /Title (Binaries) >>
+endobj
+% 'Outline.63.1': class OutlineEntryObject 
+31 0 obj
+<< /Dest [ 10 0 R
+ /XYZ
+ 62.69291
+ 765.0236
+ 0 ]
+ /Parent 29 0 R
+ /Prev 30 0 R
+ /Title (From Source) >>
+endobj
+% 'Outline.2': class OutlineEntryObject 
+32 0 obj
+<< /Dest [ 10 0 R
+ /XYZ
+ 62.69291
+ 651.0236
+ 0 ]
+ /Next 33 0 R
+ /Parent 26 0 R
+ /Prev 29 0 R
+ /Title (Basic Example) >>
+endobj
+% 'Outline.3': class OutlineEntryObject 
+33 0 obj
+<< /Count 54
+ /Dest [ 10 0 R
+ /XYZ
+ 62.69291
+ 536.8236
+ 0 ]
+ /First 34 0 R
+ /Last 76 0 R
+ /Parent 26 0 R
+ /Prev 32 0 R
+ /Title (Contents and Usage) >>
+endobj
+% 'Outline.64.0': class OutlineEntryObject 
+34 0 obj
+<< /Count 27
+ /Dest [ 10 0 R
+ /XYZ
+ 62.69291
+ 473.8236
+ 0 ]
+ /First 35 0 R
+ /Last 61 0 R
+ /Next 62 0 R
+ /Parent 33 0 R
+ /Title (Main module: the Polygon Class) >>
+endobj
+% 'Outline.65.0': class OutlineEntryObject 
+35 0 obj
+<< /Dest [ 12 0 R
+ /XYZ
+ 62.69291
+ 765.0236
+ 0 ]
+ /Next 36 0 R
+ /Parent 34 0 R
+ /Title (Operations on Polygon Objects) >>
+endobj
+% 'Outline.65.1': class OutlineEntryObject 
+36 0 obj
+<< /Dest [ 12 0 R
+ /XYZ
+ 62.69291
+ 594.0236
+ 0 ]
+ /Next 37 0 R
+ /Parent 34 0 R
+ /Prev 35 0 R
+ /Title (Polygon\(|arg\)) >>
+endobj
+% 'Outline.65.2': class OutlineEntryObject 
+37 0 obj
+<< /Dest [ 12 0 R
+ /XYZ
+ 62.69291
+ 435.0236
+ 0 ]
+ /Next 38 0 R
+ /Parent 34 0 R
+ /Prev 36 0 R
+ /Title (p.addContour\(c |, hole=0\)) >>
+endobj
+% 'Outline.65.3': class OutlineEntryObject 
+38 0 obj
+<< /Dest [ 12 0 R
+ /XYZ
+ 62.69291
+ 324.0236
+ 0 ]
+ /Next 39 0 R
+ /Parent 34 0 R
+ /Prev 37 0 R
+ /Title (p.contour\(i\)) >>
+endobj
+% 'Outline.65.4': class OutlineEntryObject 
+39 0 obj
+<< /Dest [ 12 0 R
+ /XYZ
+ 62.69291
+ 231.0236
+ 0 ]
+ /Next 40 0 R
+ /Parent 34 0 R
+ /Prev 38 0 R
+ /Title (p.isHole\(|i\)) >>
+endobj
+% 'Outline.65.5': class OutlineEntryObject 
+40 0 obj
+<< /Dest [ 12 0 R
+ /XYZ
+ 62.69291
+ 126.0236
+ 0 ]
+ /Next 41 0 R
+ /Parent 34 0 R
+ /Prev 39 0 R
+ /Title (p.isSolid\(|i\)) >>
+endobj
+% 'Outline.65.6': class OutlineEntryObject 
+41 0 obj
+<< /Dest [ 13 0 R
+ /XYZ
+ 62.69291
+ 705.0236
+ 0 ]
+ /Next 42 0 R
+ /Parent 34 0 R
+ /Prev 40 0 R
+ /Title (p.nPoints\(|i\)) >>
+endobj
+% 'Outline.65.7': class OutlineEntryObject 
+42 0 obj
+<< /Dest [ 13 0 R
+ /XYZ
+ 62.69291
+ 600.0236
+ 0 ]
+ /Next 43 0 R
+ /Parent 34 0 R
+ /Prev 41 0 R
+ /Title (p.read\(file\)) >>
+endobj
+% 'Outline.65.8': class OutlineEntryObject 
+43 0 obj
+<< /Dest [ 13 0 R
+ /XYZ
+ 62.69291
+ 465.0236
+ 0 ]
+ /Next 44 0 R
+ /Parent 34 0 R
+ /Prev 42 0 R
+ /Title (p.write\(file\)) >>
+endobj
+% 'Outline.65.9': class OutlineEntryObject 
+44 0 obj
+<< /Dest [ 13 0 R
+ /XYZ
+ 62.69291
+ 354.0236
+ 0 ]
+ /Next 45 0 R
+ /Parent 34 0 R
+ /Prev 43 0 R
+ /Title (p.simplify\(\)) >>
+endobj
+% 'Outline.65.10': class OutlineEntryObject 
+45 0 obj
+<< /Dest [ 13 0 R
+ /XYZ
+ 62.69291
+ 237.0236
+ 0 ]
+ /Next 46 0 R
+ /Parent 34 0 R
+ /Prev 44 0 R
+ /Title (p.area\(|i\)) >>
+endobj
+% 'Outline.65.11': class OutlineEntryObject 
+46 0 obj
+<< /Dest [ 13 0 R
+ /XYZ
+ 62.69291
+ 132.0236
+ 0 ]
+ /Next 47 0 R
+ /Parent 34 0 R
+ /Prev 45 0 R
+ /Title (p.center\(|i\)) >>
+endobj
+% 'Outline.65.12': class OutlineEntryObject 
+47 0 obj
+<< /Dest [ 14 0 R
+ /XYZ
+ 62.69291
+ 711.0236
+ 0 ]
+ /Next 48 0 R
+ /Parent 34 0 R
+ /Prev 46 0 R
+ /Title (p.orientation\(|i\)) >>
+endobj
+% 'Outline.65.13': class OutlineEntryObject 
+48 0 obj
+<< /Dest [ 14 0 R
+ /XYZ
+ 62.69291
+ 606.0236
+ 0 ]
+ /Next 49 0 R
+ /Parent 34 0 R
+ /Prev 47 0 R
+ /Title (p.isInside\(x, y |, i\)) >>
+endobj
+% 'Outline.65.14': class OutlineEntryObject 
+49 0 obj
+<< /Dest [ 14 0 R
+ /XYZ
+ 62.69291
+ 465.0236
+ 0 ]
+ /Next 50 0 R
+ /Parent 34 0 R
+ /Prev 48 0 R
+ /Title (p.covers\(q\)) >>
+endobj
+% 'Outline.65.15': class OutlineEntryObject 
+50 0 obj
+<< /Dest [ 14 0 R
+ /XYZ
+ 62.69291
+ 360.0236
+ 0 ]
+ /Next 51 0 R
+ /Parent 34 0 R
+ /Prev 49 0 R
+ /Title (p.overlaps\(q\)) >>
+endobj
+% 'Outline.65.16': class OutlineEntryObject 
+51 0 obj
+<< /Dest [ 14 0 R
+ /XYZ
+ 62.69291
+ 255.0236
+ 0 ]
+ /Next 52 0 R
+ /Parent 34 0 R
+ /Prev 50 0 R
+ /Title (p.boundingBox\(|i\)) >>
+endobj
+% 'Outline.65.17': class OutlineEntryObject 
+52 0 obj
+<< /Dest [ 14 0 R
+ /XYZ
+ 62.69291
+ 138.0236
+ 0 ]
+ /Next 53 0 R
+ /Parent 34 0 R
+ /Prev 51 0 R
+ /Title (p.aspectRatio\(|i\)) >>
+endobj
+% 'Outline.65.18': class OutlineEntryObject 
+53 0 obj
+<< /Dest [ 15 0 R
+ /XYZ
+ 62.69291
+ 711.0236
+ 0 ]
+ /Next 54 0 R
+ /Parent 34 0 R
+ /Prev 52 0 R
+ /Title (p.scale\(xs, ys |, xc, yc\)) >>
+endobj
+% 'Outline.65.19': class OutlineEntryObject 
+54 0 obj
+<< /Dest [ 15 0 R
+ /XYZ
+ 62.69291
+ 552.0236
+ 0 ]
+ /Next 55 0 R
+ /Parent 34 0 R
+ /Prev 53 0 R
+ /Title (p.shift\(xs, ys\)) >>
+endobj
+% 'Outline.65.20': class OutlineEntryObject 
+55 0 obj
+<< /Dest [ 15 0 R
+ /XYZ
+ 62.69291
+ 441.0236
+ 0 ]
+ /Next 56 0 R
+ /Parent 34 0 R
+ /Prev 54 0 R
+ /Title (p.rotate\(a |, xc, yc\)) >>
+endobj
+% 'Outline.65.21': class OutlineEntryObject 
+56 0 obj
+<< /Dest [ 15 0 R
+ /XYZ
+ 62.69291
+ 300.0236
+ 0 ]
+ /Next 57 0 R
+ /Parent 34 0 R
+ /Prev 55 0 R
+ /Title (p.warpToBox\(x0, x1, y0, y1\)) >>
+endobj
+% 'Outline.65.22': class OutlineEntryObject 
+57 0 obj
+<< /Dest [ 15 0 R
+ /XYZ
+ 62.69291
+ 141.0236
+ 0 ]
+ /Next 58 0 R
+ /Parent 34 0 R
+ /Prev 56 0 R
+ /Title (p.flip\(|x\)) >>
+endobj
+% 'Outline.65.23': class OutlineEntryObject 
+58 0 obj
+<< /Dest [ 16 0 R
+ /XYZ
+ 62.69291
+ 711.0236
+ 0 ]
+ /Next 59 0 R
+ /Parent 34 0 R
+ /Prev 57 0 R
+ /Title (p.flop\(|y\)) >>
+endobj
+% 'Outline.65.24': class OutlineEntryObject 
+59 0 obj
+<< /Dest [ 16 0 R
+ /XYZ
+ 62.69291
+ 618.0236
+ 0 ]
+ /Next 60 0 R
+ /Parent 34 0 R
+ /Prev 58 0 R
+ /Title (p.cloneContour\(i|, xs, ys\)) >>
+endobj
+% 'Outline.65.25': class OutlineEntryObject 
+60 0 obj
+<< /Dest [ 16 0 R
+ /XYZ
+ 62.69291
+ 489.0236
+ 0 ]
+ /Next 61 0 R
+ /Parent 34 0 R
+ /Prev 59 0 R
+ /Title (p.triStrip\(\)) >>
+endobj
+% 'Outline.65.26': class OutlineEntryObject 
+61 0 obj
+<< /Dest [ 16 0 R
+ /XYZ
+ 62.69291
+ 342.0236
+ 0 ]
+ /Parent 34 0 R
+ /Prev 60 0 R
+ /Title (p.sample\(rng\)) >>
+endobj
+% 'Outline.64.1': class OutlineEntryObject 
+62 0 obj
+<< /Count 4
+ /Dest [ 16 0 R
+ /XYZ
+ 62.69291
+ 237.0236
+ 0 ]
+ /First 63 0 R
+ /Last 66 0 R
+ /Next 67 0 R
+ /Parent 33 0 R
+ /Prev 34 0 R
+ /Title (Module Polygon.Shapes) >>
+endobj
+% 'Outline.66.0': class OutlineEntryObject 
+63 0 obj
+<< /Dest [ 16 0 R
+ /XYZ
+ 62.69291
+ 189.0236
+ 0 ]
+ /Next 64 0 R
+ /Parent 62 0 R
+ /Title (Circle\(|radius=1.0, center=\(0.0,0.0\), points=32\)) >>
+endobj
+% 'Outline.66.1': class OutlineEntryObject 
+64 0 obj
+<< /Dest [ 17 0 R
+ /XYZ
+ 62.69291
+ 738.0236
+ 0 ]
+ /Next 65 0 R
+ /Parent 62 0 R
+ /Prev 63 0 R
+ /Title (Star\(|radius=1.0, center=\(0.0,0.0\), beams=16, iradius=0.5\)) >>
+endobj
+% 'Outline.66.2': class OutlineEntryObject 
+65 0 obj
+<< /Dest [ 17 0 R
+ /XYZ
+ 62.69291
+ 591.0236
+ 0 ]
+ /Next 66 0 R
+ /Parent 62 0 R
+ /Prev 64 0 R
+ /Title (Rectangle\(|xl= 1.0, yl=None\)) >>
+endobj
+% 'Outline.66.3': class OutlineEntryObject 
+66 0 obj
+<< /Dest [ 17 0 R
+ /XYZ
+ 62.69291
+ 480.0236
+ 0 ]
+ /Parent 62 0 R
+ /Prev 65 0 R
+ /Title (SierpinksiCarpet\(|width= 1.0, level=5\)) >>
+endobj
+% 'Outline.64.2': class OutlineEntryObject 
+67 0 obj
+<< /Count 8
+ /Dest [ 17 0 R
+ /XYZ
+ 62.69291
+ 351.0236
+ 0 ]
+ /First 68 0 R
+ /Last 75 0 R
+ /Next 76 0 R
+ /Parent 33 0 R
+ /Prev 62 0 R
+ /Title (Module Polygon.IO) >>
+endobj
+% 'Outline.67.0': class OutlineEntryObject 
+68 0 obj
+<< /Dest [ 17 0 R
+ /XYZ
+ 62.69291
+ 303.0236
+ 0 ]
+ /Next 69 0 R
+ /Parent 67 0 R
+ /Title (encodeBinary\(p\)) >>
+endobj
+% 'Outline.67.1': class OutlineEntryObject 
+69 0 obj
+<< /Dest [ 17 0 R
+ /XYZ
+ 62.69291
+ 186.0236
+ 0 ]
+ /Next 70 0 R
+ /Parent 67 0 R
+ /Prev 68 0 R
+ /Title (decodeBinary\(s\)) >>
+endobj
+% 'Outline.67.2': class OutlineEntryObject 
+70 0 obj
+<< /Dest [ 18 0 R
+ /XYZ
+ 62.69291
+ 675.0236
+ 0 ]
+ /Next 71 0 R
+ /Parent 67 0 R
+ /Prev 69 0 R
+ /Title (writeGnuplot\(ofile, polylist\)) >>
+endobj
+% 'Outline.67.3': class OutlineEntryObject 
+71 0 obj
+<< /Dest [ 18 0 R
+ /XYZ
+ 62.69291
+ 552.0236
+ 0 ]
+ /Next 72 0 R
+ /Parent 67 0 R
+ /Prev 70 0 R
+ /Title (writeGnuplotTriangles\(ofile, polylist\)) >>
+endobj
+% 'Outline.67.4': class OutlineEntryObject 
+72 0 obj
+<< /Dest [ 18 0 R
+ /XYZ
+ 62.69291
+ 429.0236
+ 0 ]
+ /Next 73 0 R
+ /Parent 67 0 R
+ /Prev 71 0 R
+ /Title (writeSVG\(ofile, polylist, ...\)) >>
+endobj
+% 'Outline.67.5': class OutlineEntryObject 
+73 0 obj
+<< /Dest [ 18 0 R
+ /XYZ
+ 62.69291
+ 186.0236
+ 0 ]
+ /Next 74 0 R
+ /Parent 67 0 R
+ /Prev 72 0 R
+ /Title (writeXML\(ofile, polylist, withHeader=False\)) >>
+endobj
+% 'Outline.67.6': class OutlineEntryObject 
+74 0 obj
+<< /Dest [ 20 0 R
+ /XYZ
+ 62.69291
+ 675.0236
+ 0 ]
+ /Next 75 0 R
+ /Parent 67 0 R
+ /Prev 73 0 R
+ /Title (readXML\(ifile\)) >>
+endobj
+% 'Outline.67.7': class OutlineEntryObject 
+75 0 obj
+<< /Dest [ 20 0 R
+ /XYZ
+ 62.69291
+ 582.0236
+ 0 ]
+ /Parent 67 0 R
+ /Prev 74 0 R
+ /Title (writePDF\(ofile, polylist, pagesize=None, linewidth=0, fill_color=None\)) >>
+endobj
+% 'Outline.64.3': class OutlineEntryObject 
+76 0 obj
+<< /Count 11
+ /Dest [ 20 0 R
+ /XYZ
+ 62.69291
+ 405.0236
+ 0 ]
+ /First 77 0 R
+ /Last 87 0 R
+ /Parent 33 0 R
+ /Prev 67 0 R
+ /Title (Module Polygon.Utils) >>
+endobj
+% 'Outline.68.0': class OutlineEntryObject 
+77 0 obj
+<< /Dest [ 20 0 R
+ /XYZ
+ 62.69291
+ 357.0236
+ 0 ]
+ /Next 78 0 R
+ /Parent 76 0 R
+ /Title (fillHoles\(p\)) >>
+endobj
+% 'Outline.68.1': class OutlineEntryObject 
+78 0 obj
+<< /Dest [ 20 0 R
+ /XYZ
+ 62.69291
+ 264.0236
+ 0 ]
+ /Next 79 0 R
+ /Parent 76 0 R
+ /Prev 77 0 R
+ /Title (pointList\(p\)) >>
+endobj
+% 'Outline.68.2': class OutlineEntryObject 
+79 0 obj
+<< /Dest [ 20 0 R
+ /XYZ
+ 62.69291
+ 171.0236
+ 0 ]
+ /Next 80 0 R
+ /Parent 76 0 R
+ /Prev 78 0 R
+ /Title (convexHull\(p\)) >>
+endobj
+% 'Outline.68.3': class OutlineEntryObject