Changeset 7714

Timestamp:

May 11, 2010, 11:31:16 AM (15 years ago)

Author:

James Hudson

Message:

Minor refactorings and optimisations in quadtree search code

Location:

anuga_core/source/anuga

Files:

• fit_interpolate/search_functions.py (modified) (4 diffs)
• geometry/aabb.py (modified) (1 diff)
• geometry/quad.py (modified) (2 diffs)
• geometry/test_geometry.py (modified) (1 diff)

anuga_core/source/anuga/fit_interpolate/search_functions.py

@@ -72 +72 @@
             return True, sigma0, sigma1, sigma2, k
 
-    # search to bottom of tree from last found leaf
     branch = last_triangle[0][1]
     
     if branch == -10:
         branch = root   
-    
-    tri_data = branch.search(x[0], x[1])
+
+    # test neighbouring tris
+    tri_data = branch.test_leaves(x)
+    triangles = _trilist_from_data(mesh, tri_data)            
+    element_found, sigma0, sigma1, sigma2, k = \
+                _search_triangles_of_vertices(triangles, x)
+    if element_found:
+        return True, sigma0, sigma1, sigma2, k       
+
+    # search to bottom of tree from last found leaf    
+    tri_data = branch.search(x)
     triangles = _trilist_from_data(mesh, tri_data)            
     element_found, sigma0, sigma1, sigma2, k = \
@@ -95 +103 @@
             
         for sibling in siblings:
-            tri_data = sibling.search(x[0], x[1])
+            tri_data = sibling.search(x)
             triangles = _trilist_from_data(mesh, tri_data)            
             element_found, sigma0, sigma1, sigma2, k = \
@@ -104 +112 @@
         branch = branch.parent
         if branch:
-            tri_data = branch.test_leaves(x[0], x[1])
+            tri_data = branch.test_leaves(x)
             triangles = _trilist_from_data(mesh, tri_data)            
             element_found, sigma0, sigma1, sigma2, k = \
@@ -112 +120 @@
 
     return element_found, sigma0, sigma1, sigma2, k
-
-
-    ## Get triangles in the cell that the point is in.
-    #tri_data = root.search(x[0], x[1])
-    #triangles = _trilist_from_data(mesh, tri_data)
-    
-    #element_found, sigma0, sigma1, sigma2, k = \
-                   #_search_triangles_of_vertices(triangles, x)
-
-    #if element_found:
-        #return True, sigma0, sigma1, sigma2, k
 
 

anuga_core/source/anuga/geometry/aabb.py

@@ -68 +68 @@
         return True
  
-    def contains(self, x, y):
-        return (self.xmin <= x <= self.xmax) and (self.ymin <= y <= self.ymax)
+    def contains(self, x):
+        return (self.xmin <= x[0] <= self.xmax) and (self.ymin <= x[1] <= self.ymax)
         

anuga_core/source/anuga/geometry/quad.py

@@ -135 +135 @@
  
 
-    def search(self, x, y):
+    def search(self, x):
         """return a list of possible intersections with geometry"""
-
- #       if self.searched == [x,y]:
- #           print 'ERROR: already searched at ', [x,y]
- #       self.searched = [x,y]
         
-        intersecting_regions = self.test_leaves(x, y)
+        intersecting_regions = self.test_leaves(x)
         
         # recurse down into nodes that the point passes through
         if self.children:
             for child in self.children:    
-                if child.extents.contains(x, y):
-                    intersecting_regions.extend(child.search(x, y))
+                if child.extents.contains(x):
+                    intersecting_regions.extend(child.search(x))
              
         return intersecting_regions
  
  
-    def test_leaves(self, x, y):
+    def test_leaves(self, x):
         intersecting_regions = []
         
@@ -159 +155 @@
         for leaf in self.leaves:
             aabb, data = leaf
-            if aabb.contains(x, y):
+            if aabb.contains(x):
                 intersecting_regions.append((data, self))
                 

anuga_core/source/anuga/geometry/test_geometry.py

@@ -19 +19 @@
     def test_AABB_contains(self):
         box = AABB(1, 21, 1, 11)
-        assert box.contains(10, 5)
-        assert box.contains(1, 1)
-        assert box.contains(20, 6)
-        assert not box.contains(-1, -1)
-        assert not box.contains(5, 70)
-        assert not box.contains(6, -70)
-        assert not box.contains(-1, 6)
-        assert not box.contains(50, 6)        
+        assert box.contains([10, 5])
+        assert box.contains([1, 1])
+        assert box.contains([20, 6])
+        assert not box.contains([-1, -1])
+        assert not box.contains([5, 70])
+        assert not box.contains([6, -70])
+        assert not box.contains([-1, 6])
+        assert not box.contains([50, 6])        
         
     def test_AABB_split_vert(self):