MAKE A MEME
View Large Image
| View Original: | Point quadtree.svg (400x400) | |||
| Download: | Original | Medium | Small | Thumb |
| Courtesy of: | commons.wikimedia.org | More Like This | ||
| Keywords: Point quadtree.svg A point quadtree 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 2005-05-31 David Eppstein Source code The Python source code for generating this image <syntaxhighlight lang python >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 toplefti+botrighti 0 5 for i in range 2 svgLine mid0 topleft1 mid0 botright1 svgLine topleft0 mid1 botright0 mid1 quadtree p for p in points if p0<mid0 and p1<mid1 topleft mid quadtree p for p in points if p0<mid0 and p1> mid1 topleft0 mid1 mid0 botright1 quadtree p for p in points if p0> mid0 and p1<mid1 mid0 topleft1 botright0 mid1 quadtree p for p in points if p0> mid0 and p1> mid1 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 </syntaxhighlight> Computational geometry Files by User David Eppstein from en wikipedia Quadtrees Images with Python source code | ||||
