Время от времени мне приходится составлять карту, чтобы показать достопримечательности. Первый шаг для создания страниц, используя обычную сетку:
Мне не нравится решение, потому что а) есть несколько страниц с одиночными точками (например, страница 25), расположенными по краю, и б) слишком много страниц.
Первую проблему легко исправить с помощью кода, - переместите прямоугольник экстента страницы в центр экстента соответствующих точек:
Мне все еще не нравится это, это выглядит очень переполненным, потому что число страниц остается тем же самым. Помните, что все они в конечном итоге становятся настоящими бумажными страницами формата А3 в нескольких экземплярах отчета!
Итак, я приготовил код, который уменьшает количество страниц. В этом примере от 45 до 34.
Я не уверен, что это лучший результат, который может быть достигнут,
Какова наилучшая стратегия (псевдокод, публикация, библиотека Python) для перемещения по точкам, чтобы минимизировать количество прямоугольников заданного размера для захвата всех точек? Конечно, кто-то открыл это в теории игр, военного искусства или рыбной промышленности.
Это обновление к оригинальному вопросу:
Это показывает реальный экстент и необходимый размер страницы:
Увеличение масштаба изображения, показывающее 10 из 164 страниц:
Размер прямоугольника может измениться, как только он останется в пределах, то есть меньше - это хорошо.
Ответы:
Это не ответ, я просто решил опубликовать решение на Python для тех, кто заинтересован:
применил его в последнее время для планирования обследования:
ОБНОВИТЬ:
Похоже, что для некоторых паттернов, имеющих дело с «случайными» точками, первым должен быть путь. Я использовал кожуру «выпуклой оболочки», чтобы идентифицировать их, идея whuber, не могу найти пост, извините.
источник
Это похоже на геометрическую версию проблемы максимального покрытия, которая тесно связана с проблемой покрытия покрытия , и эти два NP-Complete.
Таким образом, чтобы решить это, можно использовать приближение. Я бы попробовал следующий алгоритм, и он, кажется, работает отлично. Хотя из-за сложности проблемы, мы не можем найти лучший ответ.
реализация этого алгоритма, только для круга, находится здесь: http://jsfiddle.net/nwvao72r/3/
источник