Часть 2. Оптимальное использование доступных кирпичей.
К этому моменту я уже сопоставил свою цветовую палитру исходного изображения с доступными цветами кирпичей LEGO, как описано в моем предыдущем посте, и теперь я хочу выйти за рамки простого цветового обмана и воплотить эту идею в физическую реальность.
Оптимальные расчеты кирпичей 💰
При рассмотрении возможности покупки кубиков LEGO для изготовления этих спрайтов оказывается, что это довольно дорого. Сами кирпичи в среднем составляют около 0,05 фунта стерлингов за штуку, поэтому стоимость изображения размером 64 x 64 пикселя составляет 204,80 фунта стерлингов, что является экстремальным показателем.
Тем не менее, есть экономия, которую нужно сделать. Если вы можете использовать меньше больших блоков для создания того же изображения, эффективная цена за пиксель может значительно снизиться, примерно до 0,01 фунта стерлингов за пиксель, что позволяет сэкономить довольно значительную сумму денег.
Это просто не Лего
В дополнение к проблеме необработанных затрат, это не совсем чувствуется как настоящий проект, если все сделано из кирпичиков 1x1. Это скучная вещь, которую мог бы выводить матричный принтер старого образца, и он не кажется таким уж креативным.
Как выяснилось, это именно то, что делает специализированный стенд в лондонском магазине LEGO, но я все еще думаю, что это отговорка, и я могу сделать лучше.
В поисках предыдущей работы.
Я ленивый программист. Я бы предпочел повторно использовать чужой код, чем тратить целую вечность, пытаясь понять его самостоятельно, и с этой целью я гуглил бесконечное множество фраз в поисках какой-то предварительной работы по оптимальному использованию кирпичиков LEGO в двухмерной плоскости. , только чтобы придумать абсолютно ничего.
Я прочитал несколько увлекательных статей о таких вещах, как "Приближенный алгоритм нахождения наибольшего прямоугольника внутри невыпуклого многоугольника" и чертовски много постов обо всем, от Bin Packing до Сжатие JPEG на StackOverflow и Википедии, но в конечном итоге я не смог найти ничего подходящего.
Похоже, что оптимальное размещение неограниченной комбинации фигур произвольного размера в контейнерах случайной формы не является достаточно высоким приоритетом для сообщества компьютерных наук, чтобы, к моему большому разочарованию, уже решить его эффективно.
Я собирался написать логику сам. 🤔
Пишу сам.
Изменить цвета изображения с помощью элементов холста JavaScript и HTML5 довольно просто — вы извлекаете данные изображения в виде массива и перебираете их, чтобы получить значения R, G, B, A для каждого пикселя, которые вы можете изменить. на лету. Достаточно просто, но ему не хватает понимания координат пикселей и понимания соседних пикселей.
Мое решение состояло в том, чтобы скопировать данные изображения в новую структуру данных, которая могла бы легко ссылаться на своих соседей, а затем для каждого пикселя выполнить итерацию по доступным кубикам LEGO — сначала найти ближайшее цветовое соответствие, а затем найти самый большой возможный кирпич, который мог бы прилегают к якорю в этой точке.
С учетом нескольких проходов результат вполне приемлемый.
Это не самое оптимальное решение, которое может быть технически возможно, но это лучше, чем вообще ничего не делать для оптимизации вывода.
Самый большой недостаток заключается в том, что он эффективно сканирует изображение сверху вниз, слева направо, пытаясь разместить блоки оптимальным образом. По логике вещей, для некоторых фигур могли бы быть лучшие отправные точки, те, которые в конечном итоге используют меньше кирпичей для завершения, но такой подход требует невероятного количества проходов для оптимизации, а это не то, что я даже хочу пробовать.
Ну и что дальше? Оказывается, есть еще одна проблема… ошибка в моей логике.
Вы можете увидеть код в действии здесь: https://www.pokeproject.co.uk/lego/
Оставайтесь с нами, часть 3!
