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

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

Changed PointSeriesConvertor? to handle conversion using quad-tree. Therefore created a new module QuadTree?.py.

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