algorithm - 凸包分拣步骤

Question

我正在阅读格雷厄姆扫描算法以从 CLRS 中找到凸包。CLRS 中针对 Convex hull 给出的算法是::

我无法理解这一行（算法的第 2 步）：

如果两个或多个点相对于 p0 具有相同的极角，那么除了最远的点之外，其他所有点都是 p0 和最远点的凸组合，因此我们完全不考虑它们。

1. 这是什么意思？如果多个点相对于 Po 有相同的极角怎么办？

也可以说，我做了一个结构

struct points
{
    int x, y;
} P[10000];

2. 我应该如何使用 C++ STL 库实现排序步骤？我的意思是，我应该如何定义比较器功能sort(P+1, P+N, comparator)？

Answer 1

这是什么意思，如果多个点相对于 Po 具有相同的极角，我该怎么办？

假设 P ₀是(0,0)， P ₁是(1,1)并且 P ₂是(2,2)。现在 P ₁和 P _{2相对于 P 0}具有相同的角度，在这种情况下您丢弃 P ₁。_{如果 P 0}和 P ₂之间有更多具有相同角度的点，则丢弃除 P _2之外的所有点（当然还有 P ₀）。

我应该如何使用 C++ STL（算法中的排序函数）库实现排序步骤？特别是我的意思是排序（P+1，P+N，比较器）。我应该如何定义比较器功能？

不太熟悉 C++ (STL)，但请检查它是否具有atan2您可以使用的功能。另请参阅：找到两点之间的角度，相对于水平轴？以及如何计算一条线与水平轴之间的角度？

Answer 2

这是我在 C++ 中对凸包的 gharam 扫描算法的实现

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;
}

您可以使用比较器功能，也可以像我在这里所做的那样使 operator< 重载。这将类似地工作，但现在您不必将任何比较器函数作为 sort() 函数中的第三个参数传递

我希望这有帮助

Answer 3

(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 的距离排序。现在我们可以使用uniqueSTL 中的函数根据需要从以下位置删除点vector<Point> P：

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

在这里，eq如果点的角度相同，则函数返回 true。

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