Programmatic analysis of geometric shapes

Question

I’m trying to work out a math / geometry problem in a Java project I’m working.

Here is the scenario:

There are two sets of blocks, each with a different number of blocks and different dimensions. In this example Set A has 5 blocks, each is 20x20 pixels; Set B has 6 blocks, and each is 25x50 pixels:

I’m trying to come up with a way to mathematically or logically determine how those sets would line up to maximize the contact between them. If you were to line these set up end-to-end it would look like this:

In this image, 4 of the blocks in set B are in contact with the blocks in set A. However, if you shift set A to the right a bit, you can get 5 of the blocks in set B to touch:

The problem is that the formula / algorithm / logic needs to be flexible enough to handle different combinations. In this example, set C has only 3 blocks, and each block is 40x40:

Any ideas?

Answer 1

Let a_total and b_total be the total widths of the collections of blocks. Let a_single and b_single be the width of one of the blocks. We can assume a_total <= b_total (otherwise swap).

If the rows of blocks are aligned at their left edges, A is in contact with ceiling(a_total/b_single) blocks from B. That number can be increased by at most one by shifting the starting point of A to the right. The number is at most one because the situation is periodic for large B (imagine an infinitely long B, for example): shifting A by exactly b_single results in a configuration exactly the same as the starting configuration, so another B block has been added to the end.

The trick now is to see whether we can add a B block to the end by shifting the A collection, while not removing the B block at the beginning.

We can add a B block at the end only if B is long enough; the exact condition is a_total <= b_total - b_single.

We can avoid removing a B block from the beginning if we can shift the A collection by less than b_single in order for the right edge of the A collection to pass a B block boundary, in other words if and only if ceiling(a_total/b_single)*b_single - a_total < b_single, i.e., ceiling(a_total/b_single) < (a_total + b_single)/b_single, i.e., ceiling(a_total/b_single) < a_total/b_single + 1. The latter inequality is always true.

In summary, the number of blocks in contact is maximized at ceiling(a_total/b_total) + 1 if a_total <= b_total - b_single, and ceiling(a_total/b_total) otherwise (assuming, of course, that a_total <= b_total).

There is one further issue you need to consider: the above analysis holds when you can adjust the relative positions of the blocks by any real number. If you are restricted to one pixel adjustments, then you may get into further special cases if b_single = 1, for example.

Answer 2

Check the difference in total length between the two sets of blocks.

• If the difference is less than the length of the smaller block, then just align the two sets of blocks on one edge; they all have contact with each other, so call it good.
• Otherwise, move the smaller set of blocks sideways by almost the length of one member of the other set (i.e., length of larger block minus some tiny number), to maximize contact.

It will look a bit like this (where top blocks are width 5, and bottom blocks are width 3):

111112222233333444445555566666
--->111222333444555

If you're aiming for the simpler answer of "how many blocks are in contact?", then the computation is simpler. The shorter set of blocks always has contact with the longer set of blocks. The longer set of blocks is in contact with this many blocks in the shorter set if the edges are exactly aligned:

(length of shorter set of blocks) / (length of a single member of longer block)

Add one if that's both less than the number of longer blocks, and if that fraction isn't an integer (to account for a tiny shift like I described earlier). Then round up.

Answer 3

Center the two sets of blocks and shift one of them by a small amount.

Answer 4

It's a little difficult to come up with a good algorithm for this without understanding what the program is actually trying to do ... but ok, you want to 'maximise' the contact between two lists of blocks (or are they really sets?).

One thing that occurs to me here is that the best alignment will have at least one of the separators between blocks aligned. So you could just keep the longer list fixed, and shift the shorter one along, stepping by separator alignment.