Revision 3315, 5.0 KB checked in by mkochan, 12 years ago (diff)

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 KMLDocument 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
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
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
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