Finding the closest available space without colliding with existing points

Question

Given a set of points, I'm looking for ideas on how to efficiently find the closest available space of a given width and height (represented by a red field) to a specified point (point 4 in this example).

Another set of points is also given (shown below), where the box cannot immediately fit next to point 4, I still hope to find the closest place (as shown). I judge "closer" to the distance between point 4 and the center of the red square.

Any help or thoughts would be greatly appreciated.

Answer 1

The key to solving this problem is to consider that each point divides the space into four (overlapping) half-planes: north, south, west, or east.

Let's start by looking at the control point, the rectangle should be in its north or south, etc. or, in other words, in one of the half-planes defined above.

Instead of half-planes, let's consider them as rectangles aligned on the axis, which may have some side at infinity.

Now for each of these bounding rectangles, try placing the target rectangle inside, at the closest position of the anchor point. If it collides with any point, divide the bounding box at that point in the four new bounding boxes and repeat.

So in short:

1) save the queue of bounding rectangles ordered by their distance to the control point.

2) get the first element, see if you can place the rectangle there, in the closest position of the anchor point. If possible, the problem will be resolved.

3) otherwise, divide the bounding rectangle into any of the colliding points and push the resulting four bounding rectangles into the queue (filter them too little).

4) repeat.