rotating_calipers
Rotating calipers 1.0
Вращающиеся суппорты - это модуль Python, реализующий алгоритм с тем же именем.
Алгоритм был впервые изобретен Микалелем Шамосом в 1978 году и получил свое название «вращающиеся суппорты» благодаря Годфриду Туссенту, который показал его в своей статье в 1983 году.
Метод назван так, потому что идея аналогична вращению пружинного суппорта Vernier, расположенного на внешней стороне выпуклого многоугольника. Каждый раз, когда одно лезвие суппорта лежит на краю многоугольника, он образует антиподальную пару с точкой или краем, касающимся противоположного лезвия. Полное «вращение» суппорта вокруг многоугольника обнаруживает все антиподальные пары; Набор всех пар, рассматриваемый как график, образует фаркл. Метод вращающихся суппортов может быть интерпретирован как проективный двойник алгоритма линейки зачистки, в котором развертка находится на склонах линий, а не через X- или Y-координаты точек.
Выше описание было адаптировано на странице Википедии: https://en.wikipedia.org/wiki/rotating_calipers
Алгоритм «вращающихся суппортов» был реализован мной для университетского проекта. Удивительно, что я пережил много проблем с поиском эффективного решения в Python. Вот почему я хотел поделиться этим со всеми, кто нуждается в быстрой реализации «вращающихся суппортов» в Python.
Поскольку вращающиеся суппорты работают в линейное время, ему нужен выпуклый корпус на входе, вычисляется здесь с использованием алгоритма Грэма, который работает в O (NLOGN). В целом Algorihm (алгоритм Грэма + вращающиеся суппорты) Сложность - O (nlogn) + O (n) = O (nlogn)
Linux:
Пример использования можно найти здесь
