Программный анализ геометрических фигур

Question

Я пытаюсь решить проблему математики/геометрии в проекте Java, над которым я работаю.

Вот сценарий:

Есть два набора блоков, каждый с разным количеством блоков и различных размеров. В этом примере Set A имеет 5 блоков, каждый - 20x20 пикселей; Набор B имеет 6 блоков, и каждый 25x50 пикселей:

Я пытаюсь придумать способ математически или логически определить, каким образом эти наборы будут выстраиваться, чтобы максимизировать контакт между ними. Если вы должны были выстраиваться эти настройки впритык это будет выглядеть следующим образом:

На этом изображении, 4 блоков в наборе B находятся в контакте с блоками в наборе А. Однако , если сдвиг множества а вправо немного, вы можете получить 5 блоков в наборе B трогать:

Проблема заключается в том, что формула/алгоритм/логика должна быть достаточно гибкой, чтобы обрабатывать различные комбинации. В этом примере, набор С имеет только 3 блоков, и каждый блок 40х40:

Любые идеи?

Answer 1

Это немного трудно придумать хороший алгоритм для этого, не понимая, что программа на самом деле пытается сделать ... но хорошо, вы хотите «максимизировать» контакт между двумя списками блоков (или они действительно находят?).

Одна вещь, которая возникает у меня здесь, заключается в том, что для наилучшего выравнивания будет по крайней мере один из разделителей между выровненными блоками. Таким образом, вы можете просто сохранить длинный список фиксированным и сдвинуть более короткое, пройдя по выравниванию разделителя.

Answer 2

Центр двух комплектов блоков и сдвиньте один из них на небольшое количество.

Answer 3

Проверьте разницу в общей длине между двумя наборами блоков.

• Если разница меньше длины меньшего блока, то просто выровняйте два набора блоков на одном ребре; все они имеют контакт друг с другом, поэтому назовите это хорошо.
• В противном случае переместите меньший набор блоков в сторону на почти длина одного члена другого набора (т. Е. Длина большего блока минус небольшое количество), чтобы максимально связаться.

Это будет выглядеть немного, как это (где верхние блоки шириной 5, а нижние блоки шириной 3):

111112222233333444445555566666 
--->111222333444555 

Если вы стремитесь к более простому ответу «, сколько блоков находятся в контакте? ", то вычисление проще. Более короткий набор блоков всегда имеет контакт с более длинным набором блоков.Больше набора блоков находится в контакте с этим много блоков в более коротком наборе, если ребра точно выровнены:

(длина короткого набора блоков)/(длина одного члена более блока)

Добавьте один, если это меньше, чем количество более длинных блоков, и если эта доля не является целым числом (для учета крошечного сдвига, как я описал ранее). Затем округлите.

Answer 4

Пусть a_total и b_total - общая ширина коллекций блоков. Пусть a_single и b_single - ширина одного из блоков. Мы можем считать a_total < = b_total (иначе swap).

Если строки блоков выровнены по их левым краям, то A находится в контакте с потолочными (a_total/b_single) блоками из B. Это число может быть увеличено не более чем одним путем смещения начальной точки A вправо , Число не более одного, поскольку ситуация является периодической для больших B (например, представить бесконечно длинный B): сдвиг A точно на b_single приводит к конфигурации, точно такой же, как и начальная конфигурация, поэтому добавлен еще один B-блок конец.

Трюк теперь заключается в том, можно ли добавить блок B в конец, сдвинув коллекцию A, не удаляя блок B в начале.

Мы можем добавить блок B в конце, только если B достаточно длинный; точное условие: a_total < = b_total - b_single.

Мы можем избежать удаления блока B с самого начала, если мы сможем сдвинуть коллекцию A на меньшее, чем b_single, чтобы правый край коллекции A прошел границу B-блока, другими словами, если и только если потолок (a_total/b_single) * b_single - a_total < b_single, то есть потолок (a_total/b_single) < (a_total + b_single)/b_single, то есть потолок (a_total/b_single) < a_total/b_single + 1. Последнее неравенство всегда верно ,

В целом, количество блоков в контакте максимизируется на потолке (a_total/b_total) + 1, если a_total < = b_total - b_single и потолок (a_total/b_total) в противном случае (при условии, конечно, что a_total < = b_total).

Существует еще одна проблема, которую вы должны учесть: приведенный выше анализ выполняется, когда вы можете отрегулировать относительные положения блоков на любое действительное число. Если вы ограничены настройками одного пикселя, вы можете перейти к дополнительным особым случаям, например, если b_single = 1.