source: trunk/anuga_core/source/anuga/geometry/quad.py @ 7858

Last change on this file since 7858 was 7858, checked in by hudson, 14 years ago

Refactorings to increase code quality, fixed missing log import from sww_interrogate.

File size: 6.6 KB
Line 
1"""quad.py - quad tree data structure for fast indexing of regions in the plane.
2
3This generic structure can be used to store any geometry in a quadtree.
4It is naive, and does not exploit any coherency - it merely tests a point
5against all bounding boxes in its heirarchy.
6
7It returns a list of bounding boxes which intersect with the test point, which
8may then be iterated over with a proper intersection test to detect actual
9geometry intersections.
10
11As of June 2010 this module has a pylint quality rating of 10/10.
12
13"""
14
15from anuga.utilities.treenode import TreeNode
16import anuga.utilities.log as log
17
18           
19class Cell(TreeNode):
20    """class Cell
21
22    One cell in the plane.
23    """
24 
25    def __init__(self, extents, parent,
26         name = 'cell'):
27        """ Construct a new cell.
28            extents is an AABB defining a region on the plane.
29            parent is the node above this one, or None if it is root.
30        """
31 
32        # Initialise base classes
33        TreeNode.__init__(self, name)
34   
35        self.extents = extents
36        self.parent = parent
37       
38        # The points in this cell     
39        self.leaves = []
40        self.children = None
41       
42   
43    def __repr__(self):
44        ret_str = '%s: leaves: %d' \
45               % (self.name , len(self.leaves))   
46        if self.children:
47            ret_str += ', children: %d' % (len(self.children))
48        return ret_str
49
50   
51
52    def clear(self):
53        """ Remove all leaves from this node.
54        """
55        self.Prune()   # TreeNode method
56
57
58    def clear_leaf_node(self):
59        """ Clears storage in leaf node.
60            Called from Treenode.
61            Must exist.   
62        """
63        self.leaves = []
64   
65   
66    def clear_internal_node(self):
67        """Called from Treenode.   
68    Must exist.
69    """
70        self.leaves = []
71
72
73    def insert(self, new_leaf):
74        """ Insert a leaf into the quadtree.
75            new_leaf is a tuple of (AABB extents, data), where data can
76                     be any user data (geometry, triangle index, etc.).
77        """
78        if type(new_leaf)==type(list()):
79            for leaf in new_leaf:
80                self.insert_item(leaf)
81        else:
82            self.insert_item(new_leaf)
83
84
85    def insert_item(self, new_leaf):   
86        """ Internal recursive insert a single item.
87            new_leaf is a tuple of (AABB extents, data), where data can
88                     be any user data (geometry, triangle index, etc.).       
89        """
90        new_region, _ = new_leaf
91       
92        # recurse down to any children until we get an intersection
93        if self.children:
94            for child in self.children:
95                if child.extents.is_trivial_in(new_region):
96                    child.insert_item(new_leaf)
97                    return
98        else:           
99            # try splitting this cell and see if we get a trivial in
100            subregion1, subregion2 = self.extents.split()
101           
102            # option 1 - try splitting 4 ways
103            #subregion11, subregion12 = subregion1.split()   
104            #subregion21, subregion22 = subregion2.split()
105            #regions = [subregion11, subregion12, subregion21, subregion22]
106            #for region in regions:
107                #if region.is_trivial_in(new_region):
108                    #self.children = [Cell(x, parent=self) for x in regions]
109                    #self.insert_item(new_leaf)
110                    #return               
111
112            # option 2 - try splitting 2 ways - no diff noticed in practise
113            if subregion1.is_trivial_in(new_region):
114                self.children = [Cell(subregion1, self), \
115                                 Cell(subregion2, self)]   
116                self.children[0].insert_item(new_leaf)
117                return
118            elif subregion2.is_trivial_in(new_region):
119                self.children = [Cell(subregion1, self), \
120                                 Cell(subregion2, self)]   
121                self.children[1].insert_item(new_leaf)
122                return               
123   
124        # recursion ended without finding a fit, so attach it as a leaf
125        self.leaves.append(new_leaf)
126       
127     
128    def retrieve(self):
129        """Get all leaves from this tree.
130           return a traversal of the entire tree.
131        """
132       
133        leaves_found = list(self.leaves)
134       
135        if not self.children:
136            return leaves_found
137
138        for child in self.children:
139            leaves_found.extend(child.retrieve())
140           
141        return leaves_found
142
143    def count(self):
144        """Count all leaves from this tree.
145           return num of leaves in the tree.
146        """
147       
148        leaves_found = len(self.leaves)
149       
150        if not self.children:
151            return leaves_found
152
153        for child in self.children:
154            leaves_found += child.count()
155           
156        return leaves_found       
157
158    def show(self, depth=0):
159        """Traverse tree below self, dumping all information.
160        """
161        if depth == 0:
162            log.critical() 
163        print '%s%s'  % ('  '*depth, self.name), self.extents, ' [', \
164            self.leaves, ']'
165        if self.children:
166            log.critical()
167            for child in self.children:
168                child.show(depth+1)
169
170    def search(self, point):
171        """
172            Search the tree for intersection with leaves
173            point is a test point.
174            return a list of possible intersections with geometry.
175        """
176        intersecting_regions = self.test_leaves(point)
177       
178        # recurse down into nodes that the point passes through
179        if self.children:
180            for child in self.children:   
181                if child.extents.contains(point):
182                    intersecting_regions.extend(child.search(point))
183             
184        return intersecting_regions
185 
186 
187    def test_leaves(self, point):
188        """ Test all leaves to see if they intersect x.
189            x is a point to test
190            return a list of leaves that intersect x
191        """
192        intersecting_regions = []
193       
194        # test all leaves to see if they intersect the point
195        for leaf in self.leaves:
196            aabb, data = leaf
197            if aabb.contains(point):
198                intersecting_regions.append([data, self])
199               
200        return intersecting_regions               
201 
202 
203    def get_siblings(self):
204        """ return siblings of this node. If there is no parent, it
205                   returns an empty list.
206        """
207        if not self.parent:
208            return []
209         
210        siblings = list(self.parent.children)
211        siblings.remove(self)
212        return siblings
213               
Note: See TracBrowser for help on using the repository browser.