Index: uga_core/source/anuga/geometry/mesh_quadtree.py
===================================================================
--- /anuga_core/source/anuga/geometry/mesh_quadtree.py	(revision 7751)
+++ 	(revision )
@@ -1,177 +1,0 @@
-"""
-General functions used in fit and interpolate.
-
-   Ole Nielsen, Stephen Roberts, Duncan Gray
-   Geoscience Australia, 2006.
-
-"""
-import time
-
-from anuga.utilities.numerical_tools import get_machine_precision
-from anuga.utilities.numerical_tools import ensure_numeric
-from anuga.config import max_float
-from quad import Cell
-from aabb import AABB
-
-from anuga.utilities import compile
-if compile.can_use_C_extension('polygon_ext.c'):
-    # Underlying C implementations can be accessed
-    from polygon_ext import _is_inside_triangle        
-else:
-    msg = 'C implementations could not be accessed by %s.\n ' %__file__
-    msg += 'Make sure compile_all.py has been run as described in '
-    msg += 'the ANUGA installation guide.'
-    raise Exception, msg
-
-import numpy as num
- 
-
-LAST_TRIANGLE = [[[-1, num.array([[max_float, max_float],
-                               [max_float, max_float],
-                               [max_float, max_float]]),
-                      num.array([[max_float, max_float],
-                               [max_float, max_float],
-                               [max_float, max_float]])], -10]]
-
-
-
-class MeshQuadtree(Cell):
-    """ A quadtree constructed from the given mesh.
-        This class is the root node of a quadtree,
-        and derives from a Cell.
-        It contains optimisations and search patterns specific to meshes.
-    """
-    def __init__(self, mesh):
-        """Build quad tree for mesh.
-
-        All vertex indices in the mesh are stored in a quadtree.
-        """
-        
-        extents = AABB(*mesh.get_extent(absolute=True))   
-        extents.grow(1.001) # To avoid round off error
-        Cell.__init__(self, extents, None)  # root has no parent
-        
-        N = len(mesh)
-        self.mesh = mesh
-        self.set_last_triangle()  
-
-        # Get x,y coordinates for all vertices for all triangles
-        V = mesh.get_vertex_coordinates(absolute=True)
-        
-        normals = mesh.get_normals()
-        
-        # Check each triangle
-        for i in range(N):
-            i3 = 3*i
-            x0, y0 = V[i3, :]
-            x1, y1 = V[i3+1, :]
-            x2, y2 = V[i3+2, :]
-
-            node_data = [i, V[i3:i3+3,:], normals[i,:]]
-
-            # insert a tuple with an AABB, and the triangle index as data
-            self._insert((AABB(min([x0, x1, x2]), max([x0, x1, x2]), \
-                             min([y0, y1, y2]), max([y0, y1, y2])), \
-                             node_data))
-
-    def search_fast(self, x):
-        """
-        Find the triangle (element) that the point x is in.
-
-        Inputs:
-            x:    The point to test
-        
-        Return:
-            element_found, sigma0, sigma1, sigma2, k
-
-            where
-            element_found: True if a triangle containing x was found
-            sigma0, sigma1, sigma2: The interpolated values
-            k: Index of triangle (if found)
-
-        """
-        
-        x = ensure_numeric(x, num.float)
-                 
-        # check the last triangle found first
-        element_found, sigma0, sigma1, sigma2, k = \
-                   self._search_triangles_of_vertices(self.last_triangle, x)
-        if element_found:
-            return True, sigma0, sigma1, sigma2, k
-
-        branch = self.last_triangle[0][1]
-
-        # test neighbouring tris
-        tri_data = branch.test_leaves(x)          
-        element_found, sigma0, sigma1, sigma2, k = \
-                    self._search_triangles_of_vertices(tri_data, x)
-        if element_found:
-            return True, sigma0, sigma1, sigma2, k       
-
-        # search rest of tree
-        element_found = False
-        next_search = [branch]
-        while branch:               
-            for sibling in next_search:
-                tri_data = sibling.search(x)         
-                element_found, sigma0, sigma1, sigma2, k = \
-                            self._search_triangles_of_vertices(tri_data, x)
-                if element_found:
-                    return True, sigma0, sigma1, sigma2, k
-            
-            next_search = branch.get_siblings()                            
-            branch = branch.parent
-            if branch:
-                tri_data = branch.test_leaves(x)     
-                element_found, sigma0, sigma1, sigma2, k = \
-                            self._search_triangles_of_vertices(tri_data, x)
-                if element_found:
-                    return True, sigma0, sigma1, sigma2, k      
-
-        return element_found, sigma0, sigma1, sigma2, k
-
-
-    def _search_triangles_of_vertices(self, triangles, x):
-        """Search for triangle containing x among triangle list
-
-        This is called by search_tree_of_vertices once the appropriate node
-        has been found from the quad tree.
-        
-        Input check disabled to speed things up. 
-        
-        x is the point to test 
-        triangles is the triangle list
-        return the found triangle and its interpolation sigma.
-        """  
-
-        for node_data in triangles:             
-            if bool(_is_inside_triangle(x, node_data[0][1], int(True), 1.0e-12, 1.0e-12)):
-                normals = node_data[0][2]      
-                n0 = normals[0:2]
-                n1 = normals[2:4]
-                n2 = normals[4:6]          
-                xi0, xi1, xi2 = node_data[0][1]
-
-                sigma0 = num.dot((x-xi1), n0)/num.dot((xi0-xi1), n0)
-                sigma1 = num.dot((x-xi2), n1)/num.dot((xi1-xi2), n1)
-                sigma2 = num.dot((x-xi0), n2)/num.dot((xi2-xi0), n2)              
-
-                # Don't look for any other triangles in the triangle list
-                self.last_triangle = [node_data]
-                return True, sigma0, sigma1, sigma2, node_data[0][0] # tri index                      
-        return False, -1, -1, -1, -10
-
-        
-        
-    def set_last_triangle(self):
-        """ Reset last triangle.
-            The algorithm is optimised to find nearby triangles to the
-            previously found one. This is called to reset the search to
-            the root of the tree.
-        """
-        self.last_triangle = LAST_TRIANGLE
-        self.last_triangle[0][1] = self # point at root by default          
-
-    
-
-                
Index: uga_core/source/anuga/geometry/test_meshquad.py
===================================================================
--- /anuga_core/source/anuga/geometry/test_meshquad.py	(revision 7751)
+++ 	(revision )
@@ -1,184 +1,0 @@
-import unittest
-import numpy as num
-
-from aabb import AABB
-from quad import Cell
-from mesh_quadtree import MeshQuadtree
-from anuga.abstract_2d_finite_volumes.general_mesh import General_mesh as Mesh
-
-import types, sys
-
-#-------------------------------------------------------------
-
-class Test_Quad(unittest.TestCase):
-
-    def setUp(self):
-        pass
-
-    def tearDown(self):
-        pass
-
-    def test_build_quadtree(self):
-
-        a = [3, 7]
-        b = [5, 7]
-        c = [5, 5]
-        d = [7, 7]
-        e = [15, 15]
-        f = [15, 30]
-        g = [30, 10]
-        h = [30, 30]
-
-        points = [a, b, c, d, e, f, g, h]
-        
-        #bac, bce, ecf, dbe, daf, dae
-        vertices = [[1,0,2], [1,3,4], [1,2,3], [5,4,7], [4,6,7]]
-
-        mesh = Mesh(points, vertices)
-    
-        Q = MeshQuadtree(mesh)
-        #Q.show()
-        #print Q.count()
-        self.assertEqual(Q.count(), len(vertices))
-
-        # test a point that falls within a triangle
-        result = Q.search([10, 10])
-        assert type(result) in [types.ListType,types.TupleType],\
-                            'should be a list'
-                            
-        self.assertEqual(result[0][0][0], 1)
-
-
-    def test_build_quadtreeII(self):
-
-        self.cell = Cell(AABB(100, 140, 0, 40), 'cell')
-
-        p0 = [34.6292076111,-7999.92529297]
-        p1 = [8000.0, 7999.0]
-        p2 = [-7999.96630859, 7999.0]
-        p3 = [34, 7999.97021484]
-
-        points = [p0,p1,p2, p3]
-        #bac, bce, ecf, dbe, daf, dae
-        vertices = [[0,1,2],[0,2,3]]
-
-        mesh = Mesh(points, vertices)
-
-        #This was causing round off error
-        Q = MeshQuadtree(mesh)
-        
-    def NOtest_interpolate_one_point_many_triangles(self):
-        # this test has 10 triangles that share the same vert.
-        # If the number of points per cell in  a quad tree is less
-        # than 10 it should crash 
-        z0 = [2.0, 5.0]
-        z1 = [2.0, 5.0]
-        z2 = [2.0, 5.0]
-        z3 = [2.0, 5.0]
-        z4 = [2.0, 5.0]
-        z5 = [2.0, 5.0]
-        z6 = [2.0, 5.0]
-        z7 = [2.0, 5.0]
-        z8 = [2.0, 5.0]
-        z9 = [2.0, 5.0]
-        z10 = [2.0, 5.0]
-        
-        v0 = [0.0, 0.0]
-        v1 = [1.0, 0.0]
-        v2 = [2.0, 0.0]
-        v3 = [3.0, 0.0]
-        v4 = [4.0, 0.0]
-        v5 = [0.0, 10.0]
-        v6 = [1.0, 10.0]
-        v7 = [2.0, 10.0]
-        v8 = [3.0, 10.0]
-        v9 = [4.0, 10.0]
-
-        vertices = [z0,v0, v1, v2, v3,v4 ,v5, v6, v7, v8, v9,
-                    z1, z2, z3, z4, z5, z6, z7, z8, z9]
-        triangles = [
-                      [11,1,2],
-                      [12,2,3],
-                      [13,3,4],
-                      [14,4,5],
-                      [7,6,15],
-                      [8,7,16],
-                      [9,8,17],
-                      [10,9,18],
-                      [6,1,19],
-                      [5,10,0]
-                      ]
-        
-        mesh = Mesh(vertices, triangles)
-        try:
-            Q = MeshQuadtree(mesh, max_points_per_cell = 9)
-        except RuntimeError:
-            pass
-        else:
-            self.failUnless(0 ==1,  'many verts at the same position no  \
-            longer causes as error')
-    
-    def test_retrieve_triangles(self):
-
-        cell = Cell(AABB(0, 6, 0, 6), 'cell')
-
-        p0 = [2,1]
-        p1 = [4,1]
-        p2 = [4.,4]
-        p3 = [2,4]
-        p4 = [5,4]
-
-        points = [p0,p1,p2, p3, p4]
-        #
-        vertices = [[0,1,2],[0,2,3],[1,4,2]]
-
-        mesh = Mesh(points, vertices)
-
-        Q = MeshQuadtree(mesh)
-        results = Q.search([4.5, 3])
-        assert len(results) == 1
-        self.assertEqual(results[0][0][0], 2)
-        results = Q.search([5,4.])
-        self.assertEqual(len(results),1)
-        self.assertEqual(results[0][0][0], 2)
-        
-    def NOtest_num_visits(self):
-        """ Test optimisation code.
-        """
-        a = [3, 7]
-        b = [5, 7]
-        c = [5, 5]
-        d = [7, 7]
-        e = [15, 15]
-        f = [15, 30]
-        g = [30, 10]
-        h = [30, 30]
-
-        points = [a, b, c, d, e, f, g, h]
-        
-        #bac, bce, ecf, dbe, daf, dae
-        vertices = [[1,0,2], [1,3,4], [1,2,3], [5,4,7], [4,6,7]]
-
-        mesh = Mesh(points, vertices)
-
-        Q = MeshQuadtree(mesh)    
-
-
-        results = Q.search_fast([5.5, 5.5])
-        print 'visits: ', Q.count_visits()
-        
-        Q.clear_visits()
-        results = Q.search_fast([30, 10])
-        print 'visits: ', Q.count_visits()
-        
-        print 'second time:'
-
-        Q.clear_visits()        
-        results = Q.search_fast([5.5, 5.5])
-        print 'visits: ', Q.count_visits()
-################################################################################
-
-if __name__ == "__main__":
-    mysuite = unittest.makeSuite(Test_Quad,'test')
-    runner = unittest.TextTestRunner()
-    runner.run(mysuite)
