Given a set of rectangles contained within a larger rectangle such that none overlap, what is the most efficient way to determine the position of a new rectangle such that it is as close as possible to a given reference point while still not overlapping any existing rectangle?

For example, in the following diagram:


the two red rectangles are positioned within the larger, black rectangle, and a third, green rectangle is to be added. The proper position of that green rectangle is shown given three example reference points, denoted by small, blue squares. You'll see that the proper position of the green rectangle always corresponds to the shortest possible distance to its reference point, illustrated by blue lines.

Edit: I should add that the reference point will always lie on the edge of the bounding rectangle.

  • $\begingroup$ How are you defining the closeness of the newly-placed box? The nearest point on that box to the reference point? For example, on the bottom-right of your picture your ray would actually be shorter if it were measuring distance, and would go to the bottom-right corner of the green box. $\endgroup$ – Loki Clock Jun 16 '13 at 10:40
  • $\begingroup$ Though I suppose you would want to alter that notion when the box could partially or fully overlap the reference point. $\endgroup$ – Loki Clock Jun 16 '13 at 11:39
  • $\begingroup$ the closeness is defined by the distance between the reference point and any constant point on the box. so in the example i've used the top left corner, but you could use the center, as long as you're consistent $\endgroup$ – Madison Brown Jun 16 '13 at 17:14
  • $\begingroup$ So, the nearest point on the (filled) box. $\endgroup$ – Loki Clock Jun 17 '13 at 2:53
  • $\begingroup$ on second thought, it would probably be best to use the center of the box-to-be-placed to calculate distance to the reference. $\endgroup$ – Madison Brown Jun 17 '13 at 7:39

I've decided this is way too complicated to ask someone to do for you. Here are my thoughts:

Let $T$ be the rectangle to place.

  1. Consider the outer dilation of each rectangle already placed by $2*T$ (double both dimensions - see Wikipedia picture), and the inner dilation of the bounding rectangle. If the point of reference is not in the union of these dilations, there must be no box near enough to it to stop you placing the box directly on it.
  2. Consider that the whitespace of a rectangle - the dilation minus the rectangle - has the same width or the same height as $T$ in any region. This implies that if one box enters the whitespace of another, both boxes are in eachother's whitespace.
  3. Notice this can be associated with a specific Region of Anger. If Box A is above Box B, projecting each box's vertical sides onto the other's horizontal sides will yield two or four of the corners of this Region of Anger. See: collision detection using Separating Axis Theorem.
  4. Notice the whitespace of the Region of Anger is within the union of Box A and Box B's whitespace. So, the collision regions for rectangles is stable. However, the Total Region of Anger is not - consider placing a box a little to the bottom-right of the two red boxes, and removing the two Regions of Anger it would create for $T$. It would not remove the corner region. Thus, if one removes Regions of Anger pairwise, one does not need to add it as a new box and redo the whole calculation, but rather to, upon detecting whitespace infringement, add all infringers (one one side of the same box) to a list, and then add each Region of Anger obtained pairwise to the list of infringers until no new boxes are added
  5. If there are no infringers on some box's whitespace, of course that box can simply be removed from the union of the dilations. The analogous thing when there are some whitespace infringers is to take the union over all the boxes in infringement lists on all sides as well as all boxes with no infringers, and remove THAT from the union of dilations. This I reckon will leave only whitespace some $T$ can sit in at all, reducing the problem to calculating the nearest point in this region to the reference point.
  • $\begingroup$ this definitely gets me going in the right direction, thanks! $\endgroup$ – Madison Brown Jun 17 '13 at 7:40
  • $\begingroup$ Sure thing! Have to say though, this is purely heuristic, and when I do heuristic things like collision detection algorithms I often get it wrong. $\endgroup$ – Loki Clock Jun 18 '13 at 8:17
  • $\begingroup$ I have an addendum I've been meaning to make: You can also skeletonize the whitespace put out by this process. By reducing every region of whitespace to the inner region at least half the width of $T$ from the horizontal edges and the same vertically, you obtain the set of points where the center of $T$ can be placed without overlap. It will avoid branching when defining the nearest point, the other pts on $T$ are detemined by it, it might only be made of lines, and if the target isn't in a solid region's interior, only the boundary of the region will be extremely close. $\endgroup$ – Loki Clock Jun 21 '13 at 16:55

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.