Changeset 482


Ignore:
Timestamp:
Nov 3, 2004, 7:39:26 PM (20 years ago)
Author:
ole
Message:

Cleaned up, added unit tests, fixed bug in clear(),
changed split-semantics so that insert does not split automatically

Location:
inundation/ga/storm_surge/pyvolution
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • inundation/ga/storm_surge/pyvolution/cell.py

    r481 r482  
    66#FIXME add max min x y in general_mesh
    77
    8 #FIXME hacky.  maybe have as an attribute (or class att') for cell?
    9 MAX_WAY_POINTS = 4
    10 
    118class Cell(TreeNode):
    129    """class Cell
    … …  
    1613
    1714    Public Methods:
    18         Prune()
    19         Insert(Waypoint w)
    20         Search(Point p, [keywords c])
    21         Collapse()
    22         Split()
    23         Store()
    24         Retrieve()
    25         Count()
     15        prune()
     16        insert(point)
     17        search(x, y)
     18        collapse()
     19        split()
     20        store()
     21        retrieve()
     22        count()
    2623    """
    2724 
    28     def __init__(self, southern, northern, western, eastern, name):
     25    def __init__(self, southern, northern, western, eastern,
     26                 name = 'cell',
     27                 max_points_per_cell = 4):
    2928 
    3029        # Initialise base classes
    3130        TreeNode.__init__(self, string.lower(name))
     31       
    3232        # Initialise cell
    3333        self.southern = round(southern,5)   
    … …  
    3636        self.eastern = round(eastern,5)
    3737
    38         # Corners
    39         #self.SW = Point(self.southern,self.western)
    40         #self.NW = Point(self.northern,self.western)
    41         #self.NE = Point(self.northern,self.eastern)
    42         #self.SE = Point(self.southern,self.eastern)
    43 
    4438        # The points in this cell     
    4539        self.points = []
    46        
     40       
     41        self.max_points_per_cell = max_points_per_cell
     42       
     43       
    4744    def __repr__(self):
    4845        return self.name 
    4946
    5047
    51     def Spawn(self):
     48    def spawn(self):
    5249        """Create four child cells unless they already exist
    5350        """
    … …  
    7269 
    7370
    74     def Search(self, x,y):
    75         """Find all waypoints within given radius from point P meeting
    76         specified keywords (an optional comma-separated string).
     71    def search(self, x,y):
     72        """Find all points within given radius from point P
    7773        """
    7874     
    79         waypoints = []
     75        points = []
    8076        if self.children:
    8177            for child in self:
    82                 if child.Contains(None,x=x,y=y):
    83                      waypoints += child.Search(x,y)
     78                if child.contains(x,y):
     79                     points += child.search(x,y)
    8480        else:
    8581            # Leaf node: Get actual waypoints
    86             waypoints = self.Retrieve()
     82            points = self.retrieve()
    8783           
    88         return waypoints
    89 
    90 
    91 
    92     def Contains(self, point_id, x= 0, y= 0):
     84        return points
     85
     86
     87
     88    def contains(*args):   
    9389        """True only if P's coordinates lie within cell boundaries
    94         """
    95 
    96         if point_id <> None:
    97             x = self.__class__.domain.coordinates[point_id][0]
    98             y = self.__class__.domain.coordinates[point_id][1]
    99         #print "x",x
    100         #print "y",y
    101         #print "self.southern",self.southern
    102         #print "self.northern",self.northern
    103         #print "self.western",self.western
    104         #print "self.eastern",self.eastern
    105         if y <  self.southern: return 0
    106         if y >= self.northern: return 0
    107         if x <  self.western:  return 0
    108         if x >= self.eastern:  return 0
    109         return 1
    110    
    111     def Contains_old(self, P):
    112         """True only if P's coordinates lie within cell boundaries
    113         """
    114    
    115         if P.latitude  <  self.southern: return 0
    116         if P.latitude  >= self.northern: return 0
    117         if P.longitude <  self.western:  return 0
    118         if P.longitude >= self.eastern:  return 0
    119         return 1
     90        This methods has two forms:
     91       
     92        cell.contains(index)
     93          #True if cell contains indexed point
     94        cell.contains(x, y)
     95          #True if cell contains point (x,y)   
     96
     97        """
     98       
     99        self = args[0]
     100        if len(args) == 2:
     101            point_id = int(args[1])
     102            x = self.__class__.mesh.coordinates[point_id][0]
     103            y = self.__class__.mesh.coordinates[point_id][1]       
     104        elif len(args) == 3:
     105            x = float(args[1])
     106            y = float(args[2])
     107        else:
     108            msg = 'Number of arguments to method must be two or three'
     109            raise msg                         
     110       
     111        if y <  self.southern: return False
     112        if y >= self.northern: return False
     113        if x <  self.western:  return False
     114        if x >= self.eastern:  return False
     115        return True
    120116   
    121117   
    122     def Insert(self, W):
    123         """Insert waypoint in existing tree structure below self
    124            and split if necessary
     118    def insert(self, points, split = False):
     119        """insert point(s) in existing tree structure below self
     120           and split if requested
    125121        """
    126122 
    127         # Call insert for each element of a list of waypoints
    128         if type(W) == types.ListType:
    129             for w in W:
    130                 self.Insert(w)
    131             return
    132    
    133         # Find appropriate cell
    134         if self.children:
    135             for child in self:
    136                 if child.Contains(W):
    137                     child.Insert(W)
    138                     break
    139         else:
    140             # Cell is a leaf cell. Insert waypoint in database table
    141             if self.Contains(W):
    142                 self.Store(W)
    143                
    144                 #FIXME? - where was this called before? 
    145                 self.Split()
     123        # Call insert for each element of a list of points
     124        if type(points) == types.ListType:
     125            for point in points:
     126                self.insert(point, split)
     127        else:
     128            #Only one point given as argument   
     129            point = points
     130       
     131            # Find appropriate cell
     132            if self.children is not None:
     133                for child in self:
     134                    if child.contains(point):
     135                        child.insert(point, split)
     136                        break
    146137            else:
    147                 #FIXME rasie exception
    148                raise "point not in region"
    149 
    150 
    151     def Store(self,objects):
    152         #import storage
    153         #storage = storage.Factory()
     138                # self is a leaf cell: insert point into cell
     139                if self.contains(point):
     140                    self.store(point)
     141                else:
     142                    raise 'point not in region'
     143               
     144               
     145        #Split datastructure if requested       
     146        if split is True:
     147            self.split()
     148               
     149
     150
     151    def store(self,objects):
    154152       
    155153        if type(objects) not in [types.ListType,types.TupleType]:
    … …  
    157155        else:
    158156            self.points.extend(objects)
    159            
    160         #for object in objects:
    161         #    storage.Store(self.name,object)
    162 
    163 
    164 
    165     def Retrieve(self):
     157
     158
     159    def retrieve(self):
    166160         objects = []
    167161         if self.children is None:
    … …  
    169163         else: 
    170164             for child in self:
    171                  objects += child.Retrieve()
     165                 objects += child.retrieve()
    172166         return objects 
    173167
    174168
    175     def Count(self, keywords=None):
    176         """Retrieve number of stored objects beneath this node inclusive
     169    def count(self, keywords=None):
     170        """retrieve number of stored objects beneath this node inclusive
    177171        """
    178172       
    … …  
    180174        if self.children:
    181175            for child in self:
    182                 num_waypoint = num_waypoint + child.Count()
     176                num_waypoint = num_waypoint + child.count()
    183177        else:
    184178            num_waypoint = len(self.points)
    … …  
    186180 
    187181
    188     def Clear(self):
     182    def clear(self):
    189183        self.Prune()   # TreeNode method
    190184
    191185
    192     def ClearLeafNode(self):
     186    def clear_leaf_node(self):
     187        """Clears storage in leaf node.
     188        Called from Treenod.
     189        Must exist.     
     190        """
    193191        self.points = []
    194 
    195 
    196 
    197     def Split(self, threshold=None):
     192       
     193       
     194    def clear_internal_node(self):
     195        """Called from Treenode.   
     196        Must exist.
     197        """
     198        pass
     199
     200
     201
     202    def split(self, threshold=None):
    198203        """
    199204        Partition cell when number of contained waypoints exceeds
    … …  
    201206        child cell.
    202207        """
    203         if  threshold == None:
    204             threshold = MAX_WAY_POINTS
    205         #FIXME, mincellsize removed.  base it on side lenght, if needed
    206        
     208        if threshold == None:
     209           threshold = self.max_points_per_cell
     210           
     211        #FIXME, mincellsize removed.  base it on side length, if needed
     212       
     213        #Protect against silly thresholds such as -1
     214        if threshold < 1:
     215            return
     216       
    207217        if not self.children:               # Leaf cell
    208             if self.Count() > threshold : #and self.radius > mincellsize:
     218            if self.count() > threshold :   
     219                #Split is needed
     220                points = self.retrieve()    # Get points from leaf cell
     221                self.clear()                # and remove them from storage
    209222               
    210                 waypoints = self.Retrieve() # Get waypoints from leaf cell
    211                 self.Clear()                # and remove them from storage
    212                
    213                 self.Spawn()                # Spawn child cells and move
    214                 for wp in waypoints:        # waypoints to appropriate child
     223                self.spawn()                # Spawn child cells and move
     224                for p in points:            # points to appropriate child
    215225                    for child in self:
    216                         if child.Contains(wp):
    217                             child.Insert(wp)
     226                        if child.contains(p):
     227                            child.insert(p)
    218228                            break
    219229   
    220230        if self.children:                   # Parent cell
    221             for child in self:              # Split (possibly newly created)
    222                 child.Split(threshold)      # child cells recursively
     231            for child in self:              # split (possibly newly created)
     232                child.split(threshold)      # child cells recursively
    223233               
    224234
    225235
    226     def Collapse(self,threshold=None):
    227         """
    228         Collapse child cells into immediate parent if total number of contained waypoints
     236    def collapse(self,threshold=None):
     237        """
     238        collapse child cells into immediate parent if total number of contained waypoints
    229239        in subtree below is less than or equal to threshold.
    230240        All waypoints are then moved into parent cell and
    … …  
    233243       
    234244        if threshold is None:
    235             threshold = config['maxwaypoints']
     245            threshold = self.max_points_per_cell       
     246
    236247
    237248        if self.children:                   # Parent cell   
    238             if self.Count() <= threshold:   # Collapse
    239                 waypoints = self.Retrieve() # Get all waypoints from child cells
    240                 self.Clear()                # Remove children, self is now a leaf node
    241                 self.Insert(waypoints)      # Insert all waypoints in local storage
     249            if self.count() <= threshold:   # collapse
     250                points = self.retrieve()    # Get all points from child cells
     251                self.clear()                # Remove children, self is now a leaf node
     252                self.insert(points)         # Insert all points in local storage
    242253            else:                         
    243254                for child in self:          # Check if any sub tree can be collapsed
    244                     child.Collapse(threshold)
     255                    child.collapse(threshold)
    245256
    246257
    … …  
    260271                s += child.Get_tree(depth+1)
    261272        else:
    262             s += '(#wp=%d)\n' %(self.Count())
     273            s += '(#wp=%d)\n' %(self.count())
    263274
    264275        return s
    265276
    266     def Show(self,depth=0):
     277       
     278    def show(self, depth=0):
    267279        """Traverse tree below self
    268280           Print for each node the name and
    … …  
    271283        if depth == 0:
    272284            print
    273         print "%s%s:" % ('  '*depth, self.name),
     285        print "%s%s" % ('  '*depth, self.name),
    274286        if self.children:
    275287            print
    276288            for child in self.children:
    277                 child.Show(depth+1)
    278         else:
    279             print '#wp=%d, c=(%.2f,%.2f)'\
    280                   %(self.Count(), self.latitude, self.longitude)
    281 
    282            
    283 
    284     def ShowAll(self,depth=0):
     289                child.show(depth+1)
     290        else:
     291            print '(xmin=%.2f, xmax=%.2f, ymin=%.2f, ymax=%.2f): [%d]'\
     292                  %(self.western, self.eastern,
     293                    self.southern, self.northern,
     294                    self.count())
     295
     296
     297    def show_all(self,depth=0):
    285298        """Traverse tree below self
    286299           Print for each node the name and if it is a leaf all its objects
    … …  
    292305            print
    293306            for child in self.children:
    294                 child.ShowAll(depth+1)
    295         else:
    296             print '%s' %self.Retrieve()
    297 
    298 
    299     def Stats(self,depth=0,min_rad=sys.maxint,max_depth=0,max_points=0):
     307                child.show_all(depth+1)
     308        else:
     309            print '%s' %self.retrieve()
     310
     311
     312    def stats(self,depth=0,min_rad=sys.maxint,max_depth=0,max_points=0):
    300313        """Traverse tree below self and find minimal cell radius,
    301314           maximumtree depth and maximum number of waypoints per leaf.
    … …  
    308321        else:
    309322            #FIXME remvoe radius stuff
    310             min_rad = sys.maxint
     323            #min_rad = sys.maxint
    311324            #if self.radius < min_rad:   min_rad = self.radius
    312             if depth > max_depth:       max_depth = depth
    313             num_points = self.Count()
     325            if depth > max_depth: max_depth = depth
     326            num_points = self.count()
    314327            if num_points > max_points: max_points = num_points
    315328
    316         return min_rad, max_depth, max_points   
    317 
    318     def initialise(cls,domain):
    319         cls.domain = domain
     329        #return min_rad, max_depth, max_points   
     330        return max_depth, max_points   
     331       
     332
     333    #Class initialisation method       
     334    def initialise(cls, mesh):
     335        cls.mesh = mesh
    320336
    321337    initialise = classmethod(initialise)

  • inundation/ga/storm_surge/pyvolution/general_mesh.py

    r343 r482  
    11   
    2 class General_Mesh:
     2class General_mesh:
    33    """Collection of triangular elements (purely geometric)
    44

  • inundation/ga/storm_surge/pyvolution/least_squares.py

    r479 r482  
    2525class ShapeError(exceptions.Exception): pass
    2626
    27 from general_mesh import General_Mesh
     27from general_mesh import General_mesh
    2828from Numeric import zeros, array, Float, Int, dot, transpose
    2929from LinearAlgebra import solve_linear_equations
    … …  
    174174       
    175175        #Build underlying mesh
    176         self.mesh = General_Mesh(vertex_coordinates, triangles)
     176        self.mesh = General_mesh(vertex_coordinates, triangles)
    177177
    178178        #Smoothing parameter

  • inundation/ga/storm_surge/pyvolution/mesh.py

    r415 r482  
    55"""
    66
    7 from general_mesh import General_Mesh
    8 
    9 class Mesh(General_Mesh):
     7from general_mesh import General_mesh
     8
     9class Mesh(General_mesh):
    1010    """Collection of triangular elements (purely geometric)
    1111
    … …  
    6767        from Numeric import array, zeros, Int, Float, maximum, sqrt, sum
    6868
    69         General_Mesh.__init__(self,coordinates, triangles)
     69        General_mesh.__init__(self,coordinates, triangles)
    7070
    7171        N = self.number_of_elements
    … …  
    205205       
    206206        Postcondition:
    207           self.vertexlist is build
     207          self.vertexlist is built
    208208        """
    209209

  • inundation/ga/storm_surge/pyvolution/test_cell.py

    r481 r482  
    22from cell import Cell
    33
    4 from domain import *
     4#from domain import *
     5from general_mesh import General_mesh as Mesh
    56
    67import types, sys
    … …  
    1112
    1213    def setUp(self):
    13         self.cell = Cell(100,140,0,40,'cell')
     14        self.cell = Cell(100, 140, 0, 40, 'cell')
    1415       
    1516        a = [3, 107]
    … …  
    2627        vertices = [ [1,0,2],[1,3,4], [1,2,3], [5,4,7], [4,6,7]]
    2728
    28         conserved_quantities = ['level', 'xmomentum', 'ymomentum']
    29         other_quantities = ['elevation', 'friction']
    30        
    31         domain = Domain(points, vertices, None,
    32                         conserved_quantities, other_quantities)
    33         Cell.initialise(domain)
     29        #FIXME: Why?
     30        #conserved_quantities = ['level', 'xmomentum', 'ymomentum']
     31        #other_quantities = ['elevation', 'friction']
     32        #domain = Domain(points, vertices, None,
     33        #                conserved_quantities, other_quantities)
     34       
     35        mesh = Mesh(points, vertices)
     36        Cell.initialise(mesh)
    3437       
    3538    def tearDown(self):
    … …  
    3740
    3841    def test_add_points_2_cell(self):
    39         self.cell.Insert(0)
    40         self.cell.Insert(1)
     42        self.cell.insert(0)
     43        self.cell.insert(1)
    4144       
    42         result = self.cell.Retrieve()
    43         #result = self.cell.Get_tree()
    44         #print  result
    45         assert type(result) in [types.ListType,types.TupleType], 'should be a list'       
     45        result = self.cell.retrieve()
     46        assert type(result) in [types.ListType,types.TupleType],\
     47                                'should be a list'       
    4648        self.assertEqual(len(result),2)
    4749       
    4850    def test_add_points_2_cellII(self):
    49         self.cell.Insert([0,1,2,3,4,5,6,7])
     51        self.cell.insert([0,1,2,3,4,5,6,7])
    5052       
    51         result = self.cell.Retrieve()
    52         #result = self.cell.Get_tree()
    53         #print  result
    54         assert type(result) in [types.ListType,types.TupleType], 'should be a list'       
     53        result = self.cell.retrieve()
     54        assert type(result) in [types.ListType,types.TupleType],\
     55                                'should be a list'       
    5556        self.assertEqual(len(result),8)
    5657
    5758
    5859    def test_search(self):
    59         self.cell.Insert([0,1,2,3,4,5,6,7])
     60        self.cell.insert([0,1,2,3,4,5,6,7])
     61        self.cell.split(4)
    6062       
    61         result =  self.cell.Search(x = 1, y = 101)
    62         assert type(result) in [types.ListType,types.TupleType], 'should be a list'       
     63        result =  self.cell.search(x = 1, y = 101)
     64        assert type(result) in [types.ListType,types.TupleType],\
     65                                'should be a list'       
    6366        self.assertEqual(result, [0,1,2,3])
     67       
     68       
     69    def test_clear_1(self):
     70        self.cell.insert([0,1,2,3,4,5,6,7])
     71        assert self.cell.count() == 8   
     72        self.cell.clear()
     73       
     74        #This one actually revealed a bug :-)
     75        assert self.cell.count() == 0   
     76               
     77    def test_clear_2(self):
     78        self.cell.insert([0,1,2,3,4,5,6,7])
     79        assert self.cell.count() == 8   
     80        self.cell.split(2)
     81        assert self.cell.count() == 8           
     82               
     83        self.cell.clear()
     84        assert self.cell.count() == 0   
     85       
     86       
     87       
     88    def test_split(self):
     89        self.cell.insert([0,1,2,3,4,5,6,7], split = False)   
     90       
     91        #No children yet
     92        assert self.cell.children is None
     93        assert self.cell.count() == 8
     94
     95        #Split
     96        self.cell.split(4)
     97        #self.cell.show()
     98        #self.cell.show_all()
     99       
     100       
     101        #Now there are children
     102        assert self.cell.children is not None
     103        assert self.cell.count() == 8   
     104       
     105       
     106               
     107    def test_collapse(self):
     108        self.cell.insert([0,1,2,3,4,5,6,7], split = False)   
     109       
     110        #Split maximally
     111        self.cell.split(1)
     112       
     113        #Now there are children
     114        assert self.cell.children is not None
     115        assert self.cell.count() == 8   
     116       
     117        #Collapse
     118        self.cell.collapse(8)
     119       
     120       
     121        #No children
     122        assert self.cell.children is None
     123        assert self.cell.count() == 8   
    64124
    65125#-------------------------------------------------------------

  • inundation/ga/storm_surge/pyvolution/treenode.py

    r480 r482  
    8585    def Prune(self):
    8686        if self.children is None:                  # Leaf node
    87             if callable(self.ClearLeafNode):
    88                 self.ClearLeafNode()
     87            if callable(self.clear_leaf_node):
     88                self.clear_leaf_node()
     89            else:
     90                msg = 'Node must have a method named "clear_leaf_node"'
     91                raise msg       
    8992        else:
    90             if callable(self.ClearInternalNode):   # Internal node
    91                 self.ClearInternalNode()
     93            if callable(self.clear_internal_node):   # Internal node
     94                self.clear_internal_node()
     95            else:
     96                msg = 'Node must have a method named "clear_internal_node"'
     97                raise msg       
     98                               
    9299            for child in self.children:
    93100                child.Prune()
Note: See TracChangeset for help on using the changeset viewer.