File:Point quadtree.svg

[edit] Summary

[edit] Source code

The Python source code for generating this image:

import sys
from 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 = None

def 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 nestingLevel
        if deltaIndentation < 0:
                nestingLevel -= 1
        if 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 += 1
        

def 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 nestingLevel
        if 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 = 0
        svgTag('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 = 2
svgBound = 400
margin = 4

def clusteredCoordinate(clusteringExponent,fractalExponent):
    x = long(randrange(1000)**clusteringExponent)
    y = 0
    p = 1
    while x:
        if x & 1:
            y += p
        p *= fractalExponent
        x >>= 1
    return y

def 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)/maxX
scaleY = 1.0*(svgBound-2*margin)/maxY
points = [(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()

[edit] Licensing

This work has been released into the public domain by its author, I, David Eppstein. This applies worldwide. In some countries this may not be legally possible; if so: I, David Eppstein grants anyone the right to use this work for any purpose, without any conditions, unless such conditions are required by law. Public domainPublic domainfalsefalse

Click on a date/time to view the file as it appeared at that time.

	Date/Time	Thumbnail	Dimensions	User	Comment
current	02:59, 31 July 2007		500 × 500 (30 KB)	David Eppstein	{{Information |Description= |Source=self-made; originally for [http://www.ics.uci.edu/~eppstein/pubs/EppGooSun-SoCG-05.pdf a talk at the 21st ACM Symp. on Computational Geometry, Pisa, June 2005] |Date=May 31, 2005 |Author= [[User:David Eppstein|David Epp

• Quadtree

The following other wikis use this file:

• Usage on fr.wikipedia.org
  • Quadtree
  • Structures de données dans un SIG
• Usage on it.wikipedia.org
  • Quadtree
• Usage on ja.wikipedia.org
  • 四分木
• Usage on zh.wikipedia.org
  • 四叉树