Löschen von Duplikaten aus Vektor

bekinect

Ich hab einen Vector intersects. Dieser speichert mir die Koordinaten von Schnittpunkten. Bei der Berechnung der Schnittpunkte kommt es dazu, dass der selbe Punkt mehrmals gefunden wird. Daher will ich die Duplikate aus meinem Vektor löschen. Hier einmal mein Code:

std::vector<std::array<double, 3>> intersects;

std::sort(intersects.begin(), intersects.end(), sorting_intersects);
std::set<array<double, 3>> set2(intersects.begin(), intersects.end());

intersects.erase(std::remove_if(intersects.begin(), intersects.end(), [&set2] (array<double, 3> item2) {return !set2.erase(item2); }), intersects.end());

Mit diesem Code werden aber nicht alle Duplikate entfernt. Stattdessen werden nur einige Duplikate entfernt, andere bleiben stehen.
Probiert hab ich auch dies:

bool myfunction (const std::array<double, 3>& s1, const std::array<double, 3>& s2) {
  return ((s1[0]==s2[0]) && (s1[1]==s2[1]) && (s1[2]==s2[2]));
}

intersects.erase(std::unique(intersects.begin(), intersects.end(), myfunction), intersects.end());

Ich finde einfach den Grund nicht wieso nur bestimmte Duplikate entfernt werden und andere nicht.

double-double-Vergleich.
Lasse Dir die Koordinaten der Schnittpunkte, die übrig bleiben, obwohl Du sie für gleich hältst, mit precision(15) ausgeben.

Wenn du keine Duplikate haben willst und den vector eh nachträglich sortierst, warum gehst du dann den Weg über

Schnittpunkte in vector speichern
-> set erzeugen
-> elemente aus vector löschen

statt einfach:
Schnittpunkte in Set speichern
-> ggf. set in vector speichern

Dein erase-remove_if ist hat außerdem ein Problem, wenn du einen Schnittpunkt mehr als 2x findest. Es wird nur maximal einer gelöscht. Angenommen, du findest den Punkt 10x, dann wird er nach dem Löschen noch 9x drin sein.

(und zu double und == wurde ja schon was geschrieben)

ja wenn du doubles vergleichen willst, musst du die differenz mit einem bestimmten wert vergleichen, z.b. <=0.001, je nach dem, wie genau es sein soll.

bekinect

Ich danke euch für eure Tipps.

@wob: Das vorgestellte Vorgehen habe ich so bereits in anderen Foren gefunden und auf mein Programm angewendet. Bei einem anderen Vektor funktioniert dieses Vorgehen, darum wundert es mich ja, dass es bei intersects nicht funktioniert.

@Kenner von double: Ich verwende zwar double werte die sind aber auf zwei Nachkommastellen gerundet. Und wenn ich mir die Werte ausgeben lasse stimmen sie überein. Das wurmt mich ja so, dass es hier dann zu solchen Fehlern kommt.

bei printf unterscheidet sich die ausgabe z.t. sehr stark von dem, was eigentlich ausgegeben werden müsste. keine ahnung, wie das bei cout ist.
jedenfalls hast du bei fließkommazahlen immer eine gewisse ungenauigkeit.

richtig vergleichen (natürlich nur zum debugging) kannst du deine zahlen mit so etwas:

double f = doublewert;
char *p;

p=(char*) &f;

for(int j=0;j<8;j++)
{
for(int i=0;i<8;i++)
{
cout<<((*p>>8-i)&1);
}
p++;
}

damit gibst du den wert der double richtig binär aus und auf dieser basis findet der vergleich ja statt.

ansonsten evtl. long long int mit separat gespeicherter zahl der nachkommastellen verwenden? vermutlich wird dann auch schneller gerechnet.

edit: j muss auch auf <8 geprüft werden.

firefly

bekinect schrieb:

@Kenner von double: Ich verwende zwar double werte die sind aber auf zwei Nachkommastellen gerundet. Und wenn ich mir die Werte ausgeben lasse stimmen sie überein. Das wurmt mich ja so, dass es hier dann zu solchen Fehlern kommt.

Sicher das sie damit 100% identisch sind? (bezogen auf "gleiche" Werte)
Wie schon Kenner von double sagte, gib mal die werte mit precision(15) aus, dann wird eventuell klar wiso der test doch fehlschlägt.

bekinect

@firefly: Precision(15) habe ich verwendet, zusätzlich lasse ich die Werte in ein csv-file schreiben, da ich sie so ablegen muss. In diesem File hab ich auch andere Werte mit mehr Nachkommastellen, für die Werte aus intersect reichen aber zwei Nachkommastellen aus. Darum runde ich die Werte auch bevor ich nach Duplikaten suche.

Hier einmal mein Code zum runden:

for(size_t b=0; b<intersects.size(); b++)
{
  intersects[b][0]=intersects[b][0]*10;
  intersects[b][1]=intersects[b][1]*10;
  intersects[b][2]=intersects[b][2]*10;
  intersects[b][0]=ceil(intersects[b][0]);
  intersects[b][1]=ceil(intersects[b][1]);
  intersects[b][2]=ceil(intersects[b][2]);
  intersects[b][0]=intersects[b][0]/10;
  intersects[b][1]=intersects[b][1]/10;
  intersects[b][2]=intersects[b][2]/10;			}

Wenn ich mir unter Verwendung dieses Codes die Werte ausgeben lasse, finde ich manuell auf anhieb fünf paare von Duplikaten in meinen Testwerten.

also sind die werte nach dem runden alle gleich und das programm denkt trotzdem, dass sie unterschiedlich sind?

Dann mach doch einfach mal ein lauffähiges Beispiel, damit wir das nachvollziehen können, d.h. mach doch mal einen Testcase, der fehlschlägt.

Also schreib:

#hier die includes
int main() {
  vector<array<double, 3>> testwerte = { ... };
  code;
  ausgabe;
}

Bitte so, dass wir den Fehler sehen können.

Zwei Vorschläge:

1. eine Template Klasse (z.B. "Vec3") erstellen, die einen Punkt im 3D Koordinatensystem darstellt, und die ganzen Operationen dafür definieren.

using Vec3 = std::array<double, 3>;

bool are_equal(const Vec3& a, const Vec3& b)
{
    static constexpr double precision {0.001};
    for (int i=0; i!=3; ++i) {
        if (std::abs(a[i]-b[i]) > precision) return false;
    }
    return true;
}

int main()
{
    using namespace std;

    vector<Vec3> intersects;
    // intersects füllen

    vector<Vec3> new_vec;

    unique_copy(intersects.begin(), intersects.end(), back_inserter(new_vec), are_equal);
}