source: anuga_core/source/anuga/geometry/quad.py @ 7751

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

Refactorings from May ANUGA meeting.

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