Voronoi algorithm

advanced
#1

Hi, I am developing some kind of real time detecting Voronoi diagram.

I found Voronoi algorithm here(https://rosettacode.org/wiki/Voronoi_diagram#C.2B.2B)

void ofApp::CreateSites() {
    int w = ofGetWidth(), h = ofGetHeight(), d;
    for (int hh = 0; hh < h; hh++) {
        for (int ww = 0; ww < w; ww++) {
            int ind = -1, dist = INT_MAX;
            for (size_t it = 0; it < points_.size(); it++) {
                ofPoint& p = points_[it];
                //d = DistanceSqrd(p, ww, hh);
                d = ofDist(p.x, p.y, ww, hh);
                if (d < dist) {
                    dist = d;
                    ind = it;
                }
            }
            
            if (ind > -1){
                ofPushMatrix();
                ofSetColor(colors_[ind]);
                ofDrawCircle(ww, hh, 1);
                ofPopMatrix();
            }
            
            //_pix.setColor(ww, hh, colors_[ind]);
            else
                __asm nop // should never happen!
                }
    }
}

and it works quite well, however the response time is too slow.

I think it’s because comparing all the pixels so it takes bunch of time.

Is there any algorithm that can be applied in order to reduce the response time?

thanks.

#2

Hey,

maybe you could try this addon -> https://github.com/madc/ofxVoronoi which calculates the voronoi pattern for you. It creates polygones, so it should be faster then drawing the pixels by hand.

#3

thanks! i will try!

#4

You could also use boost library for voronoi.
oF’s boost does not include it but you can download from boost website. I remember I only needed header files. Be careful to download same boost version with your oF.