确定两个向量是否包含相同的两个相邻项

Question

我有一个问题涉及确定两个向量是否包含两个相同的元素.元素可以是向量中的任何位置,但它们必须相邻.

已编辑更多示例

例如,比较时,以下两个向量将返回false.

向量1 = [0,1,2,3,4,6]

向量2 = [1,4,2,0,5,3]

但以下两个将返回true:

向量1 = [0,1,2,3,4,5]

向量2 = [4,2,1,5,0,3]

因为第一个向量中的1,2对应于第二个向量中的2,1.

真正:

向量1 = [0,1,2,3,4,5]

向量2 = [1,4,2,0,5,3]

{5,0}是一对,尽管在矢量周围循环(我原先说这是假的,感谢你发现'来自莫斯科的'弗拉德').

真正:

向量1 = [0,1,2,3,4,5]

向量2 = [4,8,6,2,1,5,0,3]

{2,1}仍然是一对,即使他们不在同一个位置

实际的应用是我有一个多边形(面),其中N个点存储在一个向量中.为了确定一组多边形是否完全包围3D体积,我测试每个面以确保每个边由另一个面共享(其中边由两个相邻点定义).

因此,Face包含指向Points的指针向量...

std::vector<Point*> points_;

并检查Face是否被包围,Face包含一个成员函数...

bool isSurrounded(std::vector<Face*> * neighbours)
{
    int count = 0;
    for(auto&& i : *neighbours)     // for each potential face
        if (i != this)              // that is not this face
            for (int j = 0; j < nPoints(); j++) // and for each point in this face
                for (int k = 0; k < i->nPoints(); k++ ) // check if the neighbour has a shared point, and that the next point (backwards or forwards) is also shared
                    if ( ( this->at(j) == i->at(k) )        // Points are the same, check the next and previous point too to make a pair
                       && (    ( this->at((j+1)%nPoints()) == i->at((k+1)%(i->nPoints())) )
                            || ( this->at((j+1)%nPoints()) == i->at((k+i->nPoints()-1)%(i->nPoints())) )))
                        { count++; }
    if (count > nPoints() - 1) // number of egdes = nPoints -1
        return true;
    else
        return false;
}

现在,显然这段代码太可怕了.如果我在两周内回到这里,我可能会理解它.所以面对原来的问题,你怎么能整齐地检查这两个向量？

请注意,如果您尝试解密提供的代码.at(int)返回面中的Point并nPoints()返回面中的点数.

非常感谢.

Answer 1

效率不高，但跟随是可能的。

bool comparePair ( pair<int,int> p1, pair<int,int> p2 ) {
  return ( p1.first == p2.first && p1.second == p2.second )
           || ( p1.second == p2.first && p1.first == p2.second );
}

//....

vector< pair<int,int> > s1;
vector< pair<int,int> > s1;
vector< pair<int,int> > intersect( vec1.size() + vec2.size() );

for ( int i = 0; i < vec1.size()-1; i++ ) {
  pair<int, int> newPair;
  newPair.first = vec1[i];
  newPair.first = vec1[i+1];
  s1.push_back( newPair );
}

for ( int i = 0; i < vec2.size()-1; i++ ) {
  pair<int, int> newPair;
  newPair.first = vec2[i];
  newPair.first = vec2[i+1];
  s2.push_back( newPair );
}

auto it = std::set_intersection ( s1.begin(), s1.end(), s2.begin(), s2.end(), 
                                   intersect.begin(), comparePair );

return ( it != intersect.begin() ); // not sure about this.