Как вы генерируете невыпуклую оболочку из ряда точек?

Question

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

Я нашел документ, который, кажется, охватывает концепцию генерации невыпуклой оболочки, но не обсуждает, как реализовать это на языке высокого уровня.http://www.geosensor.net/papers/duckham08.PR.pdf

Кто-нибудь видел прямой алгоритм построения невыпуклой оболочки или вогнутой оболочки или, возможно, любого кода на Python для достижения того же результата?

Я пробовал выпуклые корпуса, в основном qhull, с ограниченным размером кромки с ограниченным успехом.Также я заметил несколько лицензированных библиотек, которые не смогут распространяться, так что, к сожалению, это не обсуждается.Есть лучшие идеи или кулинарные книги?

Answer 1

Вы можете попробовать заглянуть в Alpha Shapes. Библиотека CGAL может их вычислить.

Редактировать : Я вижу, что документ, который вы связали, ссылается на альфа-фигуры, а также содержит список алгоритмов. Этого уровня недостаточно для вас? Поскольку вы указали python как тег, я уверен, что в Python есть библиотеки триангуляции Делоне, которые, я думаю, являются самой сложной частью реализации алгоритма; вам просто нужно убедиться, что вы можете изменить полученный результат триангуляции. Функции пограничных запросов, вероятно, могут быть реализованы с помощью ассоциативных массивов.