I have a set of rectangles overlapping each other. I need to detect that overlaps exist in a set of rectangles. If overlaps exist, then I need to update the coordinates so the set of rectangles do not overlap anymore. I wonder if there are existing python libraries suited for this task.
This operation will be applied to million+ set of rectangles, so algorithm efficiency and leveraging GPU would be important as well.
The shapely interface to GEOS may be the library for which you are looking, but I have never used it for this purpose.
It may be easier to roll your own, in this case. The algorithm is a straightforward sweep-line algorithm, with an average complexity per rectangle proportional to log(N).
A) Each rectangle is characterized by four coordinates, Left, Right, Top, Bottom.
B) The rectangles will be processed in order of their Left coordinate
c) An Interval Tree is used to maintain the top-bottom ranges for each rectangle whose Left edge has been encountered and Right edge has not yet been encountered
D) A Priority Queue is maintained, ordered by Right edge, of all rectangles that are currently in the Interval Tree
1) Get the first or next rectangle to be processed. If no more are available, exit.
2) While any element on the Priority Queue has a priority less than or equal to the Left value of this rectangle, delete that element from the Priority Queue and the associated element from the Interval Tree.
3) Search the Interval Tree for overlap with the Top-Bottom range of this rectangle; process each overlap found.
4) Insert the Top-Bottom range of this rectangle into the Interval Tree, and add an element to the Priority Queue, with a priority set to the Right value from the rectangle, referring to the interval added to the Interval Tree.
5) Return to step 1) to get the next rectangle.