Kmeans++ Color Quantization seeding.

So I was checking through a few color quantization algorithms and read the procedures needed for the Kmeans++ algorithm which is just Kmeans but it is initially seeded by finding maximally distinct colors from all previous color entries. And I was like hey, I totally already solved that problem!

http://godsnotwheregodsnot.blogspot.com/2012/09/color-distribution-methodology.html

In fact, I made a color dictionary of maximally distinct colors from all previous colors so to do the whole color quantization routine with an optimized initial seed, I can just feed it N digits of my lookup table that basically fits the gamut perfectly.

private static final String[] indexcolors = new String[]{

        "#000000", "#FFFF00", "#1CE6FF", "#FF34FF", "#FF4A46", "#008941", "#006FA6", "#A30059",

        "#FFDBE5", "#7A4900", "#0000A6", "#63FFAC", "#B79762", "#004D43", "#8FB0FF", "#997D87",

        "#5A0007", "#809693", "#FEFFE6", "#1B4400", "#4FC601", "#3B5DFF", "#4A3B53", "#FF2F80",

        "#61615A", "#BA0900", "#6B7900", "#00C2A0", "#FFAA92", "#FF90C9", "#B903AA", "#D16100",

        "#DDEFFF", "#000035", "#7B4F4B", "#A1C299", "#300018", "#0AA6D8", "#013349", "#00846F",

        "#372101", "#FFB500", "#C2FFED", "#A079BF", "#CC0744", "#C0B9B2", "#C2FF99", "#001E09",

        "#00489C", "#6F0062", "#0CBD66", "#EEC3FF", "#456D75", "#B77B68", "#7A87A1", "#788D66",

        "#885578", "#FAD09F", "#FF8A9A", "#D157A0", "#BEC459", "#456648", "#0086ED", "#886F4C",

        

        "#34362D", "#B4A8BD", "#00A6AA", "#452C2C", "#636375", "#A3C8C9", "#FF913F", "#938A81",

        "#575329", "#00FECF", "#B05B6F", "#8CD0FF", "#3B9700", "#04F757", "#C8A1A1", "#1E6E00",

        "#7900D7", "#A77500", "#6367A9", "#A05837", "#6B002C", "#772600", "#D790FF", "#9B9700",

        "#549E79", "#FFF69F", "#201625", "#72418F", "#BC23FF", "#99ADC0", "#3A2465", "#922329",

        "#5B4534", "#FDE8DC", "#404E55", "#0089A3", "#CB7E98", "#A4E804", "#324E72", "#6A3A4C",

        "#83AB58", "#001C1E", "#D1F7CE", "#004B28", "#C8D0F6", "#A3A489", "#806C66", "#222800",

        "#BF5650", "#E83000", "#66796D", "#DA007C", "#FF1A59", "#8ADBB4", "#1E0200", "#5B4E51",

        "#C895C5", "#320033", "#FF6832", "#66E1D3", "#CFCDAC", "#D0AC94", "#7ED379", "#012C58",

        

        "#7A7BFF", "#D68E01", "#353339", "#78AFA1", "#FEB2C6", "#75797C", "#837393", "#943A4D",

        "#B5F4FF", "#D2DCD5", "#9556BD", "#6A714A", "#001325", "#02525F", "#0AA3F7", "#E98176",

        "#DBD5DD", "#5EBCD1", "#3D4F44", "#7E6405", "#02684E", "#962B75", "#8D8546", "#9695C5",

        "#E773CE", "#D86A78", "#3E89BE", "#CA834E", "#518A87", "#5B113C", "#55813B", "#E704C4",

        "#00005F", "#A97399", "#4B8160", "#59738A", "#FF5DA7", "#F7C9BF", "#643127", "#513A01",

        "#6B94AA", "#51A058", "#A45B02", "#1D1702", "#E20027", "#E7AB63", "#4C6001", "#9C6966",

        "#64547B", "#97979E", "#006A66", "#391406", "#F4D749", "#0045D2", "#006C31", "#DDB6D0",

        "#7C6571", "#9FB2A4", "#00D891", "#15A08A", "#BC65E9", "#FFFFFE", "#C6DC99", "#203B3C",

        "#671190", "#6B3A64", "#F5E1FF", "#FFA0F2", "#CCAA35", "#374527", "#8BB400", "#797868",

        "#C6005A", "#3B000A", "#C86240", "#29607C", "#402334", "#7D5A44", "#CCB87C", "#B88183",

        "#AA5199", "#B5D6C3", "#A38469", "#9F94F0", "#A74571", "#B894A6", "#71BB8C", "#00B433",

        "#789EC9", "#6D80BA", "#953F00", "#5EFF03", "#E4FFFC", "#1BE177", "#BCB1E5", "#76912F",

        "#003109", "#0060CD", "#D20096", "#895563", "#29201D", "#5B3213", "#A76F42", "#89412E",

        "#1A3A2A", "#494B5A", "#A88C85", "#F4ABAA", "#A3F3AB", "#00C6C8", "#EA8B66", "#958A9F",

        "#BDC9D2", "#9FA064", "#BE4700", "#658188", "#83A485", "#453C23", "#47675D", "#3A3F00",

        "#061203", "#DFFB71", "#868E7E", "#98D058", "#6C8F7D", "#D7BFC2", "#3C3E6E", "#D83D66",

        

        "#2F5D9B", "#6C5E46", "#D25B88", "#5B656C", "#00B57F", "#545C46", "#866097", "#365D25",

        "#252F99", "#00CCFF", "#674E60", "#FC009C", "#92896B"

    };

