| 1 | """ |
|---|
| 2 | Quadtree representation of 2D mesh geometry. |
|---|
| 3 | |
|---|
| 4 | Ole Nielsen, Stephen Roberts, Duncan Gray |
|---|
| 5 | Geoscience Australia, 2006. |
|---|
| 6 | |
|---|
| 7 | |
|---|
| 8 | PADARN NOTE 06/12/12: This quad tree has been |
|---|
| 9 | replaced by a C quad tree. Save the old code |
|---|
| 10 | somewhere? |
|---|
| 11 | |
|---|
| 12 | PADARN NOTE: Most of the functionality of the |
|---|
| 13 | old quad tree has been emulated. However, some |
|---|
| 14 | methods inherrited from cell have not been. This |
|---|
| 15 | causes a few of the unit tests to fail, and thus |
|---|
| 16 | can easily be identified if it is felt the are |
|---|
| 17 | needed. |
|---|
| 18 | |
|---|
| 19 | """ |
|---|
| 20 | |
|---|
| 21 | from anuga.config import max_float |
|---|
| 22 | |
|---|
| 23 | from anuga.geometry.quad import Cell |
|---|
| 24 | from anuga.geometry.aabb import AABB |
|---|
| 25 | |
|---|
| 26 | import numpy as num |
|---|
| 27 | from anuga.utilities.numerical_tools import ensure_numeric |
|---|
| 28 | import anuga.fit_interpolate.fitsmooth as fitsmooth |
|---|
| 29 | |
|---|
| 30 | |
|---|
| 31 | # PADARN NOTE: I don't think much from Cell is used anymore, if |
|---|
| 32 | # anything, this dependency could be removed. |
|---|
| 33 | class MeshQuadtree(Cell): |
|---|
| 34 | """ A quadtree constructed from the given mesh. |
|---|
| 35 | This class is the root node of a quadtree, |
|---|
| 36 | and derives from a Cell. |
|---|
| 37 | It contains optimisations and search patterns specific to meshes. |
|---|
| 38 | """ |
|---|
| 39 | |
|---|
| 40 | def __init__(self, mesh, verbose=False): |
|---|
| 41 | """Build quad tree for mesh. |
|---|
| 42 | |
|---|
| 43 | All vertex indices in the mesh are stored in a quadtree. |
|---|
| 44 | """ |
|---|
| 45 | self.mesh = mesh |
|---|
| 46 | |
|---|
| 47 | self.set_extents() |
|---|
| 48 | self.add_quad_tree() |
|---|
| 49 | |
|---|
| 50 | Cell.__init__(self, self.extents, None) # root has no parent |
|---|
| 51 | |
|---|
| 52 | |
|---|
| 53 | def __getstate__(self): |
|---|
| 54 | dic = self.__dict__ |
|---|
| 55 | if (dic.has_key('root')): |
|---|
| 56 | dic.pop('root') |
|---|
| 57 | return dic |
|---|
| 58 | |
|---|
| 59 | def set_extents(self): |
|---|
| 60 | extents = AABB(*self.mesh.get_extent(absolute=True)) |
|---|
| 61 | extents.grow(1.001) # To avoid round off error |
|---|
| 62 | numextents = [extents.xmin, extents.xmax, extents.ymin, extents.ymax] |
|---|
| 63 | self.extents = num.array(numextents, num.float) |
|---|
| 64 | #print self.extents |
|---|
| 65 | |
|---|
| 66 | def add_quad_tree(self): |
|---|
| 67 | |
|---|
| 68 | V = self.mesh.get_vertex_coordinates(absolute=True) |
|---|
| 69 | |
|---|
| 70 | self.set_extents() |
|---|
| 71 | #print self.extents |
|---|
| 72 | self.root = fitsmooth.build_quad_tree(self.mesh.triangles, V, self.extents) |
|---|
| 73 | |
|---|
| 74 | |
|---|
| 75 | # PADARN NOTE: This function does not properly emulate the old functionality - |
|---|
| 76 | # it seems uneeded though. Check this. |
|---|
| 77 | def search(self, point): |
|---|
| 78 | return self.search_fast(point) |
|---|
| 79 | |
|---|
| 80 | # PADARN NOTE: Although this function emulates the functionality of the old |
|---|
| 81 | # quad tree, it cannot be called on the sub-trees anymore. |
|---|
| 82 | def count(self): |
|---|
| 83 | if not hasattr(self, 'root'): |
|---|
| 84 | self.add_quad_tree() |
|---|
| 85 | return fitsmooth.items_in_tree(self.root) |
|---|
| 86 | |
|---|
| 87 | def search_fast(self, point): |
|---|
| 88 | """ |
|---|
| 89 | Find the triangle (element) that the point x is in. |
|---|
| 90 | |
|---|
| 91 | Does a coherent quadtree traversal to return a single triangle that the |
|---|
| 92 | point falls within. The traversal begins at the last triangle found. |
|---|
| 93 | If this fails, it checks the triangles beneath it in the tree, and then |
|---|
| 94 | begins traversing up through the tree until it reaches the root. |
|---|
| 95 | |
|---|
| 96 | This results in performance which varies between constant time and O(n), |
|---|
| 97 | depending on the geometry. |
|---|
| 98 | |
|---|
| 99 | Inputs: |
|---|
| 100 | point: The point to test |
|---|
| 101 | |
|---|
| 102 | Return: |
|---|
| 103 | element_found, sigma0, sigma1, sigma2, k |
|---|
| 104 | |
|---|
| 105 | where |
|---|
| 106 | element_found: True if a triangle containing x was found |
|---|
| 107 | sigma0, sigma1, sigma2: The interpolated values |
|---|
| 108 | k: Index of triangle (if found) |
|---|
| 109 | |
|---|
| 110 | """ |
|---|
| 111 | |
|---|
| 112 | # PADARN NOTE: Adding checks on the input point to make sure it is a float. |
|---|
| 113 | |
|---|
| 114 | if not hasattr(self, 'root'): |
|---|
| 115 | self.add_quad_tree() |
|---|
| 116 | |
|---|
| 117 | point = ensure_numeric(point, num.float) |
|---|
| 118 | |
|---|
| 119 | [found, sigma, index] = fitsmooth.individual_tree_search(self.root, point) |
|---|
| 120 | |
|---|
| 121 | if found == 1: |
|---|
| 122 | element_found = True |
|---|
| 123 | else: |
|---|
| 124 | element_found = False |
|---|
| 125 | |
|---|
| 126 | return element_found, sigma[0], sigma[1], sigma[2], index |
|---|
| 127 | |
|---|
| 128 | # PADARN NOTE: Only here to pass unit tests - does nothing. |
|---|
| 129 | def set_last_triangle(self): |
|---|
| 130 | pass |
|---|
