-3

警告。巨大的问题长度。

你好。因此，我正在尝试编写一个程序，该程序将 xy 平面中的一系列 n 点作为输入（一个简单的多边形），以及一条线 ax + by =c，并输出该线划分的多边形列表原一成。

所以我定义以下内容：

      struct point
    {
        public:
        float x, y;
        list <point>::iterator it;//if the point is an intersection point, this points to the position in the other list in class polygon where the point is located. This value is not defined for a point which is only in list pts (see class polygon)
        bool operator <(point );
        int pair;//paired intersection points will have identical pairing values 
        int poly;//poly shows if it is part of polygon or not
        point intersection( point, point, line);//returns the point of intersection

         void output();
         };

    class polygon
    {
        public:
        int n;
        list <point> pts;//stores points of original polygon as well as intersection points
        list <point> intr;// stores intersection points
        void init_it();//initialises iterators of points present in original polygon
        void init_pair();//initialises "pair" for consecutive points as 1,1,0,0,1,1...
//This allows pairing up of consecutive points the line intersects for convenient traversal of the polygon in one direction only
        void intersects(line);//solves every relevant side of polygon with the line to get a list of relevant points
        void output();
        polygon()
        {n=0;}
    };

    class line
    {
        public:
        float a,b,c;    
        float eval(point p);
    };

看看这里的intersects()andmain()函数。

void polygon::intersects(line l)
{
    list <point>::iterator i=pts.begin();
    list <point>::iterator j=i;

    while(true)
    {   
        j++;
        if (j==pts.end())
               j=pts.begin();


                       if(intersect(*i,*j,l))
           {
            point p=intersection(*i,*j,l);
            pts.insert(j,p);
            intr.push_front(p);
            i++;
            list <point>::iterator k=intr.begin();
            (*i).it=k;
            (*k).it=i;
            (*k).poly=(*i).poly=0;
        }
    i=j;
}

}

（摘自main()）

while(p.n>0)//flag= new beginning, beg= current beginning
    { 
        //Initialise stuff
        while(i!=beg)   
        {


            t.pts.push_back(*i);
            if( (*i).poly==1 )//point from original polygon 
            {
            //do stuff, increment i
            }
            else if(((*i).poly)==0)
            {
                //DO something



                list <point>:: iterator j= (*i).it;
                list <point>:: iterator k1=j,k2=j;
                if( j==p.intr.begin() )
                {
                    j++;
                }
                else if(j==end)
                {
                    j--;
                }
                else
                {// Gets into an infinite loop here


                    k1--;
                    k2++;
                    if((*j).pair==(*k1).pair)
                    {

                        j--;
                    }
                    else
                    {
                        j++;
                    }
                }
                t.pts.push_back(*j);
                i=(*j).it;// This line is supposed to set i to the next iterator in the "intr" list, but it doesnt change!


            }
            else
            i++;
        }

    output.push_back(t);
    }

这里的问题在于main()函数。当我写的时候i=(*j).it，它不会返回我想要的值。迭代器似乎指向同一个点，导致无限循环。我找不到任何问题。

这是一个带有答案的示例测试用例：

测试用例：

12
0 0 0 5 5 5 5 2 2 2 2 3 4 3 4 4 1 4 1 1 5 1 5 0
1 0 3

预期答案：

4
8
0 0 0 5 3 5 3 4 1 4 1 1 3 1 3 0
4
2 2 2 3 3 3 3 2
4
3 0 3 1 5 1 5 0
8
3 2 3 3 4 3 4 4 3 4 3 5 5 5 5 2

注意：我在这里使用的算法似乎有效（与其他使用过类似算法的人一起检查过），但我在实现它时似乎犯了一些错误。

4

1 回答 1

1

您的问题有很多代码需要查看。但是，另一方面，我完全了解这个几何问题。因此，我将为您提供一个解决方案：

首先，保存线和点的类（简化）：

struct point_2d
{
    float x , y;

    point_2d( float _x = 0.0f , float _y = 0.0f) : x( _x ) , y( _y ) {}
};


struct line
{
    float a,b,c,d; //ax + by + c = 0

    float relative_position(const point_2d& point) { return a*point.x + b*point.y + c; }
};


using polygon = std::vector<point_2d>;

这是一个基于 STL 算法的解决方案（我更喜欢这个）：

std::pair<polygon,polygon> divide_polygon(const polygon& poly , const line& ln)
{
    polygon up_poly;
    polygon down_poly;

    std::partition_copy( std::begin( poly ) , std::end( poly ) , std::back_inserter( up_poly ) , std::back_inserter( down_poly ) , [](const point_2d& point) { return ln.relative_position( point ) >= 0; });

    return std::make_pair( up_poly , down_poly );
}

请注意，我关闭了对您问题的前两行的回答（问题的抽象描述）。此代码完美运行，并利用了 STL（算法、容器等）。对于你的问题，我没有给你确切的答案。我不会为您提供在线法官问题的解决方案。那是你的功课。

于 2013-08-15T17:25:54.187 回答