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

Question

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

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

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

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

Answer 1

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

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

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

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

Answer 2

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

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

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

Answer 3

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

Вы можете перефразировать свой вопрос?

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