c++ - 扫描算法的排序边

Question

我的类中有以下数据结构:

typedef vector< vector<int> > MxInt2d;
typedef vector< vector<double> > MxDouble2d;

class QSweep{   
public:
....
static MxDouble2d myPoints_;
MxDouble2d myEdges_;
}

哪里:每个点有 3 个分量，因此由索引、x 和 y 坐标给出；每条边由其源索引边[0] 和目标索引边[1] 给出，其中边[0]、边[1] 是 myPoints 数据结构的索引)。我的变量 myEdges_ 中有这条边。

问题如下:如何安排这些边缘以应用扫描算法并获得良好的结果和良好的结果(即边缘的所有交点)。到目前为止，我有两个不同的边缘排列标准，但它们都没有给我好的结果，只有好的结果(要么我没有获得所有的交点，要么我得到交点加上其他一些不是交点的点) .

这是我的标准:

标准 1(想法):

• 通过它们的 edge[0] 坐标的 x 坐标(如果 2 条边的 x 不同)

• 通过它们的 edge[0] 坐标的 y 坐标(如果 2 条边的 x 相等)

• 根据它们对应的斜率(当且仅当边的 x 和边的 y 相等)。

条件 1(代码):

  class QSweep{   
  public:
  ....
 static MxDouble2d myPoints_;
 MxDouble2d myEdges_;

 class order{
 public:
    bool operator() (const vector<int>& edge1, const vector<int>& edge2){
            //std::cout<<"inside sort"<<endl;
            //3 sort criteria
            return (myPoints_[edge1[0]][0]<myPoints_[edge2[0]][0])|| 
                       (myPoints_[edge1[0]][0]==myPoints_[edge2[0]][0]&& 
                        myPoints_[edge1[0]][1]<myPoints_[edge2[0]][1]) 
                   ||
                    (myPoints_[edge1[0]][0]==myPoints_[edge2[0]][0]&& 
                         myPoints_[edge1[0]][1]==myPoints_[edge2[0]][1]&& 
                     getSlope(myPoints_[edge1[0]][0],myPoints_[edge1[0][1],  
                                  myPoints_[edge1[1]][0],myPoints_[edge1[1]][0])
                     <
                         getSlope(myPoints_[edge2[0][0],myPoints_[edge2[0][1],    
                                  myPoints_[edge2[1]][0],myPoints_[edge2[1]][0]));
                    }
};

static double getSlope(double a, double b, double c, double d);
};

标准 2(想法):

• 通过它们的 edge[0] 坐标的 x 坐标(如果 2 条边的 x 不同)

• 根据它们对应的斜率(当 2 条边的 x 相等)

• 通过它们的 edge[1] 坐标的 y 坐标(当且仅当 x 的边和边的斜率相等)。

条件 2(代码):

class QSweep{   
public:
....
static MxDouble2d myPoints_;
MxDouble2d myEdges_;
class order{
public:
    bool operator() (const vector<int>& edge1, const vector<int>& edge2){
    return ((myPoints_[edge1[0]][0]<myPoints_[edge2[0]][0])||
       ((myPoints_[edge1[0]][0]==myPoints_[edge2[0[0])&&
            (getSlope(myPoints_[edge1[0]][0],myPoints_[edge1[0]][1],
                      myPoints_[edge1[1]][0],myPoints_[edge1[1]][1])
             <getSlope(myPoints_[edge2[0]][0],myPoints_[edge2[0]][1],
                      myPoints_[edge2[1]][0],myPoints_[edge2[1]][1]) ))||
    ((myPoints_[edge1[0]][0]==myPoints_[edge2[0]][0])&&(   
             getSlope(myPoints_[edge1[0]][0],myPoints_[edge1[0]][1],
                      myPoints_[edge1[1[0],myPoints_[edge1[1]][1])==
            getSlope(myPoints_[edge2[0]][0],myPoints_[edge2[0]][1],
                     myPoints_[edge2[1]][0],myPoints_[edge2[1]][1]) )
          &&(myPoints_[edge1[1]][1]<myPoints_[edge2[1]][1]))
                 );
}

};

是的，这看起来真的很复杂，我在我的算法中尝试了这些标准，但我没有获得所有的交叉点。所以我猜测扫描算法的边缘排序标准不好，因为我检测到一些交叉点而不是其他交叉点。提前感谢您的建议(或小意见)，马达丽娜

Answer 1

这与我们的问题没有直接关系，但我能否建议如果您使用简单的 Point 结构来表示 XY 坐标，您的代码将更具可读性？像这样的东西:

template <typename T> struct Point {
   Point( const T & ax, const T & ay ) : x( ax ), y( ay ) {}
   T x, y;
};

将是一个开始。然后，您可以创建 Point 的一维 vector ，并使用名称 x 和 y 而不是数组索引。

只是一个建议 - 请随意忽略...