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

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

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

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

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

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

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

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

Сообщение отредактировано: 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 влево. Описать-то вокруг комнаты пропорциональную фигуру можно...

ну так давайте разберемся какие условия ??
1. все плитки одинаковые ?
2. можно выложить из плиток пласт - с линией симметрии ?

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

3. Решетка не регулярная по этому ?
4. Если мы предположим следущее, есть закаулок такой формы, что его замостить оптимально поворотом плитки, поворачивать плитку или нарезать плиток относительно пласта ?
5. Могут ли в комнате быть столбы  ;D ?

[center]

Комната для тех, кто сомневается
[/center]

Сообщение отредактировано: Tishaishii - 30.10.03, 13:41

Подпись к рисунку: "Жилище сомневающегося. С. Дали. Масло, холст."

пришли еще какой плиткой ее замостить!
и тогда подумаем  ;)

Блин.. я туплю. Решетка таки регулярная.

Если не:
1. берем плиток N, так, чтобы N*S(плитки) >= S(комнаты).

2. Укладываем плитки, пока помещаются целые. В дырки укладываем куски плиток, вырезанные из оставшихся.

3. В пределе, при S(обрезков) -> 0, S(уложенной плитки) -> S(комнаты)

4. Но все уложенные плитки находятся внутри комнаты. Следовательно комната вымощена.

Ответ: N

Сообщение отредактировано: Visitor - 30.10.03, 14:11

дык, никто не сомневался что N 8D

а интересно, как задаётся такая замечательная комната? неужели с помощью многоугольников? и вобще для чего всё ето надо?

Действительно, N подходит лучше всего.

---

Применяется в планировании интерьеров и для расчётов сколько плитки потребуется и кто где придумает. Но хотелось свести к математической задаче и попытаться решить в общем виде. ???

Сообщение отредактировано: Tishaishii - 30.10.03, 14:36

Вы меня запутали... Нужен ответ N, или, чтобы плитка на полу красиво лежала?

Извини, если запутал.
Но ответ N подходит практически к любой задаче на счёт и он малоинформативен.
Следовательно вопрос открыт.

Так етот ответ, при отсутствии дополнительного ограничения и является правильным:

В самом деле, меньше N плиток мы взять не можем.
А больше N нам не понадобится, т.к, мы разрежем несколько последних, чтобы покрыть весь пол.

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

Значит нужно еще ограничение. Например, минимальное число разрезаний. Но тогда, задача может не иметь решения.

Можно ли ответить покупателю, что при имеющейся данной КОНКРЕТНОЙ форме плитки и форме пола для оптимальной укладки понадобится ровно N плиток?

Как зависит N от формы плитки и пола, их размера и способа укладки?

Сообщение отредактировано: Tishaishii - 30.10.03, 17:05

а что стоит на кону? всёравно ведь 2*N плиток не потребуется, а чертить на плитке линию разреза имхо проще в натуре, нежели мучаться с перегоном в компьютер, оптимизацией и выводом из компьютера. да и результат я думаю не будет сильно различаться. к тому же наши дома строятся таким образом, что точно измерить какой-либо параметр не представляется возможным, и полы кривые, так что если ты всё рассчитаешь с точностью до десятой доли миллиметра, у тебя обязательно будет несостыковка и тебе придётся всё переделывать. я сам летом занимался поклейкой потолочной плитки и на собственной шкуре в етом убедился, даже несмотря на то, что плитка у меня была прямоугольная. так что вряд ли получится сэкономить заметную долю плитки. как раньше писали в советских газетах, в масштабах всей страны экономический эффект от нововведения составит 10000 рублей в год ;D

Сообщение отредактировано: wormball - 30.10.03, 18:04

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

Подводим итоги.
Видимо, задачка действительно стоящая.
А ход всторону - тоже вариант, но не решение задачи.

Всем, кто решал, спасибо.