File:Point_quadtree.svg
Da Wikipedia, l'enciclopedia encyclopedia
![File:Point quadtree.svg](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Point_quadtree.svg/500px-Point_quadtree.svg.png)
Dimensioni di questa anteprima PNG per questo file SVG: 500 × 500 pixel. Altre risoluzioni: 240 × 240 pixel | 480 × 480 pixel | 768 × 768 pixel | 1 024 × 1 024 pixel | 2 048 × 2 048 pixel.
File originale (file in formato SVG, dimensioni nominali 500 × 500 pixel, dimensione del file: 30 KB)
![]() |
Questo file e la sua pagina di descrizione (discussione · modifica) si trovano su Wikimedia Commons (?) |
Dettagli
DescrizionePoint quadtree.svg | A point quadtree |
Data | |
Fonte | self-made; originally for a talk at the 21st ACM Symp. on Computational Geometry, Pisa, June 2005 |
Autore | 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()
Licenza
Public domainPublic domainfalsefalse |
![]() |
Quest'opera è stata rilasciata nel pubblico dominio dal suo autore, I, David Eppstein. Questa norma si applica in tutto il mondo. In alcuni paesi questo potrebbe non essere legalmente possibile. In tal caso: I, David Eppstein garantisce a chiunque il diritto di utilizzare quest'opera per qualsiasi scopo, senza alcuna condizione, a meno che tali condizioni siano richieste dalla legge. |
Didascalie
Aggiungi una brevissima spiegazione di ciò che questo file rappresenta
Elementi ritratti in questo file
raffigura
Valore sconosciuto senza un elemento Wikidata
31 mag 2005
Cronologia del file
Fare clic su un gruppo data/ora per vedere il file come si presentava nel momento indicato.
Data/Ora | Miniatura | Dimensioni | Utente | Commento | |
---|---|---|---|---|---|
attuale | 04:59, 31 lug 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 |
Pagine che usano questo file
La seguente pagina usa questo file:
Utilizzo globale del file
Anche i seguenti wiki usano questo file:
- Usato nelle seguenti pagine di de.wikipedia.org:
- Usato nelle seguenti pagine di en.wikipedia.org:
- Usato nelle seguenti pagine di es.wikipedia.org:
- Usato nelle seguenti pagine di fa.wikipedia.org:
- Usato nelle seguenti pagine di fi.wikipedia.org:
- Usato nelle seguenti pagine di fr.wikipedia.org:
- Usato nelle seguenti pagine di fr.wiktionary.org:
- Usato nelle seguenti pagine di ja.wikipedia.org:
- Usato nelle seguenti pagine di ru.wikipedia.org:
- Usato nelle seguenti pagine di sr.wikipedia.org:
- Usato nelle seguenti pagine di uk.wikipedia.org:
- Usato nelle seguenti pagine di www.wikidata.org:
- Usato nelle seguenti pagine di zh.wikipedia.org:
Estratto da "https://it.wikipedia.org/wiki/File:Point_quadtree.svg"