В дальнейшем я собираюсь предположить, что все углы на входном многоугольнике являются прямыми углами.
Сначала меня смутили ваши цифры, поскольку прямоугольники имеют разную площадь, и решить эту проблему очень просто, просто измените алгоритм вырезания ушей, чтобы работать с квадратами вместо треугольников (он работает из-за прямых углов) , Если им просто нужно иметь одинаковую область, вам просто нужно разделить каждый полученный прямоугольник на меньшие прямоугольники с размером наибольшего общего делителя для области всех прямоугольников, которые вы нашли до сих пор. Затем мне остается решить проблему для предварительно выбранного значения для области.
Существует несколько реализаций природы решения, которые мы можем использовать для решения этой проблемы (при условии, что данный экземпляр решаем).
Первая реализация состоит в том, что полигон должен иметь свою площадь, делимую на конкретную область, и любое подразделение полигона также должно удовлетворять этому.
Вторая реализация состоит в том, что тривиально поделить прямоугольник, область которого делится на определенную область, на более мелкие прямоугольники правильного размера, просто разделив его на правильное количество срезов вдоль одного из направлений.
Третье понимание состоит в том, что нам нужно уменьшить сложность многоугольника, пока у нас не останется только прямоугольники. В частности, должен существовать набор подразделений, каждое из которых имеет несколько кратных правильной площади и каждое из которых образует прямоугольник.
Четвертая реализация заключается в том, что (один набор) подразделов из третьей реализации должен иметь свои внутренние границы, являющиеся продолжением внутренних вогнутых углов многоугольника, с которого мы начали. Может быть немного сложно понять, почему это так, но если у нас нет такого расширения, то на одной стороне такого подразделения нам нужно выйти за пределы линии, и полученная форма не уменьшит ее сложность. независимо от того, сколько раз мы продолжали бы делить, мы будем постоянно вынуждены вторгаться в другой прямоугольник с некоторой областью, что означает, что у прямоугольника также будет повышенная сложность, и поэтому мы никогда не сможем удалить сложность.
Другими словами, один из способов найти подходящее деление многоугольника на прямоугольники определенной области - это сначала найти подразделения многоугольника вдоль линий, вытянутых вогнутыми углами (где площадь каждой стороны кратна определенной области), пока все подразделения не превращаются в прямоугольники. Если это не удается, то подходящего подразделения не существует. В случае успеха все, что осталось, - это поделить эти прямоугольники, как упоминалось ранее.
Следует отметить, что могут существовать подразделения на такие прямоугольники, которые не соответствуют подразделам, описанным в реализации 3 и 4, но они все еще существуют, только если такое подходящее деление может быть сделано, поскольку они фактически являются просто перестановками прямоугольники, которые пересекают эти подразделения.