Feminist Frequency: Ms. Male Character

The Joys of the Hookah

(I don't smoke but digitizing this)

THE JOYS OF THE HOOKAH*.

Though some may smoke segar, cheroot,
Or others' taste a pipe may suit,
They can't with thee the palm dispute,
                                             My Hookah.
When oft in boats I've been confin'd,
And ev'ry festive scene resigned,
Thou hast consol'd my drooping mind,
                                             My Hookah.
Whilst slow the pinnace seem'd to glide,
Along the Gunga's barren side,
What pleasing comfort thou supplied,
                                             My Hookah.
And when for weeks no change I've seen,
No fertile banks or meadows green,
With thee I've ne'er dejected been,
                                             My Hookah.
In gloomy jungles, where, alas!
No friend was near to quaff the glass,
Still did the hours contented pass,
                                             My Hookah.
And if the season bred disease,
From stagnant jeels or wither'd trees,
They smoke dispell'd the noxious breeze,
                                             My Hookah.
Expos'd to Sol's meridian power,
Or delug'd by the pelting shower,
Thou cheer'dst me in the gloomy hour,
                                             My Hookah.
In camps where oft untimely fell,
The valiant youth by fever's spell,
They fumes for ever kept me well,
                                             My Hookah.
From lengthen'd march the foe to meet,
Assail'd by thirst, expos'd to heat,
The conflict gain'd! I'd joyful greet
                                             My Hookah.
By arduous duty now deprest,
My strength exhausted, still no rest,
To me though then wert doubly blest,
                                             My Hookah.
Then as I sat beneath a tree,
If shade there haply chanc'd to be,
I seiz'd thy snake with extasy,
                                             My Hookah.
And now with evils still more trying,
To grieve for friends, departed, dying,
Alas! I often smok'd thee sighing,
                                             My Hookah.
The heart which can refuse a tear
For those who fall in war's career,
Can ne'er deserve thy envy'd cheer,
                                             My Hookah.
And if by chance in party dining,
Where conversation see'd declining,
I never thought of once repining,
                                             My Hookah.
But if that silence should be broke,
I did as others did, I spoke,
And then resumed thy snake to smoke,
                                             My Hookah.
Should lovely women deign partake,
A whiff or two for smoking's sake,
What odour would it give thy snake,
                                             My Hookah.
Not nectar would I wish to sip,
Allow'd that blest Munall to grip,
Which has been press'd by woman's lip,
                                             My Hookah.
If Hookahs can such pleasure give,
And smokers can such joys recieve,
Oh! let me smoke thee while I live,
                                             My Hookah.

Notes:
Verse
1st, "Cheroot," an Eastern name for segar.
3d, "Gunga." the native appellation for the Ganges,
5th, "Jungle", thick forests.
6th, "Jeel," large pools formed by the rains; and from their stagnant state, rendering the neighbourhood peculiarly unhealthy.
11th, "Snake," the name given to the long flexible tube which conveys the smoke.
17th "Munall," the part applied to the mouth; made of gold, silver, or agate,

Field Terrain Fractals

It occurs to me that treating fractals as fields that iterate from the previous and are solvable recursively for some subset so long as it doesn't diverge from the entire infinite field actually provides for not just a much better diamond squared fractal but rather for an infinite array of different types of fractals. There are basically only noise algorithms to do landscape like things, but if you take my algorithm and simply use it to recursively iterate the iterations within a limited scope you can produce a hell of a lot of different fractals.

Not to say they aren't useful, but most fractal iterations simply iterate and store the entire fractal in memory. To some extent that's not really needed. You could create a series of linear fractions say by starting by in infinite random field and then each iteration inserting the midpoint offset displacement just along the width. You'd get the 1d midpoint replacement fractal in infinite rows.  Or perhaps more useful you could apply say a box blur to a landscape, insert additional area with average random offset and repeat each iteration.

If (iteration == 5) {

     request sliver of the Iteration5 from iteration4 requested + 1 on each side,

     Apply a block blur (or frankly any convolution), and return the center bit that is accurately blurred.

}

You could likely produce pretty good landscape noise by inserting progressively less random additional points between all your current points and then applying a blur to all points. Even larger Gaussian blurs wouldn't be too difficult. In fact, there are some artifacts in diamond squared that cannot be fixed. Some points simply have different probability curves based on their location. If you always got the maximum possible random number every time, for a diamond squared field, you'll notice a *VERY* apparent pattern.

This typically blends into the noise and only matters for the standard deviation of the pattern. So long as they average at 0, it isn't very obvious (if you have run so that on average you deviate in some direction, it becomes apparent). It doesn't really have to be this way.

Field Diamond Squared Fractal Terrain Algorithm

The traditional Diamond Squared algorithm for generating fractal terrain has a number of constraints that make it really hard to use.

https://code.google.com/p/fractalterraingeneration/wiki/Diamond_Square
Gives a pretty good rundown of the cons:

* The map must be stored in memory, because pixels reference other pixels.
* Because it must be stored in memory, memory becomes a constraint. [...]
* The map must have a width and height of 2x + 1 pixels.
* Has 'creasing' artifacts if wrapping isn't used.
* Wrapping isn't always wanted.

I have solved all of these. And simplified the algorithm.


The traditional algorithm is that you set 4 corners to random values and wrap around the edges.

0 0
0 0


You double the height and width. Then each place you have four corners available to you, you insert the average of those corners and a slight random offset.

0   0
  1   1
0   0
  1   1

Due to the wrapping. You have four diamonds.

Then after all the diamond steps are done, you add in the square sections.

0 2 0 2
2 1 2 1
0 2 0 2
2 1 2 1

Keeping in mind it wraps around.


----

My solution is to simply view the base step as an infinite field of purely random values. This seems harder to conceptualize. But, it fixes the problems. You can't create an infinite field with twice the width as an infinite field. But, if you note, the next iteration doesn't require anything more than 1 away from the current iteration.

Even without any wrapping you can take:
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

And diverge.

0   0   0   0
  1 2 1 2 1
0 2 0 2 0 2 0
  1 2 1 2 1
0 2 0 2 0 2 0
  1 2 1 2 1
0   0   0   0

We went from a 4x4 to a 5x5. Next it goes to a 7x7 then a 11x11 then a (2n-3)x(2n-3)...

So we can simply reverse this with our well formed request.

If we want 1000x1000 block of data say at the range [0-1000], [0-1000] at 24 iterations (which under the traditional method would require 2^48 bits of memory to store), we can request:

[0,1000] [0,1000] @ 24 which means we divide the range in half rounding towards the larger area and increasing the bounds by 1.
We need the range:
-1 to 501 @ 23
Then:
-1 to 252 @ 22
Then:
-1 to 127 @ 21
Then:
-1 to 65 @ 20
Then:
-1 to 34 @ 19
Then:
-1 to 17 @ 18
Then:
-1 to 10 @ 17
Then:
-1 to 6 @ 16
Then:
-1 to 4 @ 15
Then:
-1 to 3 @ 14
Then:
-1 to 3 @ 13
...
...
Then:
-1 to 3 @ 1
Then:
-1 to 3 @ 0 which simply returns a field of 4x4 random numbers.


Rather than all that nonsense with wrapping and seeding and making what is actually a special case of the base case, we can simply reduce the algorithm to:

getTerrain(x0,y0,x1,y1,iterations) {
    if (iterations == 0) return maxtrixOf(random numbers);
    map = getTerrain(floor(x0/2) - 1, floor(y0/2) - 1, ceiling(x1/2), ceiling(y1/2), iterations-1);
    make a newmap twice as large.
    copy values from map into x*2,y*2 locations in newmap.
    apply diamond where possible. +- smaller random offset
    apply square where possible. +- smaller random offset
    return requested area from within newmap. (This is typically newmap from [1,(n-1)] [1,(n-1]
}

Done.

That's the entire algorithm. No more constraints and it's easier. On top of this the number of iterations doesn't control the size of the field but rather smoothness, of the underlying fractal. And since the base case is seen as an infinite field of purely random numbers, it goes on forever even at just a couple iterations as the iterations has no bearing on the size (it's always infinite).

On top of this rather than using a random number, you can use the the x, y, and iterations to make a pseudorandom but deterministic number like through a SHA1 hash. Then you can page from within the same area, forever without needing to have calculated all of it to start. You can create an infinite landscape without needing infinite memory to start, and returning to the same coordinates will give you the same results, and it doesn't matter which way you took to get there. 'There' will be deterministic.

---

I hacked together a working bit of the code in javascript:

http://tatarize.nfshost.com/FieldDiamondSquare.htm

Stealing liberally from http://www.somethinghitme.com/2009/12/06/terrain-generation-with-canvas-and-javascript/

---

Also check my newer algorithm Olsen Noise (though still lacking a javascript implementation) which corrects the artifacting and allows it to be changed into N dimensions. It also, simplifies. The algorithm even more.

http://godsnotwheregodsnot.blogspot.com/2014/08/3d-olsen-noise.html