Python - выпуклый корпус с некоторыми допустимыми внутренними точками

Question

Я хотел бы сделать выпуклую оболочку из набора 2D точек (в Python).Я нашел несколько примеров, которые помогли, но у меня есть дополнительная функция, которую я бы не смог реализовать.То, что я хочу сделать, это создать выпуклый корпус, но позволить ему подбирать внутренние точки, если они достаточно "близко" к границе.См. Рисунок ниже -> если тета

Очевидно, что это может усложнить ситуацию, поскольку я 'узнал из моих мыслей и тестов.Например, если будет добавлена ​​внутренняя точка, то это может потенциально позволить добавить еще одну внутреннюю точку.

Скорость на самом деле не имеет значения, так как количество точек, с которыми я буду работать, будет относительномаленький.Я предпочел бы иметь более надежный алгоритм, чем быстрый.

Мне интересно, знает ли кто-нибудь о каком-либо таком примере или мог бы указать мне правильное направление, с которого начать.Благодаря.

Answer 1

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

Answer 2

Понятие, которое вы ищете, может иметь альфа-форму. Настраивая альфа, вы допускаете больше или меньше очков в своем вогнутом корпусе. Посмотрите на алгоритм Edelsbrunner для поиска альфа-формы.

Answer 3

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