Algorithm: Smallest container on torus

[Simon]

Hi,

what is a smart algorithm for this?

Input data: List L of rectangles. Rectangle is 4 ints: (x, y) of top-left corner, (xl, yl) the two lengths. Also input data is exactly one torus map M -- this is a large rectangle, it's larger than any single rectangle in L.

Wanted output: Rectangle O that surrounds all the listed rectangles. This rectangle should be as small as possible. It's allowed to move the rectangles in L by integer multiples of the length of M. The output rectangle O should account for O-minimizing optimal shifts of the rectangles in L. (To clarify after NaOH's question: I want to minimize the lengths of O. You may shift the rectangles of L as often as you wish to minimize the length of O.)

I know: You can separate this problem by dimension: Consider only x and x-length first, then y and y-length.

Existing algorithms: I have an algorithm to find the smallest container on a non-torus map -- when you're not allowed to move the rectangles in L by the length of M.

For example, if the rectangles are denoted as Rect(x, y, xl, yl), the non-torus algorithm computes the correct smallest container for the following list of three rectangles:

    [ Rect(3, 5, 10, 10), Rect(5, 5, 9, 9), Rect(1, 1, 1, 1) ]
    .reduce!smallestContainer == Rect(1, 1, 13, 14)

I also have an exptime algorithm for the torus-smallest container: For each rectangle in the input list, try whether to set its top-left point in the range [0, M.xl[ or into [M.xl, 2 * M.xl[ instead. With an input list of length n, we have 2ⁿ choices to try. For each choice, measure with the non-torus algorithm. Use the choice that minimizes the non-torus algorithm target value.

Can I do it in less than exptime?

-- Simon

[NaOH]

Interesting problem, thinking about it.

The output rectangle O should account for O-minimizing optimal shifts of the rectangles in L.

I'm not sure what this means. Are we minimizing the size of the rectangle or the number of shifts?

[NaOH]

How about something like: calculate the distances between each rectangle (edit) and the previous along rectangle (/edit) along a certain axis, then pick the largest of these gaps, shift everything to the left of the gap up by M, and apply the non-toroidal algorithm to the result?

Edit: a "gap" from a rectangle A to the previous rectangle B is A.x - B.x - B.xl, and the "previous rectangle B" is the rectangle with the largest (B.x+B.xl) value such that B.x < A.x

Edit2: and then special-case the rectangle with the least x coordinate.

And then do it again for y.

[Simon]

Are we minimizing the size of the rectangle or the number of shifts?

We're minimizing the lengths of the output rectangle. We may shift as often as necessary.

My idea right now for a linear runtime: Recursively fold the list with the following function.

Rect foldTwoRects(Rect a, Rect b)
{
    // induction hypothesis: a is the output rectangle of the already-folded part of the list.
    Have the rectangle b top-left point in the interval [0, M[.
    Measure the container of a and b here.
    Move b ahead by M.
    Measure the container of a and b here.
    Move b back to where it was, and back by M again.
    Measure the container of a and b here.
    Return the smallest container of the 3 measured containers.
}

How about something like: calculate the distances between each rectangle along a certain axis, then pick the largest of these gaps, shift everything to the left of the gap up by M, and apply the non-toroidal algorithm to the result?

I like this, will think about it. This sounds more like my first shower ideas earlier today. My impl in this post feels too brute-force-ish.

-- Simon

[Simon]

About gaps in one dimension: You care about the area that's not covered by any rectangle. This area is a collection of disjoint intervals, the gaps. You find the largest gap G, and herd the rectangles of L such that O spans the complement of G.

This sounds plausible. I have to track the list of gaps then, beginning with the full M, and hack the gaps apart according to the list of input rectangles.

Problem: When the rectangles leave no gaps whatsoever, where should we cut? This is an esoteric corner case in practice. I want to apply the algorithm to tile grouping, and grouping is best for small-scale cutting of few tiles. It's not designed to group map-spanning constructs. The recursive foldTwoRects seems to answer this case too, which is a nice-to-have.

-- Simon

[Simon]

Folding with foldTwoRects is not correct sometimes when the gap-finding stays correct.

Assume the following spread of 1x1 rectangles on a 10x1 torus map:

a a a a a b     b a
0 1 2 3 4 5 6 7 8 9

Using foldTwoRects, if we gather pieces starting with the a at 0, going towards the right from there, we get the correct smallest container: The smallest container is the complement of the big gap.

But if we use foldTwoRects and start with the two bs, the algorithm will select the big gap in the very first iteration. Then, we never let the big gap go. We will leave out a small gap. Not even sorting the pieces by location would have helped us.

-- Simon

[Nepster]

I will focus on the one-dimensional problem.

There you want to compute
   min_R1 max_R2 ((R2.x - R1.x) mod M.Width + R2.xl)
where both R1 and R2 range over all rectangles in the list L. (In this post mod will always return a non-negative result, even if the input was negative)
Explanation:

• ((R2.x - R1.x) mod M.Width + R2.xl): Computes the size of the smallest rectangle with left border starting at the border of R1 and containing R2
• max_R2 [...]: Computes the size of the smallest rectangle with left border starting at the border of R1 and containing all rectangles in L
• min_R1 [...]: We choose that "start" rectangle R1 in L, for which the resulting rectangle O has minimal size.

(The actual position of the final rectangle O can be obtained from R1 and R2).

This gives an obvious algorithm of O(N^2), by computing the innermost expression for all R1, R2 and then finding the min-max for these values.

But we can do even better using the following algorithm:

• Sort L according to the x-value or the rectangles to get SortedL:
  We assert from now on that the x-values lie in the interval [0, M.Width[. This step is O(N log N).
• Remove all rectangles that can be covered totally by another rectangle:
  This can now be done in O(2N) as follows. Loop twice through your sorted list. For every index i, check if the the right border of the rectangle with index i-1 is to the right of the border of the current tile. If YES, then remove the current element with index i from the list. For all indices i > 0, we can essentially ignore the torus topology for this step (because we just ordered our list!). For i = 0 we have to shift the rectangle SortedL[-1] by -M.Width first.
  The result of this step is a new list SortedShortL of rectangles, where not only the x-coordinate is sorted increasingly, but as well R.x+R.xl, i.e. the coordinate of the right edge.
  Two more comments on this step: Looping twice through the list is necessary! Assume there is a huge rectangle almost at the very end of the list, that covers all other rectangles. Than the other rectangles get only removed after passing this huge rectangle for the first time, i.e. they will only get removed during the second loop.
  Secondly all removed rectangles are irrelevant for finding the correct result: We have to cover the bigger rectangle, so we automatically cover the smaller rectangle as well.
  
• For a R1 in SortedShortL compute max_R2 ((R2.x - R1.x) mod M.Width + R2.xl) in O(1):
  By having such a nicely ordered list, we can tell at once, which R2 gives the maximal value: The one coming directly before R1 in SortedShortL!
  
• Find O now as above:
  Because we can compute the max_R2 [...] now in O(1), this task can be achieved in O(N).
  

In total this algo runs as O(N log N) with a few additional O(N) parts.

PS: I don't think I ever make use of the fact, that rectangles have width at most M.Width.
PPS: Is this assumption even true for tiles that are already groups themselves?

[Simon]

Thanks! This is an excellent view of the problem. I have implemented the O(n²)-version in my code here. It's short, well-documented, and unittested.

I want to draw GUI buttons for the grouping, then push everything to github these days.

I've understood how to generate SortedShortL and why it is good. I'm not using the improved algorithm yet. When grouping 10 to 20 tiles at most, tile allocation is responsible for most of the runtime, not the O(n²) algo. If people generate larger groups, I'll refine the algorithm.

Tiles must be shorter than M: It's perfect to not rely on this. Yes, it may be false on small maps with huge groups.

-- Simon

[ccexplore]

Problem: When the rectangles leave no gaps whatsoever, where should we cut? This is an esoteric corner case in practice. I want to apply the algorithm to tile grouping, and grouping is best for small-scale cutting of few tiles. It's not designed to group map-spanning constructs.

Do agree it probably won't happen often in practice.  That said, you may still want to determine how much the output of such a corner case may confuse Lix and in turn, whether the user may need to be warned or outright disallowed about such constructs.

For example, it would seem that in that case, the algorithm will probably end up producing a rectangle larger than M (in the dimension(s) that have no gaps).  If you allow the grouping, that means you either have a group whose bounding rectangle exceeds the map's size, or you force the group's bounding rectangle to match the map size at which point it is no longer a traditional bounding rectangle (ie. the boundary will cut into one or more rectangles of the constituent tiles).

[Simon]

The game allows tiles larger than the map.

Nepster's algo may produce groups larger than the map, and that's fine. Groups shouldn't depend on the map. We use the map in the algorithm because the editor is handy to specify groups, and the editor works on maps.

On a torus map, when a gigantic tile gets to draw to the same pixel multiple times due to wrapping, I don't specify what color should end up there.

Only concerning gigangic tiles, too: Earth, air or steel will be correctly set if (the tile has air or earth, no steel) or (the tile has air or steel, no earth). Groups may have both steel and earth, hm. Maybe there's a bug here where stuff looks different than what its physics is, maybe not. Let's keep it in the back of our mind.

-- Simon