Просто на ум пришел простой подход: если два прямоугольника разделяют ребро [1], то вместе они образуют прямоугольник, который содержит оба - либо смежные прямоугольники [][ ], либо один содержит другой [[] ].
Таким образом, если список прямоугольников образует прямоугольник большего размера, то все, что вам нужно, это многократно перебирать прямоугольники и «объединять» их пары в один более крупный. Если за одну итерацию вы не можете объединить ни одного, то с этими частями невозможно создать прямоугольник большего размера, чем у вас уже есть; в противном случае вы будете продолжать объединять прямоугольники до тех пор, пока не останется один.
[1] Поделись, так как у них одинаковый край; для одного из них недостаточно иметь ребро, включенное в ребро другого.
эффективность
Поскольку эффективность, по-видимому, является проблемой, вы, вероятно, могли бы ускорить ее, создав два индекса прямоугольников, один с большим размером ребра, а другой с меньшим размером края.
Затем сравните ребра одинакового размера и, если они совпадают, объедините два прямоугольника, удалите их из индексов и добавьте новый прямоугольник в индексы.
Вероятно, вы можете ускорить его, не переходя к следующей итерации при объединении чего-либо, а переходя к концу индексов перед повторением. (Останавливается, когда одна итерация не объединяет или остался только один прямоугольник.)
Кроме того, края прямоугольника, полученные в результате объединения, всегда по результатам анализа равны или превышают края исходных прямоугольников.
Таким образом, если индексы упорядочены по возрастанию размера ребра, новый прямоугольник будет вставлен либо в ту же позицию, что и проверяемая, либо в позиции, которые еще предстоит проверить, поэтому каждое объединение не потребует дополнительного цикла итерации. (Поскольку новый прямоугольник, несомненно, не объединится ни с одним прямоугольником, ранее проверенным в этой итерации, поскольку его ребра больше, чем все отмеченные ребра.)
Для этого на каждом шаге определенной итерации вам нужно попытаться объединиться по следующему меньшему ребру из любого из индексов:
- Если вы находитесь в index1 = 3 и index2 = 6, вы проверяете index1 и повышаете этот индекс;
- Если следующее ребро в этом индексе равно 5, следующий шаг итерации будет в index1 = 5 и index2 = 6, поэтому он проверит index1 и улучшит этот индекс;
- Если следующее ребро в этом индексе равно 7, следующий шаг итерации будет в index1 = 7 и index2 = 6, поэтому он проверит index2 и улучшит этот индекс;
- Если следующее ребро в этом индексе равно 10, следующий шаг итерации будет в index1 = 7 и index2 = 10, поэтому он проверит index1 и улучшит этот индекс;
- и т.д.
примеры
[A ][B ]
[C ][D ]
A можно объединить с B, C с D, а затем AB с CD. Один слева, ABCD, таким образом, возможно.
[A ][B ]
[C ][D ]
A можно объединить с B, C с D, но AB нельзя объединить с CD. 2 слева, AB и CD, таким образом, невозможно.
[A ][B ]
[C ][D [E]]
A можно объединить с B, C с D, CD с E, CDE с AB. 1 слева, ABCDE, таким образом, возможно.
[A ][B ]
[C ][D ][E]
A можно объединить с B, C с D, CD с AB, но не E. 2 слева, ABCD и E, таким образом, это невозможно.
ловушка
Если прямоугольник содержится в другом, но не разделяет границу, такой подход не объединит их.
Способ решения этой проблемы заключается в том, что, когда каждый попадает на итерацию, которая ничего не объединяет, и до того, как сделать вывод, что объединить набор прямоугольников невозможно, получить прямоугольник с самым широким краем и отбросить из индексов все остальные которые содержатся в этом самом большом прямоугольнике.
Это все еще не касается двух ситуаций.
Сначала рассмотрим ситуацию, когда с этой картой:
A B C D
E F G H
у нас есть прямоугольники ACGE и BDFH. Эти прямоугольники не имеют общего края и не содержатся, но образуют прямоугольник большего размера.
Во-вторых, рассмотрим ситуацию, когда с этой картой:
A B C D
E F G H
I J K L
у нас есть прямоугольники ABIJ, CDHG и EHLI. Они не разделяют ребра, не содержатся внутри друг друга, и никакие два из них не могут быть объединены в один прямоугольник; но в целом прямоугольник.
С этими подводными камнями этот метод не завершен. Но его можно использовать, чтобы значительно снизить сложность задачи и уменьшить количество анализируемых прямоугольников.