Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.


Sorting rectangle groups by intersections

  • Aharon Levine
    Aharon Levine


    I have a list of about 50000 rectangles that I need to sort into sub groups in the following fashion:

    1) I count how many other rectangles each one intersects.
    2) I build groups from any rectangle which intersects more than 20 other ones (with all the ones he intersects.

    Now I think if I use RTree for this with the interscts function then I can do this in O(nlog(n)) by loading all the rects into an RTree and then then testing each rect separately against this RTree.

    However I wonder: Is it possible to simply build the tree and then get my groups from the different nodes of the tree directly (since the tree has already divided my rectangles into initial groups)?

    • Aled Morris
      Aled Morris


      Assuming that the intersects() query is O(log n), then the building of the groups can be done in O(n log(n)). Note that this assumes the rtree already exists.

      I'm not sure that it the intersects() query is as simple as O(log n). I'd be interested to know what it is, but not enough to work it out myself.

      Unfortunately, I don't think there's any way to get your groups directly from the rtree.