Как мне найти самый сложный выпуклый многоугольник, содержащий множество точек?

Question

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

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

Answer 1

Похоже, вы ищете алгоритм выпуклой оболочки ? Прошло уже более десяти лет с тех пор, как меня учили об этом, но имя Грэм Скан запомнилось мне и, вероятно, будет тем, с чего я начну.

Answer 2

Взгляните на Алгоритм Грэма .

Answer 3

Qhull - хорошее программное обеспечение для вычисления 2D выпуклых оболочек.

Answer 4

Если это проблема реального мира - например, не академическая - , на самом деле никогда не существует причины для решения такой общей проблемы самостоятельно.