Das Feststellen, ob zwei Vektoren zwei benachbarte Elemente enthalten, die gleich sind

Question

Ich habe ein Problem, das darin besteht zu bestimmen, ob zwei Vektorelemente enthalten, die gleich sind. Die Elemente können überall im Vektor sein, aber sie müssen benachbart sein.

FÜR MEHR BEISPIELE BEARBEITET

Zum Beispiel würden die folgenden zwei Vektoren bei Vergleich falsch zurückgeben.

Vektor 1 = [ 0, 1, 2, 3, 4, 6 ]

Vektor 2 = [ 1, 4, 2, 0, 5, 3 ]

Aber die folgenden beiden würden wahr zurückgeben:

Vektor 1 = [ 0, 1, 2, 3, 4, 5 ]

Vektor 2 = [ 4, 2, 1, 5, 0, 3 ]

weil das 1,2 im ersten Vektor mit dem 2,1 im zweiten Vektor übereinstimmen würde.

Wahr:

Vektor 1 = [ 0, 1, 2, 3, 4, 5 ]

Vektor 2 = [ 1, 4, 2, 0, 5, 3 ]

{5,0} ist ein Paar, trotz Rundumloop des Vektors (ich habe ursprünglich gesagt, dass dies falsch ist, vielen Dank, dass du das bemerkt hast, 'Vlad von Moskau').

Wahr:

Vektor 1 = [ 0, 1, 2, 3, 4, 5 ]

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

{2,1} ist immer noch ein Paar, auch wenn sie sich nicht an derselben Position befinden

Die tatsächliche Anwendung besteht darin, dass ich ein Polygon (Gesicht) mit N Punkten in einem Vektor habe. Um zu bestimmen, ob eine Reihe von Polygonen ein 3D-Volumen vollständig einschließen, überprüfe ich jedes Gesicht, um sicherzustellen, dass jede Kante von einem anderen Gesicht geteilt wird (wobei eine Kante durch zwei benachbarte Punkte definiert ist).

Also enthält Face einen Vektor von Zeigern auf Punkte...

std::vector points_;

und um zu überprüfen, ob ein Face umgeben ist, enthält Face eine Memberfunktion...

