Алгоритм для многоугольника

[dklinge]

Столкнулся с проблемой при составлении алгоритма для рисования многоугольника по случайным точкам.
Пользователь задаёт N случайных точек struct TPoint { int x, y; };, по ним нужно составить многоугольник без самопересечений.

Может кто-нибудь помочь с алгоритмом? Я попробовал отсортировать точки по возрастанию Х, но столкнулся с проблемой, как среди точек найти следующую с максимальным Y.
Может, есть какой-нибудь ещё не сильно сложный алгоритм?

[Аватар]

А вот графическое представление одного из алгоритмов построения

[dklinge]

Да, как должно выйти, я понимаю. Есть какой-нибудь алгоритм для этого или готовый код для сортировки точек / отрисовки линий?
По рисунку: точки сравниваются и берётся ближайшая по Х с наибольшим Y?

[Аватар]

А это и есть алгоритм. Сначала от левой крайней до правой крайней точки огибающую по низу ломанную строим. Потом соединяем отрезками точки слева направо отсортированные по возрастанию координаты по оси абсцисс

[dklinge]

Не выходит построить ломанную по нижним точкам.
Выходит так, что линия идёт просто по всем точкам.
Вот код:

for (int i = 0; i < N; i++) {
		int max = i + 1;
		for (int j = i + 1; j < N; j++) {
			if (pt2[j].y > pt2[max].y && pt2[j].x < pt2[max].x) max = j;
			MoveToEx(dc, pt1[i].x, pt1[i].y, NULL);
			LineTo(dc, pt2[max].x, pt2[max].y);
		}

	}

Пытался находит ближайшую точку, которая находится ниже остальных, но не вышло.

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

[Аватар]

Выбирай любой алгоритм построения выпуклой оболочки набора точек в
https://ru.wikipedia.org/wiki/%D0%A1...BC%D0%BE%D0%B2
там их куча

[dklinge]

Всё же написал программу, не могли бы Вы её проверить на правильность?
Сначала я сортирую все точки по возрастанию Х.
Затем нахожу точку с максимальным Y, эта точка и будет первой, с которой начинается цикл.
После этого я нахожу точку с максимальным Y, игнорируя первый элемент (for (int i = 1; i < N; i++)), эта точка будет последней.
В итоге у меня есть начало и конец линии, остальные точки между первой и последней соединяются по возрастанию Х, а первую и последнюю я в самом конце соединяю.

Нашлась ошибка.

[Аватар]

Не понял - дважды по возрастанию Y. Проверь на бумаге с карандашом. Вангую - алгоритм будет с самопересечением.

[dklinge]

Так и есть, иногда выходит пересечение.
Моя задумка была в том, чтобы ломанная начиналась с самой низшей точки, а заканчивалась бы второй по наибольшему Y точкой.

Почему-то иногда появляется сбой во второй и третьей точках с конца. Они будто меняются местами в очереди.

[Poma][a]

У меня вот такое чудо есть :

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
 
#define eps 1e-8
 
using namespace std;
 
struct point
{
    int x, y;
    bool operator < (const point& a)
    {
        return this->x < a.x || this->x == a.x && this->y < a.y;
    }
 
    point operator - (const point& a)
    {
        this->x -= a.x;
        this->y -= a.y;
 
        return *this;
    }
};
 
int vect_mult(point a, point b, point c)
{
    point A = a - b,
          B = c - b;
 
    return A.x * B.y - B.x*A.y;
}
 
int main()
{
    int n;  
    cin >> n;
    vector<point> v(n);
     
    for (int i = 0; i < n; i++)
        cin >> v[i].x >> v[i].y;
 
    sort(v.begin(), v.end());
    point beg = v.front(),
          end = v.back();
 
    vector<point> up, down;
    up.push_back(beg);
    down.push_back(end);
 
    for (int i = 1; i < v.size(); i++)
    {
        if (vect_mult(end, beg, v[i]) > eps || i == v.size()-1)
        {
            //while (up.size() >= 2 && vect_mult(up[up.size() - 2], up[up.size() - 1], v[i]) < eps)
                //up.pop_back();
            up.push_back(v[i]);
        }
 
        if (vect_mult(end, beg, v[i]) < -eps || i == v.size() - 1)
        {
            //while (down.size() >= 2 && vect_mult(down[down.size() - 2], down[down.size() - 1], v[i]) > eps)
                //down.pop_back();
            down.push_back(v[i]);
        }
    }
     
    vector<point> ans;
 
    for (int i = 0; i < up.size(); i++)
        ans.push_back(up[i]);
         
    for (int i = down.size() - 2; i > 0; i--)
        ans.push_back(down[i]); 

    return 0;
 
}

Он кажется будет лажать на одном типе тестов. Если такая ересь вам сойдет (я ее, кстати, не проверял), то скажу свои подозрения