Как я могу заполнить контур предопределенными формами танграмм?

Question

Меня интересует использование таких форм:

Обычно танграмма состоит из 7 фигур (5 треугольников, 1 квадрат и 1 параллелограмм).

То, что я хочу сделать, - это заполнить фигуру только фигурами танграма, поэтому на данном этапе размер и повторение фигур не должны иметь значения.

Вот что я попробовал вручную:

Я немного растерялся, как подойти к этому.

Предполагая, что у меня есть путь (упорядоченный список / массив точек контура), я полагаю, что мне следует попытаться выполнить какую-то триангуляцию.

Существует ли такая вещь, как триангуляция Деуланая с треугольниками, ограниченными 45-градусными прямоугольными треугольниками?

Более "грубый" подход - добавить группу треугольников (45 градусов) и использовать SAT для обнаружения столкновений, чтобы «исправить» перекрытия, и, надеюсь, пробелы будут исключены.

Поскольку квадрат и параллелограмм также могут быть сделаны из треугольников (45 градусов), я думаю,хорошее чистое геометрическое решение, верно?

Как мне упаковать треугольники (45 градусов) в произвольную форму?

Любые идеи приветствуются.

Answer 1

Несколько случайных мыслей (возможно, они помогут вам найти лучшее решение), если вы используете только оригинальные размеры фигур:

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

• Любая триангуляция неполигонов (например, полумесяц в вашем примере), вероятно, делаетне очень хорошо работает ...

• Похоже, вы требуете, чтобы формы могли иметь только несколько отдельных ориентаций.Чтобы найти наилучшее соответствие этих треугольников в заданной форме, я бы предложил следующее приблизительное решение: нарисуйте сетку треугольников (то есть квадратную сетку с диагональными линиями) поперек фигуры и возьмите те треугольники, которые полностью содержатся.Это, скорее всего, не даст вам оптимального покрытия, но тогда вы могли бы многократно смещать сетку на одну десятую размера сетки в горизонтальном и вертикальном направлении и посмотреть, найдете ли вы что-то, что покрывает большую долю исходной формы (или выможет идти с шагом 1/2, затем 1/4 и т. д. исходного размера сетки в духе бинарного поиска).

Если вы разрешите произвольное масштабирование фигур, которые выможет приблизить любую (достаточно гладкую?) форму к произвольной точности, добавляя все меньшие и меньшие фигуры.Например, если у вас есть растровое изображение, вы можете, например, выбрать размер желтого треугольника, чтобы два из них составляли пиксель на изображении, а затем вы можете представить любое такое растровое изображение.