3. vector-Elemente iterieren und löschen

vector-Elemente iterieren und löschen

  • W

    @ dot:

    // CLASS RECTANGLE
class Rectangle
{
public:
	Rectangle() : x(0), y(0), width(0), height(0) {}
	Rectangle(int x_, int y_, int w, int h) : x(x_), y(y_), width(w), height(h) {}
	bool intersects(const Rectangle& other);
	bool includes_point(int px, int py);
private:
	int x;
	int y;
	int width;
	int height;
};

bool Rectangle::intersects(const Rectangle& other)
{
	if (includes_point(other.x, other.y)) return true;
	if (includes_point(other.x + other.width, other.y)) return true;
	if (includes_point(other.x, other.y + other.height)) return true;
	if (includes_point(other.x + other.width, other.y + other.height)) return true;
	if ((x < other.x) && (x+width > other.x+other.width) && (y > other.y) && (y+height < other.y+other.height)) return true;
	if ((x > other.x) && (x+width < other.x+other.width) && (y < other.y) && (y+height > other.y+other.height)) return true;
	if ((x < other.x) && (x+width > other.x+other.width) && (y < other.y) && (y+height > other.y+other.height)) return true;
	return false;
}

bool Rectangle::includes_point(int px, int py)
{
	return (px > x) && (px < x+width) && (py > y) && (py < y+height);
}
// END CLASS

// Lösche jedes Rechteck, dass sich mit einem anderen überschneidet
void delete_intersecting_rects(vector<Rectangle>& vec)
{
	for (vector<Rectangle>::iterator iter1 = vec.begin(); iter1 != vec.end(); ++iter1)
	{
		for (vector<Rectangle>::iterator iter2 = vec.begin(); iter2 != vec.end(); ++iter2)
		{
			if (iter1 == iter2)
				continue;
			if (iter1->intersects(*iter2))
			{
				iter1 = vec.erase(iter1);
				break;
			}
		}
	}
}

    @ DocShoe: remove_if braucht aber eine Funktion, die genau ein Element als Parameter hat. Meine braucht aber ein Element und den Vektor.

    0

  • Ok, da stellt sich nun natürlich die Frage mit wievielen Rechtecken du es da zu tun hast und ob es Performancemäßig ein Problem gibt.

    Der Bug in dem Code ist übrigens: Im Fall von einem erase() darfst du iter1 natürlich nicht inkrementieren...

    0
  • W

    Ok, da stellt sich nun natürlich die Frage mit wievielen Rechtecken du es da zu tun hast und ob es Performancemäßig ein Problem gibt.

    Weiß nicht, vielleicht 50. Wäre aber auch nicht uninteressiert an einer performanten Lösung für ganz viele Rechtecke 🙂

    0

  • Naja, die beste Lösung wär, von vornherein keine sich überlappenden Rechtecke zu erzeugen.

    Abgesehen davon: Eine effiziente Lösung für sehr viele Dreiecke würde sich irgendeine Beschleunigungsstruktur zu Nutze machen. Man könnte z.B. alle Rechtecke in ein Grid einsortiert halten, um dann beim Testen nicht immer alle anderen Rechtecke überprüfen zu müssen, sondern nur die, die das aktuelle Rechteck auch wirklich potentiell schneiden.
    Statt vector::erase() wäre es vermutlich effizienter std::remove_if() zu verwenden, denn bei einem erase() muss immer alles was hinter dem gelöschten Element liegt nach vorne kopiert werden.

    Aber wenn du nur so 50 Rechtecke hast, dann wird die Performance sowieso eher kein Problem sein 😉

    0
  • W

    Die Sache mit dem Grid verstehe ich nicht.

    Ob ich nun erase oder remove_if verwende ist ja egal, denn funktionieren tut es trotzdem nicht.

    0

  • Wurstinator schrieb:

    @ DocShoe: remove_if braucht aber eine Funktion, die genau ein Element als Parameter hat. Meine braucht aber ein Element und den Vektor.

    Nö. remove_if kann auch mit Funktoren arbeiten, die einen internen Status besitzen (und damit z.B. deinen Vektor):

    struct MyPredicate : std::unary_function<Rectangle,bool>
{
   std::vector<Rectangle>& Data_;

