class QuadTree():
    def __init__(self,items,bounding_rect=None):
        self.nw = self.ne = self.se = self.sw = None
        if bounding_rect:
            l, t, r, b = bounding_rect
        else:
            l = self.l = min(item.x for item in items)
            t = self.t = min(item.y for item in items)
            r = self.r = max(item.x for item in items)
            b = self.b = max(item.y for item in items)
        cx = self.cx = (l + r) * 0.5
        cy = self.cy = (t + b) * 0.5
        self.h = b-t
        self.w = r-l
        nw_items = []
        ne_items = []
        se_items = []
        sw_items = []
        if len(items)<200:
            self.items=items
        else:
            self.items=[]
            for item in items:
                if item.x <= cx and item.y <= cy: nw_items.append(item)
                elif item.x >= cx and item.y <= cy: ne_items.append(item)
                elif item.x >= cx and item.y >= cy: se_items.append(item)
                elif item.x <= cx and item.y >= cy: sw_items.append(item)
                else : print "somethig went wrong"
            if nw_items:
                self.nw = QuadTree(nw_items, (l, t, cx, cy))
            if ne_items:
                self.ne = QuadTree(ne_items, (cx, t, r, cy))
            if se_items:
                self.se = QuadTree(se_items, (cx, cy, r, b))
            if sw_items:
                self.sw = QuadTree(sw_items, (l, cy, cx, b))
    def hit(self, rect):
        cx=self.cx
        cy=self.cy
        l=rect[0]
        r=rect[2]
        t=rect[1]
        b=rect[3]
        if not((abs(cx-(l+r)*0.5) < (self.w+r-l)*0.5) and (abs(cy-(t+b)*0.5) < (self.h+b-t)*0.5)):
            return []
        def overlaps(item):
            return r >= item.x and l <= item.x and b >= item.y and t <= item.y
        hits = list(item for item in self.items if overlaps(item))
        if (self.nw is not None) and l <= cx and t <= cy:
            hits.extend(self.nw.hit(rect))
        if (self.sw is not None) and l <= cx and b >= cy:
            hits.extend(self.sw.hit(rect))
        if (self.ne is not None) and r >= cx and t <= cy:
            hits.extend(self.ne.hit(rect))
        if (self.se is not None) and r >= cx and b >= cy:
            hits.extend(self.se.hit(rect))
        return hits
if __name__=="__main__":
    import random
    class item():
        def __init__(self,x,y):
            self.x=x
            self.y=y
    myL = [item(1000*random.random(),1000*random.random()) for i in xrange(10000)]
    qt=QuadTree(myL)
    print len(qt.hit((0.0,0.0,1000.0,1000.0)))
