Нужно векторное произведение. Оно дает синус угла и позволяет понять, что один вектор лежит правее другого.
Если вы будете игнорировать точки уже на выпуклой оболочке, то все оставшиеся точки будут лежать в одной полуплоскости относительно данной. А дальше надо выбирать точку, вектор на которую правее. А если вектора коллиниарны - то ближайшую (или самую далекую, если точки на границе выпуклой оболочки вы хотите пропустить.
Тут одна проблема - если не выкидывать точки уже из оболочки, то может быть ситуация, когда вы рассматриваете ход из точки в середине стороны в выпуклой оболочке. Тогда точки вперед и назад вдоль границы нельзя разделить таким методом. Все векторные произведения будут нулевыми, и ближайшая точка может быть как сзади, так и спереди. Но можно добавить проверку с пердыдущей стороной оболочки. Вектор на следующую точку, если он дает 0 при произведении с этим, то он должен давать положительно скалярное произведение.
Вот набросок кода на C++, думайте, что это псевдокод.
vector<int> ConvexHull(vector<double> x, vector<double> y) {
int first = ...; // Тут поиск самой нижней-левой точки.
const int n = x.size();
int cur = first;
vector<int> ans{first};
// Текущий вектор стороны может идти вправо от самой нижней точки.
double side_x = 1;
double side_y = 0;
while (true) {
int bsti = -1;
// Вектор на лучшую точку.
double bst_x = 0;
double bst_y = 0;
// Расстояние до нее.
double bst_dist = 0;
for (i = 0; i < n; ++i) {
if (i == cur) continue;
// Вектор на текущую точку.
double cur_x = x[i] - x[cur];
double cur_y = y[i] - y[cur];
// Отсекаем точки назад вдоль оболочки на той же стороне.
// Можно заменить пометкой в bool in_hull[],
// которая ставится при добавлении точки в ответ (ans).
if (side_x*cur_y-side_y*cur_x == 0 && side_x*cur_x+side_y*cur_y < 0) continue;
double vec = bst_x*cur_y-bst_y*cur_x;
double dist = cur_x*cur_x+cur_y*cur_y;
// Берем точку, если она правее текущего кандидата. Или на той же прямой, но ближе.
if (bsti == -1 || vec < 0 || (vec == 0 && dist < bst_dist)) {
bsti = i;
bst_dist = dist;
bst_x = cur_x;
bst_y = cur_y;
}
}
// Сделали полный оборот.
if (bsti == first) break;
side_x = bst_x;
side_y = bst_y;
and.push_back(bsti);
cur = bsti;
}
return ans;
}