   MyPredicate( std::vector<Rectangle>& v ) : Data_( v )
   {
   }

   bool operator()( const Rectangle& r ) const
   {
      // auf Überschneidung testen
   }
};

    Das Dumme ist nur, dass du für das aktuelle Rechteck dessen Position im Vektor nicht mehr kennst, d.h. du müsstest erst die Position feststellen und dann mit den nachfolgenden Rechtecken auf Überschneidung testen.

    0
  • T

    Wieso fügst Du überlappende Rechtecke überhaupt in den Vektor ein, wenn Du sie nicht drin haben willst? Du kannst doch vor ein Einfügen z.B. mit find_if prüfen, ob das einzufügende Rechteck mit anderen überlappt, und es dann gar nciht erst einfügen.

    0
  • W

    @ DocShoe: Okay, das wusste ich nicht. Trotzdem entfernt remove_if nur das erste überlappende Rechteck (oder die ersten, wenn sich mehrere an einer Stelle überlappen) und nicht das letzte.

    @ Tachyon: Vielleicht brauche ich vorher alle Rechtecke und später nur noch die, die sich nicht überlappen. Vielleicht verändern sie sich, nachdem sie eingefügt wurden.

    0
  • W

    push

    0
  • K

    Vielleicht solltest Du ein neues Thema aufmachen, dessen Titel auch etwas mit Deinem aktuellen Problem zu tun hat. Wenn ich mir nämlich hier Deinen ersten Beitrag durchlese, schreit das ganz einfach nach einer Antwort a la "Benutze erase-remove_if". Ich habe zumindest keine Lust, zu suchen, wo Deine aktuelle Frage steht und worum es eigentlich geht...

    0
  • W

    Der Titel passt und das Problem ist das selbe wie am Anfang.

    Da die Frage scheinbar nicht ganz klar war, habe ich den Startpost jetzt noch etwas erweitert.

    0
  • ?

    Is das ne blöde Idee?

    void delete_intersecting_rects(vector<Rectangle>& vec)
{
    vector<bool> intersects;
    bool intersectTmp;
    for (vector<Rectangle>::iterator iter1 = vec.begin(); iter1 != vec.end(); ++iter1)
    {
        intersectTmp = false;
        for (vector<Rectangle>::iterator iter2 = vec.begin(); iter2 != vec.end(); ++iter2)
        {
            if(iter1==iter2) {
                continue;
            }
            if (iter1->intersects(*iter2))
            {
                intersectTmp = true;
                break;
            }
        }
        intersects.push_back(intersectTmp);
    }
    int position = intersects.size() -1 ;
    for(vector<bool>::reverse_iterator ri = intersects.rbegin(); ri != intersects.end(); ++ri, --position)
    { //von hinten löschen, damit vorne die positionierung nicht verkackt weil der rest nachrutscht
        if(*ri)
        {
            vec.erase(vec.begin()+position);
        }
    }
}

    Bin grad a bißerl müde und unkonzentriert, also verzeih falls ich da grad nen fundamentalen fehler mache, aber so sollts zumindest gehen. Die Prüfung am Anfang kann man noch optimieren, weil man jedes paar doppelt prüft - aber zufaul drüber gedanken zu machen.

    0
  • W

    Hm, ich hatte die Idee, einen vector<size_type> zu erstellen, mit dem die Indexe der zu löschenden Elemente gespeichert werden. Deine vector<bool>-Idee gefällt mir besser, aber ich find es trotzdem nicht so toll, wenn man einen neuen vector dafür erstellen muss.
    Vielleicht kennt ja jemand eine noch bessere Lösung 🙂

    0
Anmelden zum Antworten