упорядочение ребер для алгоритма подметания

Question

В моем классе есть следующие структуры данных:

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

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

, где: Каждая точка имеет 3 компонента, которые задаются индексом, координатами x и y; Каждое ребро задается его исходным index-edge [0] и его целевым index-edge [1], где edge [0], edge [1] являются индексами структуры данных myPoints). У меня есть эти ребра в моей переменной myEdges _.

Вопрос заключается в следующем: как нужно расположить эти ребра для применения алгоритма развертки и получения только хороших результатов и хороших результатов (то есть всех пересечений ребер). Пока у меня есть два разных критерия для расположения ребер, но ни один из них не дает мне хороших результатов и только хороших результатов (либо я не получаю все пересечения, либо я получаю пересечения плюс некоторые другие точки, которые не являются пересечениями) .

Вот мои критерии:

критерий 1 (идея):

• по координате x их ребра [0] (если x двух ребер различны)

• по координате y их ребра [0] (если 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 (идея):

• по координате x их ребра [0] (если x двух ребер различны)

• по их соответствующим наклонам (если x равны двум ребрам)

• по координате y их ребра [1] (если 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]))
                 );
}

* +1047 *}; * * 1 048

да, это выглядит действительно сложно, я попробовал эти критерии в своем алгоритме, и я не получаю все пересечения. Поэтому я предполагаю, что критерии порядка для моих ребер для алгоритма развертки не годятся, потому что я обнаруживаю некоторые пересечения, но не другие. Спасибо за ваши предложения (или небольшие мнения) заранее, Madalina

Answer 1

Ничего общего с нашим вопросом, но могу ли я предположить, что ваш код был бы чертовски удобнее, если бы вы использовали простую структуру Point для представления координат XY? что-то вроде:

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

будет началом. Затем вы можете создать 1-мерные векторы Point и использовать имена x & y, а не индексы массива.

Просто предложение - не стесняйтесь игнорировать ...

Answer 2

Для алгоритмов разметки вы обычно используете лексикографическую сортировку по вашим точкам:

• Сортировать по X, если компонент X двух сравниваемых точек равен, вместо этого сортировать по Y. В 3D вы можете расширить до Z-компонента и т. Д.

Однако я сомневаюсь, что сортировка - это корень ваших проблем (ложные и пропущенные пересечения).

Алгоритмы Sweepline очень чувствительны к ошибкам округления. Работать с арифметикой с плавающей запятой невозможно, если вы не уверены, что ваша математика сохраняет достаточную точность, чтобы дать вам действительные результаты.

Взгляните на эту веб-страницу для получения более подробной информации (и решений) о таких проблемах:

http://www.cs.cmu.edu/~quake/robust.html

Удачи.

Кстати - вы пишете скан пересечения Бентли-Оттмана, не так ли? Они даже более чувствительны, чем другие алгоритмы развертки, поскольку вставка точки пересечения немного изменит наклон пересекающихся ребер из-за конечной точности поплавков.