Самый маленький выпуклый многоугольник вокруг точки

Question

Я получил кучу 2d очков. То, что я пытаюсь найти, - это наименьший многоугольник вокруг (созданный из минимального набора точек, которые полностью охватывают) одной конкретной точки. Я пытался использовать выпуклый корпус и Вороного, но ни один из них не дал результатов, которые я искал, и у меня заканчиваются идеи ...

Я хочу найти строки (красным цветом), которые представляют наименьший выпуклый многоугольник вокруг точки (зеленым цветом), как показано на рисунке ниже:

Другой пример:

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

Answer 1

Начните с любой черной точки на диаграмме, назовем ее A. Нарисуйте линию от точки A до зеленой точки G. Теперь нарисуйте линию от точки A до любой другой точки A1, A2, .... Если по часовой стрелке эта строка находится после строки AG, игнорируйте ее. Из всех других линий выберите ту, которая образует наименьший угол с линией AG. Теперь переместите точку А к следующей точке. Повторите, пока вы не посещаете точку во второй раз.