Шаг сортировки по выпуклой оболочке

Что это означает, что мне делать, если несколько точек имеют одинаковый полярный угол относительно Po?

Скажем, P ₀ - это (0,0), P ₁ - это (1,1), а P ₂ - это (2,2). Теперь P ₁ и P ₂ имеют одинаковый угол относительно P ₀, и в этом случае вы отбрасываете P ₁ . Если есть больше точек между P ₀ и P ₂ с тем же углом, отбросьте все, кроме P ₂ ( и P ₀ конечно).

Как мне реализовать этап сортировки с использованием библиотеки C ++ STL (функция сортировки в алгоритме)? Особенно я имею в виду сортировку (P + 1, P + N, компаратор). Как мне определить функцию компаратора?

Не очень знаком с C ++ (STL), но проверьте, есть ли atan2 функция, которую вы можете использовать. См. Также: Найти угол между двумя точками относительно горизонтальной оси? и Как чтобы вычислить угол между линией и горизонтальной осью?

Вот моя реализация алгоритма сканирования Гарама для выпуклой оболочки на С ++

struct vert
{
    int x,y;
    float rad;
    int idx;
};    
bool operator<(const vert &a,const vert &b)//this is the function u are looking for
{
    if(a.rad<b.rad)
        return true;
    if(a.rad==b.rad)
    {
        if(a.y>b.y)
            return true;
        else if(a.y==b.y&&a.x>b.x)
            return true;
        else
            return false;
    }
    return false;
}    
vert operator-(vert x,vert y)
{
    vert tmp;
    tmp.x=x.x-y.x;
    tmp.y=x.y-y.y;
    return tmp;
}
double dist(vert a,vert b)
{
    vert ab=b-a;
    return sqrt(ab.x*ab.x+ab.y*ab.y);
}
int cross(vert a,vert b,vert c)
{
    vert ab,bc;
    ab=b-a;
    bc=c-b;
    return ab.x*bc.y-ab.y*bc.x;
}
int main()
{
    int t,i,j,k,n;
    //("example.txt","r",stdin);
    scanf("%d",&t);
    vert a[100009],point[100009];
    int kx,ky;
    while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&a[i].x,&a[i].y);
            a[i].idx=i+1;
        }
        vert d;
        d=a[0];
        for(i=1;i<n;i++)
        {
            if(a[i].y<d.y)
                d=a[i];
            else if(a[i].y==d.y&&a[i].x<d.x)
                d=a[i];
        }
        vector<vert> v;
        for(i=0;i<n;i++)
        {
            kx=a[i].x-d.x;
            ky=a[i].y-d.y;
            if(kx==0&&ky==0)
                continue;
            a[i].rad=atan2(kx,ky)*-1.00;
            v.push_back(a[i]);
        }
        sort(v.begin(),v.end());
        float rad=-10000;
        j=0;
        for(i=0;i<v.size();i++)
        {
            if(v[i].rad!=rad)
            {
                a[j++]=v[i];
                rad=v[i].rad;
            }
        }
        k=0;
        point[k++]=d;
        for(i=0;i<j;i++)
        {
            if(k<=1)
                point[k++]=a[i];
            if(cross(point[k-2],point[k-1],a[i])>0)
            {
                point[k++]=a[i];
            }
            else
            {
                do
                {
                    k--;
                    if(cross(point[k-2],point[k-1],a[i])>0)
                        break;
                }while(k>1);
                point[k++]=a[i];
            }
        }
        double dis=0;
        for(i=1;i<k;i++)
            dis+=dist(point[i],point[i-1]);
        dis+=dist(point[0],point[k-1]);
        printf("%0.2f\n",dis);
        for(i=0;i<k;i++)
            printf("%d ",point[i].idx);
        cout<<endl<<endl;;
    }
    return 0;
}

либо u может использовать функцию компаратора, либо u может перегрузить оператор ‹, как я сделал здесь. Это будет работать аналогично, но теперь вам не нужно передавать какую-либо функцию компаратора в качестве третьего аргумента в функции sort ().

надеюсь, это поможет

(B) Как мне реализовать этап сортировки с использованием библиотеки C ++ STL (функция сортировки в алгоритме)? Особенно я имею в виду сортировку (P + 1, P + N, компаратор). Как мне определить функцию компаратора?

Я предлагаю вам избегать беспорядочной арифметики с плавающей запятой. Как показано в упражнении 33.1-3 той же книги, вы можете просто отсортировать по полярному углу с помощью перекрестных произведений. Вот как это сделать:

struct Point {int x,y;}

int operator^(Point p1, Point p2) {return p1.x*p2.y - p1.y*p2.x;}

Point p0; //set this separately

bool operator<(Point p1, Point p2) 
{
    p1=p1-p0; p2=p2-p0; 
    if(p1.y==0&&p1.x>0) return true; //angle of p1 is 0, thus p2>p1
    if(p2.y==0&&p2.x>0) return false; //angle of p2 is 0 , thus p1>p2
    if(p1.y>0&&p2.y<0) return true; //p1 is between 0 and 180, p2 between 180 and 360
    if(p1.y<0&&p2.y>0) return false;
    return (p1^p2)>0; //return true if p1 is clockwise from p2
}

(A) Что это означает, что мне делать, если несколько точек имеют одинаковый полярный угол относительно Po?

Если p0, pi и pj коллинеарны, только самый дальний от p0 может быть частью выпуклой оболочки. Таким образом, мы должны убрать остальные точки. Мы можем сделать это на C ++. Начнем с определения скалярного произведения,

int operator*(Point p1, Point p2) {return p1.x*p2.x + p1.y*p2.y;}

и добавив эту строку в компаратор:

if((p1^p2)==0&&p1*p2>0) return p1*p1<p2*p2;

Теперь при одинаковом угле точки будут отсортированы по расстоянию от p0. Теперь мы можем использовать функцию unique из STL, чтобы удалить точки, как требуется, из vector<Point> P:

sort(P.begin(),P.end());
P.erase(unique(P.begin(),P.end(),eq),P.end());

Здесь функция eq возвращает истину, если точки имеют одинаковый угол.

bool eq(Point p1, Point p2) 
{
    p1=p1-p0; p2=p2-p0;
    return ((p1^p2)==0&&p1*p2>0); 
}