Finding nearest available space without colliding with existing points

Question

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

Also given a different set of points (shown below) where the box cannot fit immediately next to point 4, I'm still hoping to find the closest space (as shown). I'm judging "closest" by the distance between point 4 and centre of the red box.

Any help or thoughts would be much appreciated.

Answer 1

The key for solving this problem is considering that every point divides the space in four (overlapping) semiplanes: north, south, west or east.

Start by considering the reference point, the rectangle must be at its north or at its south or etc. or in other words, in one of the semiplanes defined above.

Instead of semiplanes, lets think on them as axis-aligned rectangles which may have some side in the infinite.

Now for every one of these bounding rectangles, try to place the target rectangle inside, at the nearest position to the reference point. If it collides with any point, divide the bounding rectangle at that point in four new bounding rectangles and repeat.

So, in summary:

1) keep a queue of bounding rectangles ordered by their distance to the reference point.

2) get the first element, see if you can fit the rectangle there, at the nearest position to the reference point. If you can, the problem is solved.

3) otherwise, divide the bounding rectangle at any of the colliding points and push the resulting four bounding rectangles into the queue (filtering out those too small).

4) repeat.