import sysfrom random import seed, randrange# ==========================================================================#Recursive quadtree data structure# ==========================================================================def quadtree(points,topleft,botright):    if len(points) > 1:#        print >>sys.stderr,"splitting",len(points),topleft,botright        mid = [(topleft[i]+botright[i])*0.5 for i in range(2)]        svgLine((mid[0],topleft[1]),(mid[0],botright[1]))        svgLine((topleft[0],mid[1]),(botright[0],mid[1]))        quadtree([p for p in points if p[0]<mid[0] and p[1]<mid[1]],                 topleft,mid)        quadtree([p for p in points if p[0]<mid[0] and p[1]>=mid[1]],                 (topleft[0],mid[1]),(mid[0],botright[1]))        quadtree([p for p in points if p[0]>=mid[0] and p[1]<mid[1]],                 (mid[0],topleft[1]),(botright[0],mid[1]))        quadtree([p for p in points if p[0]>=mid[0] and p[1]>=mid[1]],                 mid,botright)        # ==========================================================================#SVG output utility routines# ==========================================================================nestingLevel = Nonedef svgTag(s, deltaIndentation = 0):"""Send a single XML tag to the SVG file.First argument is the tag with all its attributes appended.Second arg is +1, -1, or 0 if tag is open, close, or both respectively."""global nestingLevelif deltaIndentation < 0:nestingLevel -= 1if nestingLevel:sys.stdout.write('\t' * nestingLevel)sys.stdout.write('<')if deltaIndentation < 0:sys.stdout.write('/')sys.stdout.write(s)if not deltaIndentation:sys.stdout.write(' /')sys.stdout.write('>\n')if deltaIndentation > 0:nestingLevel += 1def svgHeader(maxX, maxY):"""Start producing an SVG object.The output bounding box runs from (0,0) to (maxX,maxY).Must be followed by svg content and a call to svgTrailer()."""global nestingLevelif nestingLevel is None:sys.stdout.write('''<?xml version="1.0" encoding="iso-8859-1"?><!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">''')nestingLevel = 0svgTag('svg xmlns="http://www.w3.org/2000/svg" version="1.1" '   'width="%dpt" height="%dpt" viewBox="0 0 %d %d"'% (maxX, maxY, maxX, maxY), 1)def svgTrailer():"""End of SVG object."""svgTag('svg', -1)def svgStyle(style):"""Start a group of svg items with the given style.Argument is a string in the form of a list of svg item attributes.Must be followed by svg content and a call to svgEndStyle()."""svgTag('g ' + style, 1)def svgEdgeStyle(index):"""Look up edge style and call svgStyle with it."""svgStyle(globals()['edgeStyle' + str(index)])def svgEndStyle():"""Finish group of styled svg items."""svgTag('g', -1)def svgLine(start, end):"""Output line segment from start to end coordinates.Must be called within an svgStyle()/svgEndStyle() call pair."""svgTag('line x1="%d" y1="%d" x2="%d" y2="%d"' % (start+end) )def svgCircle(center, radius):"""Output circle with given center and radius coordinates.Must be called within an svgStyle()/svgEndStyle() call pair."""svgTag('circle cx="%d" cy="%d" r="%s"' % (center+(radius,)) )# ==========================================================================#Test code driver# ==========================================================================seed(27)svgRadius = 2svgBound = 400margin = 4def clusteredCoordinate(clusteringExponent,fractalExponent):    x = long(randrange(1000)**clusteringExponent)    y = 0    p = 1    while x:        if x & 1:            y += p        p *= fractalExponent        x >>= 1    return ydef clusteredPoint():    return clusteredCoordinate(2,2.5),clusteredCoordinate(1.5,3.2)points = [clusteredPoint() for i in range(250)]maxX = max(x for x,y in points)maxY = max(y for x,y in points)scaleX = 1.0*(svgBound-2*margin)/maxXscaleY = 1.0*(svgBound-2*margin)/maxYpoints = [(x*scaleX+margin,y*scaleY+margin) for x,y in points]svgHeader(svgBound,svgBound)svgStyle('fill="none" stroke="blue"')svgLine((1,1),(1,svgBound-1))svgLine((1,svgBound-1),(svgBound-1,svgBound-1))svgLine((svgBound-1,svgBound-1),(svgBound-1,1))svgLine((svgBound-1,1),(1,1))quadtree(points,(1,1),(svgBound-1,svgBound-1))svgEndStyle()svgStyle('fill="white" stroke="black"')for p in points:    svgCircle(p,svgRadius)svgEndStyle()svgTrailer()