Removing items from vector

Hi all,

I’m trying to port a program I used in processing over to oF. The original program used an arrayList to store and remove elements as the program traversed across the pixel array. Since arrayList is not an option in c++ I decided to use a vector to store my data. The program generates a “seed” pixel and then expands outwards coloring each pixel it comes across with a noise function. As it moves outwards it is supposed to remove the pixels that it has already colored to speed up performance, and so that it isn’t just running over the same colors over and over again (preventing overlap). However, I’m having trouble figuring out how to properly remove my traversed pixels from the vector.

I tried doing

  
  
std::remove(traversed.begin(), traversed.end(), i);  
  

and

  
  
if(traversed[i] == true){  
  seeds.erase(seeds.begin()+i);  
}  
  

but neither are working. I also briefly tried to use ofRemove, but I’m a little confused about how to implement the boolean function in this instance.

Here is what I’ve got:

.h

  
  
#pragma once  
  
#include "ofMain.h"  
  
class testApp : public ofBaseApp{  
  
	public:  
		void setup();  
		void update();  
                void updateSeeds();  
		void draw();  
  
		void keyPressed  (int key);  
		void keyReleased(int key);  
		void mouseMoved(int x, int y );  
		void mouseDragged(int x, int y, int button);  
		void mousePressed(int x, int y, int button);  
		void mouseReleased(int x, int y, int button);  
		void windowResized(int w, int h);  
		void dragEvent(ofDragInfo dragInfo);  
		void gotMessage(ofMessage msg);  
		  
    vector<int> seeds;  
    vector<bool> traversed;  
  
    int step, steps, w, h, numRandSeeds;  
    bool finishIt;  
      
    ofImage screen;  
    ofPixels pix;  
    ofColor c;  
    unsigned char * pixels;   
};  
  

.cpp

  
  
#include "testApp.h"  
  
//--------------------------------------------------------------  
void testApp::setup(){  
    w = 500;  
    h = 500;  
      
    ofSetWindowShape(w, h);  
      
    finishIt = false;  
    numRandSeeds = 3;  
    step = 0;  
    steps = 10000;  
    traversed.resize(w*h);  
}  
  
//--------------------------------------------------------------  
void testApp::update(){  
      
}  
  
//--------------------------------------------------------------  
void testApp::draw(){  
    ofPushStyle();  
    ofSetColor(255, 255, 255);  
    ofRect(0, 0, w, h);  
    ofPopStyle();  
      
    screen.grabScreen(0, 0, w, h);  
      
      
    if(step == 0){  
        cout<<"finding edges"<<endl;  
          
        for(int i = 0; i<numRandSeeds; i++){  
            int seed = int(ofRandom(w*h));  
            seeds.push_back(seed);  
            traversed[seed] = true;  
        }  
    }  
    else{  
        updateSeeds();  
    }  
      
    if(step < steps){  
        step++;  
        cout<<ofToString(step)+"/"+ofToString(steps)<<endl;  
        screen.update();  
    }  
      
    else{  
        cout<<"done"<<endl;  
    }  
    screen.draw(0,0);  
}  
  
//--------------------------------------------------------------  
void testApp::updateSeeds(){  
      
    float xOff = 0.0;  
    float zOff = 0.0;  
      
    for(int i = seeds.size()-1; i>=0; i--){  
        float yOff = 0.0;  
          
        int x = seeds[i] % w;  
        int y = seeds[i] / w;  
          
        int r = ofNoise(zOff,xOff,yOff)*255; //red      
        int g = ofNoise(xOff,yOff,zOff)*255; //green      
        int b = ofNoise(yOff,zOff,yOff)*255; //blue  
  
        int n = int(abs(ofNoise(zOff))*ofRandom(ofGetFrameNum()*0.009)*3.141592);  
        c = ofColor(r,g,b);  
          
        screen.setColor(x, y, c);  
          
        //---------Up, Right, Down, Left  
        int upIndex = seeds[i] - w;  
        if(y>0 && !traversed[upIndex]){  
            seeds.push_back(upIndex);  
            traversed[upIndex] = true;  
        }  
          
        int rightIndex = seeds[i] +1;  
        if(x<w-1 && !traversed[rightIndex]){  
            seeds.push_back(rightIndex);  
            traversed[rightIndex] = true;  
        }  
          
        int downIndex = seeds[i] + w;  
        if(y<h-1 && !traversed[downIndex]){  
            seeds.push_back(downIndex);  
            traversed[downIndex] = true;  
        }  
          
        int leftIndex = seeds[i] - 1;  
        if(x > 0 && !traversed[leftIndex]){  
            seeds.push_back(leftIndex);  
            traversed[leftIndex] = true;  
        }  
          
         /*  
        //---------Upper Left, Upper Right, Lower Left, Lower Right   
        int ulIndex = seeds[i] - w-1;  
        if(x>0 && y>0 && !traversed[ulIndex]){  
            seeds.push_back(ulIndex);  
            traversed[ulIndex] = true;  
        }  
          
        int urIndex = seeds[i] - w+1;  
        if( y>0 && !traversed[urIndex]){  
            seeds.push_back(urIndex);  
            traversed[urIndex] = true;  
        }  
          
        int llIndex = seeds[i] + w-1;  
        if(y< h-1 && !traversed[llIndex]){  
            seeds.push_back(llIndex);  
            traversed[llIndex] = true;  
        }  
          
        int lrIndex = seeds[i] + w+1;  
        if(x< w-1 && y< h-1 && !traversed[lrIndex]){  
            seeds.push_back(lrIndex);  
            traversed[lrIndex] = true;  
        }  
        */  
          
        xOff +=0.00001;  
        yOff +=0.000009;  
        //std::remove(traversed.begin(), traversed.end(), i);  
          
        if(traversed[i] == true){  
        seeds.erase(seeds.begin()+i);  
        }  
          
    }  
    zOff +=0.1;  
      
}  
  

As an aside this is a tweaked version of Jeff Thompson’s seed sorting program with the sorting and edge detection and supplied image removed.
https://github.com/jeffThompson/PixelSorting/tree/master/SeedSorting

So, how do I drop those traversed pixels out of the vector? I looked into using an iterator to move through the vector as well but I wasn’t sure if I was barking up the right tree there either.

Thanks in advance for the help!

the problem is that if you remove element i then the next iteration of the loop will be pointing to the original i+2 instead of i+1 so when you delete an element you just need to decrement i by 1

Thanks for the reply Arturo!

So you are saying that I can just include the i-- in here? I gave this a shot, and it seems to do something, but it’s definitely not right. The pixels expand to the wrong neighbors at a certain point and then it just devolves into craziness.

Is this even the right way to be removing from the vector?

  
  
        if(traversed[i] == true){  
        seeds.erase(seeds.begin()+i);  
            i--;  
        }  
  

Just reporting back. I actually figured it out, I think I was initially mis-diagnosing my problem. I ended up changing my boolean values from a vector to an array.

in .h I changed

  
vector<bool> traversed   

to

  
bool* traversed;  

in testapp.cpp I changed

  
traversed.resize(w*h);  

to

  
traversed = new bool[w*h];  

and then at the end where I was asking about removing items from the vector it just ended up being

  
seeds.erase(seeds.begin()+i);  

without if statement and the i–; that arturo suggested.

Seems to be working great now, and a whole lot faster than the version I was using in processing!

Hi,
If you don’t need random access to “seed” and always iterate from begin to end, I think the best solution is to use a http://www.cplusplus.com/reference/forward-list/forward-list/"">forward_list. This container is designed for quick insert/remove operations. Faster than vector and array. I think it can really improve the perfomances.