В настоящее время я пытаюсь построить область, охватываемую устройством за период работы. Первым шагом в этом процессе является построение многоугольника покрываемой области. Поскольку шаблон не имеет стандартной формы, выпуклые оболочки завышают площадь покрытия, переходя к максимально возможной области покрытия.
Я нашел статью, в которой рассматривается концепция генерации невыпуклых оболочек, но нет обсуждений того, как это реализовать на языке высокого уровня. http://www.geosensor.net/papers/duckham08.PR.pdf
Кто-нибудь видел прямой алгоритм построения невыпуклой оболочки или вогнутой оболочки или, возможно, какой-либо код Python для достижения того же результата?
Я пробовал выпуклые корпуса, в основном qhull, с ограниченным размером края с ограниченным успехом. Также я заметил некоторые лицензированные библиотеки, которые нельзя будет распространять, так что, к сожалению, это исключено. Любые лучшие идеи или поваренные книги?