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

Question

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

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

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

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

Answer 1

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

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