Voronoi - ASCII-Art

Bei einem Voronoidiagramm, welches auch als Dirichlet-Zerlegung bezeichnet wird, handelt es sich um eine Darstellung eines endlichen Raumes, der in einzelne Regionen aufgeteilt wird. Jede Region kann einen oder mehrere Zentren besitzen. Dies variiert je nach Anwendungsfall. Die Größe der Regionen ist unabhängig von der Anzahl der Regionen und wird durch den Bezug zur euklidischen Metrik gebildet. Dies bedeutet, dass alle in der Region liegenden Punkte zu   keinem anderen Zentrum näher liegen, als zu seinem eigenen. Alle Punkte, welche die gleiche Distanz zu mehreren Zentren besitzen, werden als Grenzen bezeichnet.

Zur Bestimmung der Voronoi-Regionen wird die nächste Entfernung zweier Voronoi- Zentren durch nächst größere geteilt (best / good). Dies Zahl wird immer zwischen null und eins liegen. Punkte die nahe dem Zentrum sind haben fast den wert 0. Punkte nahe einer Kante haben fast den Wert eins. Was so viel bedeutet das sie fast genau soweit von zwei Punkten entfernt sind. Am Ende wird dieser Wert mit 10 multipliziert und in einen Integer gecastet. Diese Zahl ist dann der Index aus einem Array in dem alle für die Grafik zur Verfügung stehenden Zeichen abgelegt sind.

/* 
 * File:   main.cpp
 * Author: Thomas Rager
 *
 * Created on 17. Juni 2011, 21:19
 */

#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <time.h>
#include <math.h>

using namespace std;

/*
 *  Voronoi by Thomas Rager
 */

#define ROWS 50
#define COLS 130
#define POINT_COUNT 8

struct point{
    double x;
    double y;
};

point orgPoints[POINT_COUNT];
vector<point> points;
char chars[] = {‘.‘,‘,‘,‘-‘,‘+‘,‘*‘,
	‘$‘,‘&‘,‘#‘,‘@‘,‘~‘,‘~‘};
//char chars[] = {‘.‘,‘ ‘,‘ ‘,‘ ‘,‘ ‘,
	‘ ‘,‘ ‘,‘ ‘,‘ ‘,‘~‘,‘~‘};
string screen[ROWS] ="";

double xfact = 1.0 / ROWS;
double yfact = 1.0 / COLS;
static int randCount = 0;


void generateRandom(point &in){
    srand(time(NULL)+randCount);
    in.x =  (double) rand()/RAND_MAX;
    in.y =  (double) rand()/RAND_MAX;
    randCount++;
}

//xs und ys werden nicht benötigt da global
void closes(double x,double y,point &pointIn){
    double best = 99;
    double oldbest = 99;
    double good = 99;
    for(int i = 0; i < points.size(); i++){
       
        //ToDo
        double dist = sqrt(pow(x-points[i].x,2)+pow(y-points[i].y,2)); 

        if(dist < best){
            oldbest = best;
            best = dist;
            good = oldbest;
        }
        else if(dist < good){
            good = dist;
        }
    }
    //eventuell neues struct wegen besserer benamung...
    //cout << x << " " << y << " "<< best << " " << good << "\n";
    pointIn.x = best;
    pointIn.y = good;
}

int main(int argc, char** argv) {

    cout << "ragersVoronoi - www.ragersweb.de\n";
    cout << "================================\n\n";

    cout << "Punkte (x,y)\n";
    cout << "============\n\n";

    for(int i = 0 ; i < POINT_COUNT;  i++ ){
        point pointVal;
        generateRandom(pointVal);
        orgPoints[i].x = pointVal.x;
        orgPoints[i].y = pointVal.y;

        cout << "(" << setprecision(6) << pointVal.x << "," 
        << setprecision(6) << pointVal.y << ")\n";

        for(int xoff =  -1; xoff < 2; xoff++){
            for(int yoff =  -1; yoff < 2; yoff++){
                pointVal.x = orgPoints[i].x;
                pointVal.y = orgPoints[i].y;
                pointVal.x = pointVal.x + xoff;
                pointVal.y = pointVal.y + yoff;
                
                points.push_back(pointVal);
            }
        }
    }

    //initialisieren des screens
    for(int i = 0; i < ROWS; i++){
        screen[i] = " ";
    }

    //bild generieren
    double x;
    double y;
    double best;
    double good;
    point temp;

    for(int i = 0; i < ROWS; i++){
        x = i*xfact;
        for(int j = 0; j < COLS; j++){
           y = j * yfact;
           closes(x,y,temp);

           best = temp.x;
           good = temp.y;

           int myChar = (int) (10.0 * best / good);
           screen[i] = screen[i] + chars[myChar];
        }
    }

    //bild ausgeben
    cout << "\nAusgabe\n";
    cout << "=======\n\n";
    for(int i = 0; i < ROWS; i++){
        cout << screen[i] << "\n";
    }
    cout << "\n";

    return 0;
}