source: DPPP/kml/csml2kml/python/csml2kml/csml2kml/QuadTree.py @ 3651

Subversion URL: http://proj.badc.rl.ac.uk/svn/ndg/DPPP/kml/csml2kml/python/csml2kml/csml2kml/QuadTree.py@3651
Revision 3651, 5.5 KB checked in by mkochan, 12 years ago (diff)

Debug in csmlGrapher.

Line 
1'''
2Classes and functions for storing locations in quadric trees (representations of quadric splitting of space).
3
4It is possible to split locations in longitude-latitude space by recursive splitting regions (bounding boxes)
5into 4 smaller regions (the NE, NW, SW and SE region) until each low-level box does not contain
6a defined maximum of locations.
7
8The intended use for quadric splitting here is to allow storing I{<np:Station>} elements into a hierarchy
9of KML folders with associated KML regions, thereby making them to get rendered only for closer zooms
10to the ground.
11'''
12
13from random import random
14from cElementTree import ElementTree, Element, SubElement
15from KML import *
16import sys
17
18class Location:
19    '''
20    Represents a geographic location (C{lon}, C{lat}) with an associated object, C{obj}.
21    @ivar lon: The location longitute.
22    @type lon: C{float}
23    @ivar lat: The location latitude.
24    @type lat: C{float}
25    @ivar obj: The associated object.
26    @type obj: C{instance}
27    '''
28    def __init__(self, lon, lat, obj):
29        self.obj = obj
30        self.lon = lon; self.lat = lat
31    def __repr__(self):
32        return '"%s% @ (%f,%f)' % (str(self.obj), self.lon, self.lat)
33
34class Tree:
35    '''Abstract class, represents a quadric tree of regions/locations.'''
36    pass
37
38class Leaf(Tree):
39    '''Abstract class, represents all leaves in a quadric tree.'''
40    pass
41
42class NilLeaf(Leaf):
43    '''
44    Leaf which contains nothing in itself. Used whenever an empty region has to be created
45    (i.e. a region with no stations in it). This is because a Node should always contain 4 children.
46    '''
47    def __repr__(self):
48        return 'nil'
49
50class LocLeaf(Leaf):
51    '''
52    A tree leaf containing locations (C{Location} objects).
53    '''
54    def __init__(self, locations, bbox):
55        self.bbox = bbox
56        if not locations:
57            raise ValueError('Empty location list passed')
58        self.locations = locations
59    def __repr__(self):
60        s = ''
61        for loc in self.locations: s = s + repr(loc) + ','
62        return '[' + s + '] in ' + repr(self.bbox)
63
64class Node(Tree):
65    '''
66    A tree node which contains children (C{Tree} objects).
67    '''
68    def __init__(self, children, bbox):
69        self.bbox = bbox
70        if len(children) != 4:
71            raise ValueError('Exactly 4 tree children must be passed')
72        self.children = children
73    def __repr__(self):
74        s = ''
75        for c in self.children: s = s + repr(c) + ','
76        return '[' + s + '] in ' + repr(self.bbox)
77
78class BBox:
79    '''
80    Represents  a geographical 2D region.
81    Contains 4 methods for splitting the region quadrically (into its SW, SE, NW, NE parts).
82    '''
83
84    def __init__(self, west, south, east, north):
85        if west < -180. or south < -90. or east > 180 or north > 90:
86            raise ValueError('Degree(s) out of bounds')
87        self.west = west; self.east = east
88        self.south = south; self.north = north
89    def __repr__(self):
90        return 'BBox(lon:%s--%s,lat:%s--%s)' % (self.west, self.east, self.south, self.north)
91    def lon_centre(self):
92        '''
93        Get the central longitude for the bbox.
94        @rtype: C{int}
95        '''
96        return (self.west + self.east) / 2
97    def lat_centre(self):
98        '''
99        Get the central latitude for the bbox.
100        @rtype: C{int}
101        '''
102        return (self.south + self.north) / 2
103    def sw(self):
104        '''
105        Get the SW quarter of the bounding box.
106        @rtype: C{BBox}
107        '''
108        return BBox(self.west, self.south, self.lon_centre(), self.lat_centre())
109    def se(self):
110        '''
111        Get the SE quarter of the bounding box.
112        @rtype: C{BBox}
113        '''
114        return BBox(self.lon_centre(), self.south, self.east, self.lat_centre())
115    def nw(self):
116        '''
117        Get the NW quarter of the bounding box.
118        @rtype: C{BBox}
119        '''
120        return BBox(self.west, self.lat_centre(), self.lon_centre(), self.north)
121    def ne(self):
122        '''
123        Get the NE quarter of the bounding box.
124        @rtype: C{BBox}
125        '''
126        return BBox(self.lon_centre(), self.lat_centre(), self.east, self.north)
127
128#---------------------------------------------------------------------------------------------------------------------------
129
130def build_quadtree(l,bbox=BBox(-180.,-90.,180.,90.),max_per_region=10):
131    '''
132    Performs quadric splitting of space.
133    @param l: The locations to be splitted
134    @type l: C{Location list}
135    @param bbox: The region to split in this recursive iteration (using the default gives the whole globe)
136    @type bbox: C{BBox}
137    @param max_per_region: Maximum number of locations to be contained in a lowest-level region
138    (in a C{LocLeaf} object). This influences the depth of the resultant tree.
139    @return: The quad-tree.
140    @rtype: C{QuadTree}
141    '''
142    if len(l) == 0:
143        return NilLeaf()
144    elif len(l) <= max_per_region:
145        return LocLeaf(l,bbox)
146    else:
147        (l1, l2, l3, l4) = ([], [], [], [])
148        for i in l:
149            (lon,lat) = (i.lon,i.lat)
150            if lat < bbox.lat_centre():
151                if lon < bbox.lon_centre():
152                    l1.append(i) # SW
153                else:
154                    l2.append(i) # SE
155            else:
156                if lon < bbox.lon_centre():
157                    l3.append(i) # NW
158                else:
159                    l4.append(i) # NE
160        t1 = build_quadtree(l1, bbox.sw())
161        t2 = build_quadtree(l2, bbox.se())
162        t3 = build_quadtree(l3, bbox.nw())
163        t4 = build_quadtree(l4, bbox.ne())
164        return Node([t1, t2, t3, t4],bbox)
Note: See TracBrowser for help on using the repository browser.