Changeset 1667

Show
Ignore:
Timestamp:
07/18/07 05:34:53 (1 year ago)
Author:
arj..@yirdis.nl
Message:

more quadtree updates

Files:

Legend:

Unmodified
Added
Removed
Modified
Copied
Moved

  • gaphas/trunk/gaphas/quadtree.py

    r1666 r1667  
    3131    >>> len(qtree) 
    3232    20 
     33    >>> qtree.dump() # doctest: +ELLIPSIS 
     34     <__main__.QuadtreeBucket object at 0x...> (0, 0, 100, 100) 
     35       11 (44, 20, 10, 10) 
     36       12 (48, 30, 10, 10) 
     37       <__main__.QuadtreeBucket object at 0x...> (0, 0, 50.0, 50.0) 
     38         0 (0, 0, 10, 10) 
     39         1 (4, 10, 10, 10) 
     40         2 (8, 20, 10, 10) 
     41         3 (12, 30, 10, 10) 
     42         4 (16, 40, 10, 10) 
     43         9 (36, 0, 10, 10) 
     44         10 (40, 10, 10, 10) 
     45       <__main__.QuadtreeBucket object at 0x...> (50.0, 0, 50.0, 50.0) 
     46         13 (52, 40, 10, 10) 
     47         18 (72, 0, 10, 10) 
     48         19 (76, 10, 10, 10) 
     49       <__main__.QuadtreeBucket object at 0x...> (0, 50.0, 50.0, 50.0) 
     50         5 (20, 50, 10, 10) 
     51         6 (24, 60, 10, 10) 
     52         7 (28, 70, 10, 10) 
     53         8 (32, 80, 10, 10) 
     54       <__main__.QuadtreeBucket object at 0x...> (50.0, 50.0, 50.0, 50.0) 
     55         14 (56, 50, 10, 10) 
     56         15 (60, 60, 10, 10) 
     57         16 (64, 70, 10, 10) 
     58         17 (68, 80, 10, 10) 
    3359 
    3460    Find all items in the tree:: 
    …… 
    4369    >>> [qtree.get_bounds(item) for item in qtree.find_inside((40, 40, 40, 40))] 
    4470    [(52, 40, 10, 10), (56, 50, 10, 10), (60, 60, 10, 10), (64, 70, 10, 10)] 
     71 
     72    >>> qtree.find_intersect((40, 40, 20, 20)) 
     73    ['12', '13', '14', '15'] 
     74    >>> [qtree.get_bounds(item) for item in qtree.find_intersect((40, 40, 20, 20))] 
     75    [(48, 30, 10, 10), (52, 40, 10, 10), (56, 50, 10, 10), (60, 60, 10, 10)] 
     76 
    4577    """ 
    4678 
    …… 
    113145        return len(self._ids) 
    114146 
     147    def dump(self): 
     148        """ 
     149        Print structure to stdout. 
     150        """ 
     151        self._bucket.dump() 
     152 
    115153 
    116154class QuadtreeBucket(object): 
    …… 
    138176        """ 
    139177        # create new subnodes if threshold is reached 
    140         if not self._buckets and len(self._items) > QuadtreeBucket.CAPACITY: 
     178        if not self._buckets and len(self._items) >= QuadtreeBucket.CAPACITY: 
    141179            x, y, w, h = self._bounds 
    142180            rw, rh = w / 2., h / 2. 
    …… 
    188226        del self._items[:] 
    189227 
     228    def dump(self, indent=''): 
     229       print indent, self, self._bounds 
     230       indent += '  ' 
     231       for item, bounds in self._items: 
     232           print indent, item, bounds 
     233       for bucket in self._buckets or []: 
     234           bucket.dump(indent) 
     235 
    190236    def __contains__(self, bounds): 
    191237        """ 
    …… 
    198244def contains(inner, outer): 
    199245    """ 
    200     Returns True if recta is contained inside rectb. 
     246    Returns True if inner rect is contained in outer rect. 
    201247    """ 
    202248    ix, iy, iw, ih = inner