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

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

Prepared file hierarchy for creating an egg "csml2kml"

Line 
1'''
2Classes and functions for producing geographic quat trees, i.e. trees which enable quadric recursive space splitting.
3'''
4
5from random import random
6from cElementTree import ElementTree, Element, SubElement
7from KML import *
8import sys
9
10class Location:
11    '''
12    Represents a geographic location (lon, lat) which has some object, obj, associated with it
13    '''
14    def __init__(self, lon, lat, obj):
15        self.obj = obj
16        self.lon = lon; self.lat = lat
17    def __repr__(self):
18        return '"%s% @ (%f,%f)' % (str(self.obj), self.lon, self.lat)
19
20class Tree:
21    '''
22    Abstract class, represents a tree of regions/locations. The tree can be converted
23    directly to a KML document which contains station locations using KML regions.
24    '''
25    pass
26
27class Leaf(Tree):
28    pass
29
30class NilLeaf(Leaf):
31    '''
32    Leaf which contains nothing in itself. Used whenever an empty region has to be created
33    (i.e. a region with no stations in it). This is because a Node should always contain 4 children.
34    '''
35    def __repr__(self):
36        return 'nil'
37
38class LocLeaf(Leaf):
39    '''
40    A tree leaf containing locations, i.e. Location objects.
41    '''
42    def __init__(self, locations, bbox):
43        self.bbox = bbox
44        if not locations:
45            raise ValueError('Empty location list passed')
46        self.locations = locations
47    def __repr__(self):
48        s = ''
49        for loc in self.locations: s = s + repr(loc) + ','
50        return '[' + s + '] in ' + repr(self.bbox)
51
52class Node(Tree):
53    '''
54    A tree node which contains children, being themselves Tree objects.
55    '''
56    def __init__(self, children, bbox):
57        self.bbox = bbox
58        if len(children) != 4:
59            raise ValueError('Exactly 4 tree children must be passed')
60        self.children = children
61    def __repr__(self):
62        s = ''
63        for c in self.children: s = s + repr(c) + ','
64        return '[' + s + '] in ' + repr(self.bbox)
65
66class BBox:
67    '''
68    Represents a bounding box, i.e. a geographical 2D region (considering longitute & latitude only,
69    ignoring altitude). Contains 4 methods for splitting the region into its SW, SE, NW, NE parts
70    (i.e. quadratic splitting).
71    '''
72
73    def __init__(self, west, south, east, north):
74        if west < -180. or south < -90. or east > 180 or north > 90:
75            raise ValueError('Degree(s) out of bounds')
76        self.west = west; self.east = east
77        self.south = south; self.north = north
78    def __repr__(self):
79        return 'BBox(lon:%s--%s,lat:%s--%s)' % (self.west, self.east, self.south, self.north)
80    def lon_centre(self):
81        return (self.west + self.east) / 2
82    def lat_centre(self):
83        return (self.south + self.north) / 2
84    def sw(self):
85        return BBox(self.west, self.south, self.lon_centre(), self.lat_centre())
86    def se(self):
87        return BBox(self.lon_centre(), self.south, self.east, self.lat_centre())
88    def nw(self):
89        return BBox(self.west, self.lat_centre(), self.lon_centre(), self.north)
90    def ne(self):
91        return BBox(self.lon_centre(), self.lat_centre(), self.east, self.north)
92
93#---------------------------------------------------------------------------------------------------------------------------
94
95def build_quadtree(l,bbox=BBox(-180.,-90.,180.,90.),max_per_region=16):
96    '''
97    Description:               Performs quad-tree segmentation of space, to store (station) locations
98                               in a tree that contains locations in a hierarchy of smaller and smaller segments/nodes,
99                               each smaller node produced by splitting the space into 4 sub-spaces.
100   
101    Input:               l ... List of (station) locations, i.e. of Location objects
102                      bbox ... A BBox object determining the main bounding box enwrapping
103                               all possible time boxes, i.e. the one from which to start dividing.
104                               Supply BBox(-180.,-90.,180.,90.) to use whole globe.
105            max_per_region ... Maximum number of locations to be contained in a lowest-level region
106                               (i.e. in a LocLeaf object). This determines the depth of the resultant
107                               tree.
108
109    Output:                    The quad-tree.
110    '''
111    if len(l) == 0:
112        return NilLeaf()
113    elif len(l) <= max_per_region:
114        return LocLeaf(l,bbox)
115    else:
116        (l1, l2, l3, l4) = ([], [], [], [])
117        for i in l:
118            (lon,lat) = (i.lon,i.lat)
119            if lat < bbox.lat_centre():
120                if lon < bbox.lon_centre():
121                    l1.append(i) # SW
122                else:
123                    l2.append(i) # SE
124            else:
125                if lon < bbox.lon_centre():
126                    l3.append(i) # NW
127                else:
128                    l4.append(i) # NE
129        t1 = build_quadtree(l1, bbox.sw())
130        t2 = build_quadtree(l2, bbox.se())
131        t3 = build_quadtree(l3, bbox.nw())
132        t4 = build_quadtree(l4, bbox.ne())
133        return Node([t1, t2, t3, t4],bbox)
Note: See TracBrowser for help on using the repository browser.