[Python] Efficiently Finding Nearest Non-Colliding Position for a Rectangle in 2D Space?

I’ve been struggling with a problem related to collision detection and positioning in a 2D space, and I could really use some guidance on achieving good performance.

I have a rectangular boundary (blue). Within this space, there is a list of collidable geometries, including contour lines and other rectangles (marked in red). Additionally, I have other rectangles (marked in green) that must not collide with the red ones.

When a green rectangle collides with a red rectangle, I need to determine the nearest valid positions for the green rectangle that ensures it does not overlap with any of the red rectangles and lines.

EDITED: The green rectangles do not always have the same size. There can be up to 24 green rectangles, while the number of red lines and polygons can exceed 40 or more. The green rectangles are allowed to overlap with each other. Unfortunately, I need to use Python, and I require the performance to ensure that a green rectangle can find its new position in less than half a second.



I initially tried using a brute-force method to find the nearest non-colliding positions for the rectangles. However, this approach may lead to performance issues when dealing with a large number of collisions.

Expected Ouput:



The expected output should provide the nearest valid center positions for the green rectangle, categorized by movement along different axes:

• Only X-axis: (14.5, 7.5)
• Only Y-axis: [(5.5, 14.5)]
• Both axes: (4.5, 8.5)

Continue reading...