Оптимальный алгоритм штриховки прямоугольника

Question

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

Например, при заданном прямоугольнике 5x3 см, и я штрихую, используя параллельные линии шириной 1 см, самый большой объект, который я могу пройти через люк, - это квадрат со стороной 1 см. Я использовал всего 22 см (то есть 4x3 + 2x5) штриховок. Таким образом, чтобы пройти площадь 1 кв. М, я использовал 22 см линий штриховки.

Алгоритм должен найти шаблон, который минимизирует общие линии штриховки от текущих 22 см, не позволяя пройти области с более чем 1 кв. См (объект не обязательно должен быть в форме квадрата или даже прямоугольника, это общая площадь, которая вопросы).

Редактировать: Следуя примеру nlucaroni, я нашел Сотовую гипотезу , в которой говорится, что любое разбиение плоскости на области равной площади имеет периметр, по крайней мере, такой же, как у регулярной шестиугольной сетки , что частично отвечает на мой вопрос.

Answer 1

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

Посмотрите на тесселяции и выясните, должен ли ваш шаблон / экран / штриховка быть регулярным или нет, должен соответствовать тестируемому объекту и так далее.

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

Ваш вопрос довольно расплывчатый / неполный, с, это все, что я получил для вас.

Answer 2

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

На самом деле, это немного напоминает мне проблему разрезания торта, когда вы пытаетесь найти минимальное количество прямых нарезок, чтобы сделать x кусочков торта. Таким образом, решение может быть вдоль линий, для каждого провода, попытаться сделать наибольшее уменьшение в размере самого большого объекта, который может пройти. Это означало бы, когда это возможно, разрезать самые большие «дыры» пополам с каждым добавленным проводом.

edit: Когда я действительно попробовал свой предложенный алгоритм, я получил результаты, которые были хуже, чем наивная версия. При размещении проводов обязательно нужно учитывать минимальный размер.

Answer 3

Что означает штриховка для прямоугольника?

Можете ли вы перефразировать ваш вопрос?

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