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.

Background: There is an Web API that allows "configurations" to be added to a queue. Each configuration consists of 2-3 "plates." The process of creating a single configuration should not take several minutes. Essentially, each plate represents a wooden base (with defined bounds) that includes cutouts (in red) and clamping points (in green).

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)

I wrote out some code that would guarantee the solution is the smallest displacement of the green rectangle. It would still require some adjusting to apply to your specific problem.

I am assuming you have two functions available: a function to calculate the distance between two points: calculateDist(), and a function to detect collisions with red squares: detectCollisions(). The rect.width and rect.height get the width and height of the green rectangle that needs to move. The collission._border gets the x or y coordinate for that border of the red rectangle.

I don't guarantee it is the most efficient algorithm, but it will be more efficient then brute forcing it.

# fill with original position of rect
originalPosition = (x, y)
# keeps track of positions which are already known so there is no duplicate code
positionsSearched = set()
# sorted list with the position that has the shortest distance to the original rect as the closest
positionsToSearch = [(0, originalPosition, detectCollisions(originalPosition))] # struct = (distance_to_original, position, collisions)[]
# add the original position to the set of already searched
positionsSearched.add(originalPosition)

# loop as long as there are positions to search and the closest searched position still has collisions
while len(positionsToSearch) > 0 and len(positionsToSearch[0][2]) > 0:
    # get and remove first element of sorted list, this is the position closest to the original position due to the sort
    distance, position, collisions = positionsToSearch.pop(0)
    
    # look at all collisions so that later the collision with the shortest solution can be tested first
    for collision in collisions:
        # add the four possible positions to move to to the stack (top of rect, bottom of rect, right of rect, left of rect)
        # the rect.height and rect.width are those of the original rect you are trying to move
        possibleSolutions = [
            (collision.topBorder - rect.height, position[1]),
            (collision.bottomBorder, position[1]),
            (position[0], collision.rightBorder),
            (position[0], collision.leftBorder - rect.width)
        ]

        for possibleSolution in possibleSolutions:
            # if the possible solution was not already added to the positions to search, add it to the positions to search
            if possibleSolution not in positionsSearched and notOutOfBounds(possibleSolution):
                positionsToSearch.append((calculateDist(possibleSolution, originalPosition), possibleSolution, detectCollisions(possibleSolution)))

    # sort on the distance to the original position, this way the closest are evaluated first
    positionsToSearch.sort(key=lambda x: x[0])

# check if the positions to search are 0
if(len(positionsToSearch) == 0):
    return ERROR # this means no valid positions were found to move to

valid_closest_position = positionsToSearch[0][1] # if a valid position is found it will be in front of the list