bool isSurrounded(std::vector * neighbours)
{
    int count = 0;
    for(auto&& i : *neighbours)     // für jedes potenzielle Gesicht
        if (i != this)              // das nicht dieses Gesicht ist
            for (int j = 0; j < nPoints(); j++) // und für jeden Punkt in diesem Gesicht
                for (int k = 0; k < i->nPoints(); k++ ) // überprüfen, ob der Nachbarpunkt geteilt wird und ob der nächste Punkt (rückwärts oder vorwärts) auch geteilt wird
                    if ( ( this->at(j) == i->at(k) )        // Punkte sind gleich, prüfen Sie den nächsten und den vorherigen Punkt auch, um ein Paar zu bilden
                       && (    ( 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) // Anzahl der Kanten = nPoints -1
        return true;
    else
        return false;
}

Nun, offensichtlich ist dieser Code schrecklich. Wenn ich in 2 Wochen darauf zurückkomme, werde ich ihn wahrscheinlich nicht verstehen. Angesichts des ursprünglichen Problems, wie würden Sie elegant die beiden Vektoren überprüfen?

Beachten Sie, wenn Sie den bereitgestellten Code entschlüsseln möchten. at(int) gibt den Punkt in einem Gesicht zurück und nPoints() gibt die Anzahl der Punkte in einem Gesicht zurück.

Vielen Dank.

Answer 1

Hier ist mein Versuch, dieses Problem zu lösen. Ganz einfach, durchlaufen Sie a, finden Sie das gleiche Element in b und vergleichen Sie dann das nächste Element in a mit den Elementen vor und nach unserer Position in b.

Wenn es etwas ausführlicher ist als nötig, dann damit diese Funktion mit beliebigen Containern aufgerufen werden kann. Die einzige Anforderung ist, dass die Iteratoren der Container bidirektional sein müssen.

#include 
#include 
#include 
#include 

using namespace std;

template 
pair get_neighbors(Iter begin, Iter current, Iter end)
{
    auto p = make_pair(end, next(current));
    if(current != begin)
        p.first = prev(current);
    return p;
}

template 
bool compare_if_valid(Iter1 p1, Iter1 end1, Iter2 p2)
{
    return p1 != end1 && *p1 == *p2;
}

template 
auto neighbors_match(const C1 & a, const C2 & b) ->
    decltype(make_pair(begin(a), begin(b)))
{
    for(auto i = begin(a); i != end(a) && next(i) != end(a); ++i)
    {
        auto pos_in_b = find(begin(b), end(b), *i);
        if(pos_in_b != end(b))
        {
            auto b_neighbors = get_neighbors(begin(b), pos_in_b, end(b));
            if(compare_if_valid(b_neighbors.first, end(b), next(i)))
                return {i, b_neighbors.first};
            else if(compare_if_valid(b_neighbors.second, end(b), next(i)))
                return {i, pos_in_b};
        }
    }
    return {end(a), end(b)};
}

int main()
{
    vector a = {0, 1, 2, 3, 4, 5};
    vector b = {1, 4, 2, 0, 5, 3};
    cout << boolalpha << (neighbors_match(a, b).first != a.end()) << endl;
    vector a2 = {0, 1, 2, 3, 4, 5};
    list b2 = {4, 2, 1, 5, 0, 3};
    auto match = neighbors_match(a2, b2);
    cout << boolalpha << distance(a2.cbegin(), match.first)
         << ' ' << distance(b2.cbegin(), match.second) << endl;
    return 0;
}

Answer 2

Im Grunde genommen fragen Sie, ob die Kantenmengen von zwei Flächen (nennen wir sie a und b) disjunkt sind oder nicht. Dies kann in das Problem aufgeteilt werden, ob sich eine der Kanten in b in a befindet, was einfach ein Mitgliedschaftstest ist. Das Problem dabei ist jedoch, dass Vektoren nicht gut für Mitgliedschaftstests geeignet sind.

Meine Lösung besteht darin, einen der Vektoren in ein unordered_set< pair > umzuwandeln. Ein unordered_set ist einfach eine Hashtabelle, und die Paare repräsentieren die Kanten.

Bei der Darstellung von Kanten habe ich ein Normalisierungsschema gewählt, bei dem die Indizes der Eckpunkte in aufsteigender Reihenfolge sind (so dass [2,1] und [1,2] beide als [1,2] in meinem Kanten-Set gespeichert werden). Dies erleichtert den Gleichheitsvergleich ein wenig (da es nur der Gleichheit des Paares entspricht).

Hier ist meine Lösung:

#include 
#include 
#include 
#include 
#include 
using namespace std;

using uint = unsigned int;
using pii = pair;

// Einfaches Hashing für Paare von Ganzzahlen
struct pii_hash {
    inline size_t
    operator()(const pii & p) const
    {
        return p.first ^ p.second;
    }
};

// Ordnen von Paaren von Ganzzahlen, damit die kleinere Zahl zuerst steht
pii ord_pii(int x, int y) { return x < y ? pii(x, y) : pii(y, x); }

bool
shares_edge(vector a, vector b)
{
    unordered_set edge_set {};

    // Ungeordnetes Set von Paaren erstellen (das Kanten-Set)
    for(uint i = 0; i < a.size() - 1; ++i)
        edge_set.emplace( ord_pii(a[i], a[i+1]) );

    // Überprüfen, ob irgendwelche Kanten in B im Kanten-Set von A sind
    for(uint i = 0; i < b.size() - i; ++i)
    {
        pii edge( ord_pii(b[i], b[i+1]) );

        if( edge_set.find(edge) != edge_set.end() )
            return true;
    }

    return false;
}

int main() {
    vector
        a {0, 1, 2, 3, 4, 5},
        b {1, 4, 2, 0, 5, 3},
        c {4, 2, 1, 0, 5, 3};

    shares_edge(a, b); // false
    shares_edge(a, c); // true

    return 0;
}

In Ihrem speziellen Fall möchten Sie möglicherweise die Funktion shares_edge zu einer Member-Funktion Ihrer Klasse Face machen. Es könnte auch vorteilhaft sein, das Kanten-Set vorzuberechnen und als Instanzvariable von Face zu speichern, aber das hängt davon ab, wie oft sich die Kantendaten ändern im Vergleich dazu, wie oft diese Berechnung durchgeführt wird.

EDIT Zusätzliche Lösung

EDIT 2 Fehler korrigiert aufgrund der Änderung der Frage: Das Kanten-Set umschließt jetzt die Punktliste.

So würde es aussehen, wenn Sie das Kanten-Set hinzufügen würden, das bei der Initialisierung in irgendeiner Form einer Klasse Face vorberechnet wird. Die private verschachtelte Klasse Edge kann als Verzierung Ihrer aktuellen Darstellung einer Kante angesehen werden (d.h. zwei benachbarte Positionen in der Punkteliste), mit einer tatsächlichen Klasse, damit Sammlungen wie Sets den Index in die Punkteliste als tatsächliche Kante behandeln können:

#include 
#include 
#include 
#include 
#include 
#include 

using uint = unsigned int;

class Face {
    struct Edge {
        int  _index;
        const std::vector *_vertList;

        Edge(int index, const std::vector *vertList)
            : _index {index}
            , _vertList {vertList}
        {};

        bool
        operator==(const Edge & other) const
        {
            return
                ( elem() == other.elem() && next() == other.next() ) ||
                ( elem() == other.next() && next() == other.elem() );
        }

        struct hash {
            inline size_t
            operator()(const Edge & e) const
            {
                return e.elem() ^ e.next();
            }
        };

    private:
        inline int elem() const { return _vertList->at(_index); }

        inline int
        next() const
        {
            return _vertList->at( (_index + 1) % _vertList->size() );
        }
    };

    std::vector                     _vertList;
    std::unordered_set _edgeSet;

public:

    Face(std::initializer_list verts)
        : _vertList {verts}
        , _edgeSet {}
    {
        for(uint i = 0; i < _vertList.size(); ++i)
            _edgeSet.emplace( Edge(i, &_vertList) );
    }

    bool
    shares_edge(const Face & that) const
    {
        for(const Edge & e : that._edgeSet)
            if( _edgeSet.find(e) != _edgeSet.end() )
                return true;

        return false;
    }

};

int main() {

    Face
        a {0, 1, 2, 3, 4, 5},
        b {1, 4, 2, 0, 5, 3},
        c {4, 2, 1, 0, 5, 3},
        d {0, 1, 2, 3, 4, 6},
        e {4, 8, 6, 2, 1, 5, 0, 3};

    assert( !d.shares_edge(b) );
    assert(  a.shares_edge(b) );
    assert(  a.shares_edge(c) );
    assert(  a.shares_edge(e) );

    return 0;
}

Wie Sie sehen können, führt diese zusätzliche Abstraktion zu einer recht ansprechenden Implementierung von shares_edge(), aber das liegt daran, dass der eigentliche Trick in der Definition der Klasse Edge liegt (bzw. genauer gesagt in der Beziehung, dass e1 == e2 <=> Edge::hash(e1) == Edge::hash(e2)).

Answer 3

Zuerst schreiben Sie eine make_paired_range_view, die einen Bereich nimmt und einen Bereich zurückgibt, dessen Iteratoren std::tie(*it, *std::next(it)) zurückgeben. boost kann hier helfen, da ihr Iterator-Schreibcode dies viel weniger ärgerlich macht.

Dann nimmt unordered_equal zwei pairs und vergleicht sie, wobei die Reihenfolge ignoriert wird (sie sind gleich, wenn das erste sowohl gleich ist und das zweite auch, oder wenn das erste das andere zweite und umgekehrt gleich ist).

Jetzt suchen wir jedes Paar auf der linken Seite im rechten Bereich unter Verwendung von unordered_equal.

Dies hat den Vorteil, dass kein zusätzlicher Speicherplatz benötigt wird, aber den Nachteil, dass die Zeit O(n^2) beträgt.

Wenn uns die Zeit mehr am Herzen liegt als der Speicherplatz, können wir stattdessen die obigen pairs in ein unordered_set stecken, nachdem wir die pairs in eine kanonische Reihenfolge sortiert haben. Anschließend gehen wir durch den zweiten Container und prüfen jedes Paar (nach der Sortierung), um zu sehen, ob es im unordered_set vorhanden ist. Dies erfordert O(n) zusätzlichen Speicherplatz, läuft jedoch in O(n) Zeit ab. Es kann auch ohne schicke Vektor- und Bereichsschreibweise durchgeführt werden.

Wenn die Elemente teurer sind als int, können Sie ein benutzerdefiniertes pseudo_pair schreiben, das Zeiger enthält und dessen Hash- und Gleichheit auf dem Inhalt der Zeiger basiert.

Answer 4

Ein interessantes "Wie würdest du es machen..." Problem... :-) Es hat mich dazu gebracht, eine 15-minütige Pause einzulegen, um nicht nur Textfelder und Kombinationsfelder auf Formularen einzutragen, sondern auch ein wenig zu programmieren... LOL

Also, hier ist, wie ich denke, dass ich es machen würde...

Zuerst würde ich ein Konzept einer Kante als ein Paar von Werten definieren (Paar von Ganzzahlen - gemäß deinem ursprünglichen Beispiel). Mir ist klar, dass dein Beispiel nur eine Vereinfachung ist und du tatsächlich Vektoren deiner eigenen Klassen verwendest (Point* anstelle von int?) aber es sollte trivial sein, diesen Code zu templatisieren und jeden gewünschten Typ zu verwenden...

#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef pair edge;

Dann würde ich eine Set-Klasse erstellen, die ihre Elemente (Kanten) auf die benötigte Weise geordnet hält (indem sie Kanten in einer ordnungsinsensitiven Weise vergleicht - d.h. wenn e1.first==e2.first und e1.second==e2.second, dann sind Kanten e1 und e2 identisch, aber sie sind auch identisch, wenn e1.first==e2.second und e1.second==e2.first). Dafür könnten wir ein Funktional erstellen:

struct order_insensitive_pair_less
{
    bool operator() (const edge& e1, const edge& e2) const
    {
        if(min(e1.first,e1.second)min(e2.first,e2.second)) return false;
        else return(max(e1.first,e1.second)

`

Zuletzt wäre unsere Hilfsklasse (nennen wir sie edge_set) einfach eine Ableitung eines Sets, das mit dem obigen Funktional geordnet ist, mit ein paar zusätzlichen Bequemlichkeitsmethoden - einem Konstruktor, der das Set aus einem Vektor (oder deiner Face-Klasse in der Praxis) bevölkert, und einer Testfunktion (bool shares_edge(const vector&v)), die uns sagt, ob das Set eine Kante mit einer anderen teilt. Also:

struct edge_set : public set
{
    edge_set(const vector&v);
    bool shares_edge(const vector&v);
};

Implementiert als:

edge_set::edge_set(const std::vector&v) : set()
{
    if(v.size()<2) return; // annehmen, dass mindestens 2 Elemente im Vektor sein müssen, da es eine Liste von Kanten sein soll...
    for (std::vector::const_iterator it = v.begin()+1; it != v.end(); it++)
        insert(edge(*(it-1), *it));
}

bool edge_set::shares_edge(const std::vector& v)
{
    edge_set es(v);
    for(iterator es_it = begin(); es_it != end(); es_it++)
        if(es.count(*es_it))
            return true;
    return false;
}

Die Verwendung wird dann trivial (und relativ elegant). Angenommen, du hast die beiden Vektoren, die du als Beispiele im Abstrakt deines Problems in den Variablen v1 und v2 gegeben hast, um zu testen, ob sie eine Kante teilen, würdest du einfach schreiben:

if(edge_set(v1).shares_edge(v2))
    // Ja, sie teilen eine Kante, mach etwas damit...
else
    // Nein, nicht diese beiden... Mach etwas anderes...

Die einzige Annahme über die Anzahl der Elemente in diesem Ansatz ist, dass jeder Vektor mindestens 2 Elemente haben wird (da du keine "Kante" ohne mindestens zwei Eckpunkte haben kannst). Jedoch, auch wenn dies nicht der Fall ist (einer der Vektoren ist leer oder hat nur ein Element) - dies wird zu einem leeren edge_set führen, sodass du einfach die Antwort erhältst, dass sie keine gemeinsamen Kanten haben (da eines der Sets leer ist). Kein großes Problem... Meiner Meinung nach würde es auf diese Weise sicherlich den "Zwei-Wochen-Test" bestehen, da du eine dedizierte Klasse hast, in der du ein paar Kommentarzeilen haben könntest, um zu sagen, was sie tut, und der eigentliche Vergleich ist ziemlich lesbar (edge_set(v1).shares_edge(v2))...

`

Answer 5

Ich denke, das ist das kürzeste, was ich mir ausdenken kann.

bool check_for_pairs(std::vector A, std::vector B) {
  auto lastA = A.back();
  for (auto a : A) {
    auto lastB = B.back();
    for (auto b : B) {
      if ((b == a && lastB == lastA) || (b == lastA && lastB == a)) return true;
      lastB = b;
    }
    lastA = a;
  }
  return false;
}

Ein zeiteffizienterer Ansatz wäre die Verwendung eines Sets.

bool check_for_pairs2(std::vector A, std::vector B) {
  using pair = std::pair;
  std::unordered_set< pair, boost::hash > lookup;
  auto last = A.back();
  for (auto a : A) {
    lookup.insert(a < last ? std::make_pair(a,last) : std::make_pair(last,a));
    last = a;
  }
  last = B.back();
  for (auto b : B) {
    if (lookup.count(b < last ? std::make_pair(b,last) : std::make_pair(last,b)))
      return true;
    last = b;
  }
  return false;
}

Wenn Sie eine Hash-Funktion implementieren, die (a,b) und (b,a) auf denselben Wert hash, könnten Sie die Überprüfung entfernen, welcher Wert kleiner ist.