Способы размещения и сколько граммов вешать

Давно задачка у меня.

Керамическая плитка - криволинейная призма произвольной формы (ПРОИЗВОЛЬНОЙ - значит любой), но такой, что её края могут сопрягаться при укладке (на подобие паркета).

Есть комната тоже произвольной формы в плане.

Необходимо найти способ как уложить плитку на пол как можно более экономично и сказать сколько плитки потребуется.

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

У решеток есть направления -- ето множества прямых, проходящих через соседние вершины.

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

Сообщение отредактировано: Visitor - 28.10.03, 17:48

Есть идея.
Сначала устроить перебор с двумя фигурами на тему как лучше сопрягаются края.

|\<br>\/<br>|-<br>--<br>||<br>/|<br>/-<br>\-

L₁=Длина сопряжения краёв двух фигур
L₀=Длина мест, где края не сопряжены.

L_s=L₁/L₀

Критерий оценки пригодности - L_s. Но стоит учитывать и площадь, занимаемую обеими фигурами и количество разрывов.

Предолагаю, существует зависимость между отношением L_s и отношением занятой площади к незанятой внутри косоугольной трапеции, описывающей обе фигуры.

Есть продолжение мысли?

Хм...?

Края, для получения мозаики без дыр, сопрягаются единственным образом. Если все плитки одинаковые, значит они либо единственным образом сопрягаются, либо обладают симметрией, и преобразуются сами в себя поворотом на (некоторые) n*Pi/6, в плоскости на которой они лежат...

Т.е., все плитки, в данных задачи можно считать уже правильно сопряженными и образующими бесконечную во все стороны решетку...

Или плитки НЕ одинаковые? Тогда никаких решеток и типичная задача о рюкзаке...

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

Форма не важна, все равно у каждой плитки будет по три, четыре или шесть вершин, в которых сходятся соотв, 6, 4 или 3 плитки, и вершины ети будут расположены в узлах регулярной решетки (все ячейки одинаковые )... Произвольная форма получается произвольным искривлением граней и сдвигами узлов||->//...

--

А... понял. То, что у тебя "способ укладки", у меня "поворот и перемещение комнаты на бесконечной решетке из плиток".

Сообщение отредактировано: Visitor - 29.10.03, 09:06

Есть след. идея:

в середине у нас никаких обрезков не будет => обрезки будут скраю.

отсюда мысля

чем окуратней к 1 краю мы прилепим плитки, тем меньше обрезков получим.

развиваем

чем окураней к углу прилепим, для не перпендикуряных ребро_плитки-стена учитывать придется по всей длине стены, тем меньше обрезков получим.

надо будет вычислить кол-во обрезков при прилепления к каждому углу, и выбрать размещение с мин. кол. обрезков, тобишь угол от которого класть плитку.

Да. Мысль хорошая была.
Найти способ укладки и сделать "фон" из сетки и планом комнаты выбирать лучший вариант.

Но способ укладки может варьироваться для оптимального подгона к краям комнаты.

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

Сообщение отредактировано: Tishaishii - 29.10.03, 15:58

Была б еще стена В общей задаче прямых стен нет и грани у плиток тоже проблематичны:



Прямоугольная решетка

Сообщение отредактировано: Visitor - 29.10.03, 16:05

помоему как музыканты ни садитесь, всё равно площадь будет одна и та же, так что сэкономить не удастся ;D

Площадь-то да Штук плитки надо как можно меньше испортить

про квадратуру круга слышал ?

в нашей задаче достаточно, при округлых стенах, чтобы плитка вписалась

Кстати, я тут погорячился

Регулярных решеток не будет.
В общем случае, будут только "регулярные" параллельные полосы, произвольно сдвинутые друг относительно друга. Задача усложняется

появилась еще идея, после усложнения о всячески неровных стенах:

описАть форму, пропорциональную плитке, вокруг комнаты, так чтобы разница в площадях была минимальна, это даст нам направление швов.
это как минимум, а может и вообще идеальное расположение ?
Хотя для идеального расположения надо еще степени свободы комнаты внутри нашей формы расчитывать ?, но это уже сдвиги по осям X, Y.

1. Решетка, все-таки не регулярна и пропорциональностью _просто_ воспользоваться не удастся...

2. Даже в регулярной решетке: представь себе квадратную решетку 1х1, у которой все вертикальные отрезки вытянуты параболой на 10 влево. Описать-то вокруг комнаты пропорциональную фигуру можно...