1

我正在尝试解决找到凸多边形直径的问题，即它们之间具有最大距离的一对点。

http://cgm.cs.mcgill.ca/~orm/diam.html

我试图实现这里提到的算法/伪代码。但是对于使用这些点 (-3,-4) (2,-3) (4,3) (0,5) 制作的多边形，我得到了错误的答案

显然多边形的直径是 (-3,-4) (4,3)。但根据这里提到的伪代码，我得到的直径为 (-3,-4) (0,5)

struct vert
{
    long long int x,y,idx;
    double rad;
    int next;
    vert()
    {}
    vert(long long int _x,long long int _y)
    {
        x=_x;
        y=_y;
        rad=atan2(double(y),double(x));
    }
};
long long int dist(vert a,vert b)
{
    vert ab=b-a;
    return (ab.x*ab.x+ab.y*ab.y);
}
int cross(vert a,vert b,vert c)
{
    vert ab,ac;
    ab=b-a;
    ac=c-a;
    return ab.x*ac.y-ab.y*ac.x;
}
double area(vert a,vert b,vert c)
{
    double x=cross(a,b,c);
    x=abs(x/2.00);
    return x;
}
struct ret
{
    vert a,b;
    double dist;
};
ret comp(ret ans,vert a,vert b)
{
    if(dist(a,b)>ans.dist)
    {
        ans.a=a;
        ans.b=b;
        ans.dist=dist(a,b);
    }
    return ans;
}

ret rc_diameter(vector<vert> &v)
{
    int i,j,k,l,n;
    n=v.size();
    int a,b;
    int p,q,p0,q0;
    p0=p=0;
    q=1;
    ret ans;
    ans.dist=0;
    while(area(v[p],v[v[p].next],v[v[q].next])>area(v[p],v[v[p].next],v[q]))
    {
        q=v[q].next;
    }
    q0=q;
    ans=comp(ans,v[p],v[q]);
    while(q!=p0)
    {
        p=v[p].next;
        ans=comp(ans,v[p],v[q]);
        while(area(v[p],v[v[p].next],v[v[q].next])>area(v[p],v[v[p].next],v[q]))
        {
            q=v[q].next;
            if(p!=q0&&q!=p0)
                ans=comp(ans,v[p],v[q]);
            else
                return ans;
        }
        if(area(v[p],v[v[p].next],v[v[q].next])==area(v[p],v[v[p].next],v[q]))
        {
            if(p!=q0&&q!=p0)
                ans=comp(ans,v[p],v[v[q].next]);
            else
                ans=comp(ans,v[v[p].next],v[q]);
        }
    }
    return ans;
}

因此，任何人都可以告诉我伪代码或我的实现中是否存在问题，当我手动将此算法应用于给定的一组点时，我仍然得到 (-3,-4) (0,5) 为直径。

4

1 回答 1

1

可能有点晚了，但我看到您的 p0 初始值不正确。p0 应该是列表中的最后一个点 (pn)，而不是列表中的第一个点 (0)。换句话说，p0 是多边形 P 中第一个点的前一个点，p 是多边形 P 中的第一个点，q 是 p 之后的下一个点。

于 2013-03-08T16:40:19.407 回答