3
\$\begingroup\$

Give a 2D space with a bunch of non-intersecting AABBs, and a point in this space (that may or may not be inside an AABB), how can I find the closest place where I can place a new AABB of a given size?

For example, given the space below and the point 'X', the correct position for a certain AABB is marked in green:

AABBs

One solution I have considered is to iterate every edge, and find the closest point on that edge where the shape doesn't intersect (if such a point exists). This could be achieved by placing the AABB at the closest point on the given edge, and then if it's intersecting with another shape, move it to the outside edge of that shape, along the given edge, repeating until it's no longer intersecting. This seems relatively expensive (though could probably be optimized by using some kind of spatial hashing), but might be the way to go.

I'm wondering if there are any obvious or not so obvious solutions I'm missing here.

\$\endgroup\$
  • \$\begingroup\$ Another thought is to partition the space into an AABB tree, so that the entire space is filled with AABBs that are either "empty" or "full". Then, find the closest empty AABB that has width and height greater or equal to my AABB's width and height, and place it at the closest point inside that AABB. I just considered this though so I need to figure out what kind of data structure would work best... \$\endgroup\$ – TomD May 16 '15 at 0:40
  • \$\begingroup\$ ^ In your list of "available AABBs", some will overlap, which is fine. In your picture, the best location is in a big open space, that space is also a member of a tall narrow rectangle that ends above it. \$\endgroup\$ – david van brink May 16 '15 at 18:20
2
\$\begingroup\$

I recently encountered a related problem to do with packing a texture atlas. The main difference for yours is that you prefer "closest to a target point" result. But I think the approach will work about the same...

All of the candidate locations for the new rectangle have the following property:

  • One of its corners will lie on one of the "implied grid points" of the existing collection of rectangles.

The implied grid points is the grid made from all present X-coordinates and all present Y-coordinates of existing rectangles, PLUS the size of the new rectangle centered on the target location.

enter image description here

So, you could test each of these implied grid points, starting with the ones closest to the x-mark, and each of the four positions that the new one might touch a corner to it, til one fits.

To test legality of each candidate, you can intersect with every other rectangle, or prune that down with spatial binning or quad tree or such. (Look up algorithms for collision resolution, they will go into more detail on optimizing this aspect.)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you, this is a good suggestion. I'm worried about the exponential growth of grid points as AABBs are added, but I'm going to try an approach along these lines and profile it. Thanks! \$\endgroup\$ – TomD May 17 '15 at 0:24
  • \$\begingroup\$ It's somewhat mitigated by keeping just two lists, x & y, and spiraling out by index. Hmm, though getting the one that's actually closest, not number-of-lines closest would be tricky. :-/ \$\endgroup\$ – david van brink May 17 '15 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.