Voronoi algorithm


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){
                ofDrawCircle(ww, hh, 1);
            //_pix.setColor(ww, hh, colors_[ind]);
                __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?




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.


thanks! i will try!


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.