Playing with path optimization ideas.

main.cpp

#include "ofMain.h"
#include "ofxCv.h"

class ofApp : public ofBaseApp {
public:
    void setup() {
        bestDiff = 0;
        swaps = 64 * 64;
        n = 32;
        for(int y = 0; y < n; y++) {
            for(int x = 0; x < n; x++) {
                float a = sin(ofMap(x, 0, n - 1, 0, PI));
                float b = sin(ofMap(y, 0, n - 1, 0, PI));
                sensitivity.push_back(a * b);
            }
        }
        n2 = n * n;
        dir.open("src");
        dir.listDir();
        all.assign(dir.size(), vector<int>(n2));
        for(int i = 0; i < dir.size(); i++) {
            ofImage cur(dir.getPath(i));
            cur.resize(n, n);
            cur.setImageType(OF_IMAGE_GRAYSCALE);
            unsigned char* pixels = cur.getPixels();
            for(int j = 0; j < n2; j++) {
                all[i][j] = pixels[j];
            }
            ids.push_back(dir[i]);
        }
        
        img.allocate(n2, dir.size(), OF_IMAGE_GRAYSCALE);
    }
    
    void sort() {
        sort(0, all.size());
    }
    
    void sort(int start, int end) {
        for(int i = start; i < end - 1; i++) {
            int bestDiff = 0;
            int bestIndex = 0;
            for(int j = i + 1; j < end; j++) {
                int curDiff = dist(i, j);
                if(bestDiff == 0 || curDiff < bestDiff) {
                    bestDiff = curDiff;
                    bestIndex = j;
                }
            }
            swap(all[i + 1], all[bestIndex]);
            swap(ids[i + 1], ids[bestIndex]);
        }
    }
    
    void randomSwap() {
        for(int i = 0; i < swaps; i++) {
            int x = ofRandom(1, all.size() - 2);
            int y = ofClamp(x + ofRandom(-8, +8), 1, all.size() - 2);
            //        int y = ofRandom(1, all.size() - 2);
            
            int xl = x-1, xr = x+1;
            int yl = y-1, yr = y+1;
            
            int curCost = dist(x, xl) + dist(x, xr) + dist(y, yl) + dist(y, yr);
            int swaCost = dist(y, xl) + dist(y, xr) + dist(x, yl) + dist(x, yr);
            if(swaCost < curCost) {
                swap(all[x], all[y]);
                swap(ids[x], ids[y]);
            }
        }
    }
    
    void reverse() {
        std::reverse(ids.begin(), ids.end());
        std::reverse(all.begin(), all.end());
    }
    
    void rotate(int steps) {
        std::rotate(ids.begin(), ids.begin()+steps, ids.end());
        std::rotate(all.begin(), all.begin()+steps, all.end());
    }
    
    void update() {
        /*
         surprisingly, using randomSwap doesn't fare better than using the naive
         "sorting" (iterative nearest neighbor) approach... tsp is rough.
         */
        
        // best nn starting point is good
        int pivot = ofGetFrameNum() % all.size();
        rotate(pivot);
        sort();
        
        // not bad if descent constraint is commented out
//        rotate(10);
//        sort(0, 100);
        
        // experimental
//        rotate(2);
//        int step = 100;
//        for(int i = 0; i + step < all.size(); i+=step) {
//            sort(i, i + step);
//        }
        
        // very slow
//        randomSwap();
        
        int totalDiff = 0;
        for(int i = 0; i < all.size() - 1; i++) {
            totalDiff += dist(i, i + 1);
        }
        if(totalDiff < bestDiff || bestDiff == 0)
        {
            best = all;
            bestIds = ids;
            bestDiff = totalDiff;
            
            for(int y = 0; y < all.size(); y++) {
                for(int x = 0; x < n2; x++) {
                    img.getPixels()[y * n2 + x] = all[y][x];
                }
            }
            
            img.update();
        }
        else {
            // could swap
            all = best;
            ids = bestIds;
        }
    }
    
    void draw() {
        img.draw(0, 0);
        ofDrawBitmapStringHighlight(ofToString(bestDiff) + " " + ofToString(ofGetFrameNum()), 10, 20);
    }
    
    void keyPressed(int key) {
        if(key == 's') {
            for(int i = 0; i < bestIds.size(); i++) {
                bestIds[i].copyTo("out/" + ofToString(i, 4, '0') + ".tiff", true, true);
            }
        }
    }
    
    ofDirectory dir;
    vector< vector<int> > all, best;
    vector< ofFile > ids, bestIds;
    ofImage img;
    int n, n2;
    int swaps;
    int bestDiff;
    
    vector<float> sensitivity;
    float dist(int i, int j) {
        float diff = 0;
        for(int k = 0; k < n2; k++) {
            float cur = all[i][k] - all[j][k];
            cur *= sensitivity[k];
            diff += cur > 0 ? cur : -cur;
        }
        return diff;
    }
};


int main() {
	ofSetupOpenGL(800, 800, OF_WINDOW);
	ofRunApp(new ofApp());
}