Image: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

I, David Eppstein, the copyright holder of this work, hereby release it into the public domain. This applies worldwide. In case this is not legally possible: I grant anyone the right to use this work for any purpose, without any conditions, unless such conditions are required by law. Afrikaans | Alemannisch | Aragonés | العربية | Asturianu | Български | Català | Česky | Cymraeg | Dansk | Deutsch | Eʋegbe | Ελληνικά | English | Español | Esperanto | Euskara | Estremeñu | فارسی | Français | Galego | 한국어 | हिन्दी | Hrvatski | Ido | Bahasa Indonesia | Íslenska | Italiano | עברית | Kurdî / كوردی | Latina | Lietuvių | Latviešu | Magyar | Македонски | Bahasa Melayu | Nederlands | ‪Norsk (bokmål)‬ | ‪Norsk (nynorsk)‬ | 日本語 | Polski | Português | Ripoarisch | Română | Русский | Shqip | Slovenčina | Slovenščina | Српски / Srpski | Svenska | ไทย | Tagalog | Türkçe | Українська | Tiếng Việt | Walon | ‪中文(简体)‬ | ‪中文(繁體)‬ | zh-yue-hant | +/-

• Quadtree