000
25.03.2017, 15:37 Uhr
Yadgar
|
Hi(gh)!
Nächstes Feature in yip: Paletten mit vorgegebener Farbenzahl berechnen (durchaus auch mal mehr als 256 Farben - bei Atari ST gibt es z. B. (inoffiziell) einen 512-Farben-Modus...), und zwar nach dem Medianschnitt-Verfahren.
Dazu müssen ja die einzelnen Pixel nach einer möglichst weit gespreizten Eigenschaft (ich verwende den Grauwert, da Fließkommawert und folglich in sehr viel mehr Ausprägungen als bloß 256 vorkommend) sortiert werden. Sortieren geht z. B. mit Quicksort, was den Vorteil hat, dass ich diesen Algorithmus vor gut zehn Jahren schon einmal implementiert hatte, damals allerdings in POV-Ray:
| Code: |
#macro sort(field, l, r) // QUICKSORT for PoV-Ray!
#local m=field[(l+r)/2][1];
#local i=l;
#local j=r;
#while(i<=j)
#while (field[i][1]<m) #local i=i+1; #end
#while (field[j][1]>m) #local j=j-1; #end
#if (i<=j)
#local buf=field[i][1];
#local buf2=field[i][0];
#declare field[i][1]=field[j][1];
#declare field[i][0]=field[j][0];
#declare field[j][1]=buf;
#declare field[j][0]=buf2;
#local i=i+1;
#local j=j-1;
#end
#end
#if (l<j) sort(Dists, l, j) #end
#if (i<r) sort(Dists, i, r) #end
#end
|
Das hat damals einwandfrei funktioniert (nämlich bei der Sortierung der eingeblendeten Entfernungen zu den Hauptstädten in meinem YouTube-Video "Earth Flight, version 0.2".
Beim Konvertieren nach C++:
| C++: |
void qsrt(vector<float> &gv, vector<pixel> &pxs, unsigned int l, unsigned int r)
{
cout << "qsrt..." << endl;
unsigned int median = gv[(l+r)/2];
unsigned int i=l, j=r;
float buf1;
pixel buf2;
while (i<=j)
{
while (gv[i] < median)
i++;
while (gv[j] > median)
j--;
if (i <= j)
{
buf1 = gv[i];
buf2 = pxs[i];
gv[i] = gv[j];
pxs[i] = pxs[j];
gv[j] = buf1;
pxs[j] = buf2;
i++;
j--;
}
}
if (l < j)
qsrt(gv, pxs, l, r);
if (i < r)
qsrt(gv, pxs, i, r);
}
|
muss ich allerdings irgendetwas falsch gemacht haben, denn das Programm läuft sich in einer Endlosschleife fest, i wird nie größer als j. Aber warum?
Bis bald im Khyberspace!
Yadgar
--
Flagmaker - ein Programmier-Blog |
