Я хотел бы извиниться перед всеми постами ниже. Выбрал не тот форум, чтобы опубликовать это в оригинале. Однако вместо того, чтобы сделать это пустой тратой, я переработал вопрос, чтобы он стал настоящей проблемой «теоретической информатики».
Задача: Создать алгоритм, который принимает набор из n упорядоченных точек в 2D-плоскости, которые образуют контур простого многоугольника A, который может быть или не быть вогнутым, и создает новый многоугольник B с m точками, так что:
- все точки в A содержатся в B
- 3 <= m <n
- B - многоугольник в наборе всех B с наименьшей площадью
- B должен быть простым многоугольником (то есть без самопересечений).
- Вход в алгоритм - полигон A и «m».
- Совпадение сегментов в B с сегментами в A допускается.
Некоторые примеры входных и ожидаемых результатов:
- Если A является квадратом, а m равно 3, то B будет треугольником с наименьшей площадью поверхности, содержащей A.
- Если A является шестиугольником, а m равно 4, то B будет четырехугольником с наименьшей площадью поверхности, которая содержит A.
Удачи всем, кто решает эту проблему. Я могу обещать вам, что это будет очень сложно, особенно сейчас, когда решение должно быть оптимальным.
ds.algorithms
cg.comp-geom
polygon
Тирлан
источник
источник
Ответы:
Я не знаю, как выглядят ваши полигоны, но, возможно, достаточно упрощенной версии алгоритма Рамера-Дугласа-Пекера :
Граница многоугольника (
Для более сложных алгоритмов вы можете искать « методы обобщения полигонов », хотя ваше первое условие (точки в A содержатся в B) подразумевает некоторые дополнительные операции масштабирования.
источник
Я давно написал статью, в которой подробно описан алгоритм линейного времени для нахождения наименьшего треугольника площади, включающего множество точек (или многоугольник):
За нашей работой следовал общий алгоритм:
Вы можете использовать Google Scholar для отслеживания тех более поздних статей, в которых приводятся улучшения и сопутствующая работа.
источник