2d_circle_packing_mbc_1.cpp

// Algorithm is divided in 4 parts

// 1. Method for generating a mitchell best candidate
// PackedCircle is just a wrapper for a 2d point with a radius and the methods for drawing it
PackedCircle ofApp::getMitchellBestCandidate(){
    
    float greatestDistance = 0.0f;
    PackedCircle winningSample;
    // Init at (0,0) with radius of 0
    winningSample.setup(ofPoint(0,0), 0.0f);
    int k = 64;
    // Loop for k times, where k is the number of samples: the higher, the better
    for(int i = 0; i < k; i++){
        // Radius is fixed at 2. We're not interested in the radius now, since they're dots
        float radius = 2.0f;
        // Create a new random x,y point
        ofPoint position(ofRandom(ofGetWidth()), ofRandom(ofGetHeight()));
        PackedCircle candidate;
        candidate.setup(position, radius);
        
        float currentDistance;
        // If this is the first dot we're placing, return this as best candidate
        if(placedCircles.size() == 0) return candidate;
        
        // Start from the distance to the nearest placed sample
        currentDistance = getDistanceToNearestSample(candidate);
        // Find the greatest distance among all k samples
        if(currentDistance > greatestDistance){
            greatestDistance = currentDistance;
            winningSample = candidate;
        }
    }
    
    //cout << "Winning radius: " << winningSample.radius << endl;
    
    return winningSample;
}

// 2. Method for returning distance from sample and nearest already placed sample
float ofApp::getDistanceToNearestSample(PackedCircle candidate){
    
    float shortestDistance = 0.0f;
    
    // Loop into all samples
    for(int i = 0; i < placedCircles.size(); i++){
        PackedCircle otherSample = placedCircles[i];
        // Measure current distance between the two points 
        float currentDistance = candidate.pos.distance(otherSample.pos);
        // Get nearest sample (from previously placed ones)
        if(shortestDistance == 0.0f || currentDistance < shortestDistance){
            shortestDistance = currentDistance;
        }
    }
    return shortestDistance;
}

// 3. Method for placing and drawing samples to screen
void ofApp::placeNewSample(){
    
    // Generate new sample
    PackedCircle sample = getMitchellBestCandidate();
    // Add it to the list of samples
    placedCircles.push_back(sample);
    // Draw it
    ofFill();
    sample.draw(ofColor::black);
}


// 4. Actual code that starts the process
// fbo is just a framebuffer object used for drawing
fboBuffer.begin();
    
    ofClear(255);
    
    if(samplingMethod == MITCHELL_BEST_CANDIDATE){
        
        // USING MITCHELL'S BEST CANDIDATE
        // We want to have 30000 samples at the end
        while(placedCircles.size() < 30000){
            placeNewSample();
        }
        cout << "All samples placed!" << endl;
    }
    
fboBuffer.end();
    
// Log elapsed time
elapsedTimeMs = (ofGetElapsedTimeMillis() - startTime) / 1000;
cout << "Elapsed time: " << elapsedTimeMs << " seconds" << endl;