Changeset 7721 for anuga_core
- Timestamp:
- May 12, 2010, 2:45:56 PM (15 years ago)
- Location:
- anuga_core/source/anuga/geometry
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
anuga_core/source/anuga/geometry/aabb.py
r7714 r7721 4 4 class AABB: 5 5 """Axially-aligned bounding box class. 6 Defines a box which can check for intersections with other boxes, 7 or if a point lies within it. 6 8 """ 7 9 … … 40 42 41 43 def split(self, border=SPLIT_BORDER_RATIO): 42 """Split along shorter axis. 43 return 2 subdivided AABBs. 44 """Split box along shorter axis. 45 return 2 subdivided AABBs. This is useful for recursive 46 algorithms. 47 48 border is the overlap between the 2 regions - if set to 0.5 49 it will subdivide them exactly, > 0.5 will create a 50 shared overlapping area. 44 51 """ 45 52 … … 59 66 def is_trivial_in(self, test): 60 67 """ Is trivial in. 61 test an x,y point to test against the bounding box 62 return True if the test point falls within the bounding box 68 test a box to test against the bounding box 69 return True if the test box falls fully within the 70 bounding box without intersecting it. 63 71 """ 64 72 if (test.xmin < self.xmin) or (test.xmax > self.xmax): … … 69 77 70 78 def contains(self, x): 79 """ is point within box 80 x is a test point 81 return True if the point is contained within the box. 82 """ 71 83 return (self.xmin <= x[0] <= self.xmax) and (self.ymin <= x[1] <= self.ymax) 72 84 -
anuga_core/source/anuga/geometry/mesh_quadtree.py
r7719 r7721 80 80 81 81 Inputs: 82 root: A quad tree of the vertices 83 mesh: The mesh which the quad tree indexes into 84 x: The point being placed 82 x: The point to test 85 83 86 84 Return: … … 135 133 136 134 def _search_triangles_of_vertices(self, triangles, x): 137 """Search for triangle containing x among s candidate_vertices in triangles135 """Search for triangle containing x among triangle list 138 136 139 137 This is called by search_tree_of_vertices once the appropriate node 140 138 has been found from the quad tree. 141 139 142 x is the triangle index 143 Input check disabled to speed things up. 140 Input check disabled to speed things up. 141 142 x is the point to test 143 triangles is the triangle list 144 return the found triangle and its interpolation sigma. 144 145 """ 145 146 … … 164 165 165 166 def set_last_triangle(self): 167 """ Reset last triangle. 168 The algorithm is optimised to find nearby triangles to the 169 previously found one. This is called to reset the search to 170 the root of the tree. 171 """ 166 172 self.last_triangle = LAST_TRIANGLE 167 173 self.last_triangle[0][1] = self # point at root by default -
anuga_core/source/anuga/geometry/quad.py
r7720 r7721 2 2 3 3 This is a generic structure that can be used to store any geometry in a quadtree. 4 4 It is naive, and does not exploit any coherency - it merely tests a bounding 5 box against all other bounding boxes in its heirarchy. 6 7 It returns a list of bounding boxes which intersect with the test box, which 8 must then be iterated over to detect actual intersections. 5 9 6 10 """ … … 15 19 """class Cell 16 20 17 One cell in the plane delimited by southern, northern, 18 western, eastern boundaries. 21 One cell in the plane. 19 22 """ 20 23 21 24 def __init__(self, extents, parent, 22 25 name = 'cell'): 26 """ Construct a new cell. 27 extents is an AABB defining a region on the plane. 28 parent is the node above this one, or None if it is root. 29 """ 23 30 24 31 # Initialise base classes … … 62 69 63 70 def insert(self, new_leaf): 64 # process list items sequentially 71 """ Insert a leaf into the quadtree. 72 new_leaf is a tuple of (AABB extents, data), where data can 73 be any user data (geometry, triangle index, etc.). 74 """ 65 75 if type(new_leaf)==type(list()): 66 76 for leaf in new_leaf: … … 71 81 72 82 def _insert(self, new_leaf): 83 """ Internal recursive insert. 84 new_leaf is a tuple of (AABB extents, data), where data can 85 be any user data (geometry, triangle index, etc.). 86 """ 73 87 new_region, data = new_leaf 74 88 … … 93 107 #return 94 108 95 # option 2 - try splitting 2 ways 109 # option 2 - try splitting 2 ways - no diff noticed in practise 96 110 if subregion1.is_trivial_in(new_region): 97 111 self.children = [Cell(subregion1, self), Cell(subregion2, self)] … … 108 122 109 123 def retrieve(self): 110 """Get all leaves from this tree. """ 124 """Get all leaves from this tree. 125 return a traversal of the entire tree. 126 """ 111 127 112 128 leaves_found = list(self.leaves) … … 121 137 122 138 def count(self): 123 """Count all leaves from this tree. """ 139 """Count all leaves from this tree. 140 return num of leaves in the tree. 141 """ 124 142 125 143 leaves_found = len(self.leaves) … … 134 152 135 153 def show(self, depth=0): 136 """Traverse tree below self 154 """Traverse tree below self, dumping all information. 137 155 """ 138 156 if depth == 0: … … 159 177 160 178 def test_leaves(self, x): 179 """ Test all leaves to see if they intersect x. 180 x is a point to test 181 return a list of leaves that intersect x 182 """ 161 183 intersecting_regions = [] 162 184 … … 171 193 172 194 def get_siblings(self): 173 """ return parent and siblings of this node. 195 """ return siblings of this node. If there is no parent, it 196 returns an empty list. 174 197 """ 175 198 if not self.parent:
Note: See TracChangeset
for help on using the changeset viewer.
