Эффективный алгоритм упаковки неправильных многоугольников

Я не знаю, даст ли это оптимальный ответ, но, по крайней мере, даст ответ:

1. Вычислите триангуляцию Делоне для заданного многоугольника. Для этого существуют стандартные алгоритмы, которые будут работать очень быстро для 100 вершин или менее (см., например, эту библиотеку здесь.) Использование триангуляции Делоне должно гарантировать, что у вас не будет слишком много длинных тонких треугольников.
2. Разделите любой непрямоугольный треугольник на два прямоугольных, опустив высоту от наибольшего угла к противоположной стороне.
3. Найдите треугольники, которые можно объединить в прямоугольники: любые два конгруэнтных прямоугольных треугольника (не зеркальные отражения), которые имеют общую гипотенузу. Я подозреваю, что в общем случае их не будет слишком много, если только у вашего неправильного многоугольника не было много прямых углов.

Я понимаю, что нужно заполнить много деталей, но я думаю, что начать с триангуляции Делоне, вероятно, будет правильным решением. Триангуляции Делоне на плоскости можно эффективно вычислить, и они обычно выглядят вполне «естественно».

ОТРЕДАКТИРОВАНО ДЛЯ ДОБАВЛЕНИЯ: поскольку мы находимся в специальной эвристической вилле, в дополнение к жадным алгоритмам, обсуждаемым в других ответах, вы также должны рассмотреть какую-то стратегию «разделяй и властвуй». Если фигура не выпуклая, как в вашем примере, разделите ее на выпуклые формы, многократно разрезая от вершины рефлекса к другой вершине таким образом, чтобы максимально приблизиться к разделению угла рефлекса пополам. После того, как вы разделили фигуру на выпуклые части, я бы подумал о следующем разделении выпуклых частей на части с хорошими «основаниями», части, по крайней мере, с одной стороной, имеющей два острых или прямых угла на концах. Если какой-либо кусок не имеет такой «основы», вы сможете разделить его на две части по диаметру куска и получить две новые части, каждая из которых имеет «основу» (я думаю). Это должно свести проблему к работе с выпуклыми многоугольниками, которые являются своего рода трапецеидальными, и с этого момента жадный алгоритм должен работать хорошо. Я думаю, что этот алгоритм будет разделять исходную форму довольно естественным образом, пока вы не доберетесь до своего рода трапециевидных частей.

Хотел бы я, чтобы у меня было время поиграть с этим, потому что это звучит как действительно забавная задача!

Моя первая мысль (посмотрев на вашу диаграмму выше) состояла в том, чтобы найти 2 смежных прямых угла, поворачивающихся в одном направлении. Я уверен, что это не будет охватывать каждый случай, когда поможет прямоугольник, но с точки зрения пользователя это очевидный случай (квадратные углы снаружи = это должен быть прямоугольник).

Как только вы нашли соседнюю пару прямых углов, возьмите длину более короткого катета, и у вас получится один прямоугольник. Вычтите это из многоугольника, оставшегося до плитки, и повторите. Когда больше нет очевидных внешних прямоугольников, которые нужно удалить, тогда сделайте свою обычную мозаичную вещь (ответ Питера звучит великолепно) на этом.

Отказ от ответственности: я не эксперт в этом, и я даже не пробовал...