<s> from spatial import SpatialList <EOL> class QuadTree : <EOL> def __init__ ( self ) : <EOL> self . root = None <EOL> def append ( self , point ) : <EOL> if not self . root : <EOL> self . root = Treenode ( point ) <EOL> else : <EOL> self . root . append ( point ) <EOL> def search ( self , box ) : <EOL> pointList = SpatialList ( ) <EOL> self . root . search ( pointList , box ) <EOL> return pointList <EOL> class Treenode : <EOL> def __init__ ( self , point ) : <EOL> self . data = point <EOL> self . first = None <EOL> self . second = None <EOL> self . third = None <EOL> self . fourth = None <EOL> def quadrant ( self , point ) : <EOL> if self . data . y <= point . y : <EOL> if self . data . x <= point . x : <EOL> return <NUM_LIT:1> <EOL> else : <EOL> return <NUM_LIT:2> <EOL> else : <EOL> if self . data . x >= point . x : <EOL> return <NUM_LIT:3> <EOL> else : <EOL> return <NUM_LIT:4> <EOL> def getNext ( self , int ) : <EOL> if int == <NUM_LIT:1> : <EOL> return self . first <EOL> elif int == <NUM_LIT:2> : <EOL> return self . second <EOL> elif int == <NUM_LIT:3> : <EOL> return self . third <EOL> elif int == <NUM_LIT:4> : <EOL> return self . fourth <EOL> def setNext ( self , int , point ) : <EOL> if int == <NUM_LIT:1> : <EOL> self . first = Treenode ( point ) <EOL> elif int == <NUM_LIT:2> : <EOL> self . second = Treenode ( point ) <EOL> elif int == <NUM_LIT:3> : <EOL> self . third = Treenode ( point ) <EOL> elif int == <NUM_LIT:4> : <EOL> self . fourth = Treenode ( point ) <EOL> def append ( self , point ) : <EOL> quad = self . quadrant ( point ) <EOL> node = self . getNext ( quad ) <EOL> if not node : <EOL> self . setNext ( quad , point ) <EOL> else : <EOL> node . append ( point ) <EOL> def search ( self , pointList , box ) : <EOL> if box . contains ( self . data ) : <EOL> pointList . append ( self . data ) <EOL> for i in xrange ( <NUM_LIT:1> , <NUM_LIT:5> ) : <EOL> node = self . getNext ( i ) <EOL> if node : <EOL> node . search ( pointList , box ) <EOL> else : <EOL> num = [ ] <EOL> for vertex in box : <EOL> num . append ( self . quadrant ( vertex ) ) <EOL> indices = set ( num ) <EOL> for i in indices : <EOL> node = self . getNext ( i ) <EOL> if node : <EOL> node . search ( pointList , box ) </s>
