Какой алгоритм использовать для определения самых крайних точек области?

Question

[Родион Юрченко]

Добрый день всем!
Есть множество координат (абсолютно хаотично расставленные точки в пределах одного города) в виде lat:lng
Нужно соединить самые крайние точки между собой чтобы ограничить область
То есть чтобы все остальные точки остались внутри получившейся области

Не могу придумать - как определить именно самые крайние точки
Ну и в каком порядке их потом соединить между собой чтобы получилась именно область, а не что-то другое

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

Comments

[Сергей Соколов]

"bounding polygon"

Answer 1

[Stalker_RED]

Гугл: "многоугольник описывающий точки"
Первый результат: Построение минимальных выпуклых оболочек
Покатит?

Answer 2

[dom1n1k]

Запрос в гугл: convex hull algorithms
Алгоритмов много. Лично мне больше всего нравится QuickHull (называется так, потому что использует идею, похожую на quick sort) - имхо лучший баланс между скоростью и понятностью кода. И сам алгоритм, и готовые реализации гуглятся без проблем.