File:Point_quadtree.svg
From Wikipedia, the free encyclopedia
![File:Point quadtree.svg](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Point_quadtree.svg/500px-Point_quadtree.svg.png)
Size of this PNG preview of this SVG file: 500 × 500 pixels. Other resolutions: 240 × 240 pixels | 480 × 480 pixels | 768 × 768 pixels | 1,024 × 1,024 pixels | 2,048 × 2,048 pixels.
Original file (SVG file, nominally 500 × 500 pixels, file size: 30 KB)
![]() | This is a file from the Wikimedia Commons. Information from its description page there is shown below. Commons is a freely licensed media file repository. You can help. |
Summary
DescriptionPoint quadtree.svg | A point quadtree |
Date | |
Source | self-made; originally for a talk at the 21st ACM Symp. on Computational Geometry, Pisa, June 2005 |
Author | David Eppstein |
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()
Licensing
Public domainPublic domainfalsefalse |
![]() |
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. |
Captions
Add a one-line explanation of what this file represents
Items portrayed in this file
depicts
some value
31 May 2005
File history
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 |
File usage
The following pages on the English Wikipedia use this file (pages on other projects are not listed):
Global file usage
The following other wikis use this file:
- Usage on de.wikipedia.org
- Usage on es.wikipedia.org
- Usage on fa.wikipedia.org
- Usage on fi.wikipedia.org
- Usage on fr.wikipedia.org
- Usage on fr.wiktionary.org
- Usage on it.wikipedia.org
- Usage on ja.wikipedia.org
- Usage on ru.wikipedia.org
- Usage on sr.wikipedia.org
- Usage on uk.wikipedia.org
- Usage on www.wikidata.org
- Usage on zh.wikipedia.org
Retrieved from "https://en.wikipedia.org/wiki/File:Point_quadtree.svg"