H. Chase Stevens Logo

Most Common Tags

  1. programming
  2. python
  3. code
  4. philosophy
  5. evolution
  6. game design
  7. probability
  8. video games
  9. genetic algorithms
  10. government

Archives

Loading

Posts with tag "web":

Visualizing k-means clustering (using d3.js)

posted on: Friday, March 22, 2013 (8:22 am) by Chase Stevens

Having learned a little about d3.js at a hackathon I attended, I decided to put it to good use. Below is an interactive implementation of the k-means clustering algorithm, as visualized using d3.js. Click to place points. Centroids are (initially) set on randomly chosen points, and the number of clusters is set by a supposed rule of thumb. You can choose to step through the algorithm one centroid-readjustment/simultaneous point assignment at a time, or view the process in real time.

Download

//config values:
var colors = ['coral','green','steelblue','seagreen','yellow','cyan','salmon','skyblue','pink']
var radius = 8;
var trans_secs = 2;
var update_ms = 150;
var svg_size = {width:600,height:400};

//initialization
var mouse_x;
var mouse_y;
var new_points = false;
var points = new Array();
var centers = new Array();
var algo_started = false;
var svg = d3.select('#kmeans').append('svg')
.attr('width',svg_size.width)
.attr('height',svg_size.height);
canvas = document.getElementById('kmeans');
var stream = false;
var stop_update = false;

//@ http://jsfromhell.com/array/shuffle [v1.0]
function shuffle(o){ //v1.0
    for(var j, x, i = o.length; i; j = parseInt(Math.random() * i), x = o[--i], o[i] = o[j], o[j] = x);
    return o;
};

function safeShuffle(o){
	var x = new Array();
	for(var i = 0; i < o.length; i++){ 
		x[i] = o[i]; 
	}
	return shuffle(x);
}

function addPoint(){
	//add new point to canvas (d3)
	if (algo_started) {return true;}
	var rel_x = mouse_x - canvas.offsetLeft;
	var rel_y = mouse_y - canvas.offsetTop;
	if (points.length >= 1 && (points[points.length-1].x == rel_x)
		&& (points[points.length-1].y == rel_y)){ //making sure double-clicks don't get counted as two points
		return true;
	}
	points.push({x:(rel_x),y:(rel_y),plotted:false,nearest_center:null});
	new_points = true;
}

//tracking mouse:
document.captureEvents(Event.MOUSEMOVE);
document.onmousemove = getMousePosition;
function getMousePosition(mp) {
	mouse_x = mp.pageX;
	mouse_y = mp.pageY;
	return true;
}

function capitalize(string)
{
    return string.charAt(0).toUpperCase() + string.slice(1);
}

function createCenters () {
	//creating centroids
	document.getElementById('create').style.display = 'none';
	document.getElementById('move').style.display = 'block';
	algo_started = true;
	rand_points = safeShuffle(points);
	for (var i = 0; i < Math.round(Math.sqrt(rand_points.length / 2)); i++){
		centers.push({x:rand_points[i].x, y:rand_points[i].y, color:colors[i%colors.length], old_x:null, old_y:null});
	}
	svg.selectAll('.center')
	.data(centers)
	.enter()
	.append('circle')
	.attr('cx', function(d){return d.x;})
	.attr('cy', function(d){return d.y;})
	.attr('r', radius)
	.attr('style', function(d){return 'fill:' + d.color;})
	.attr('class','center')
   	.append("svg:title")
   	.text(function(d){return capitalize(d.color) + ' cluster center'});
}

function moveCenters () {
	//recalculate centroid positions given their assigned points
	for (var i = 0; i < centers.length; i++){
		var center = centers[i];
		center.old_x = center.x;
		center.old_y = center.y;
		var new_x = 0;
		var new_y = 0;
		var point_count = 0;
		for (var j = 0; j < points.length; j++){
			if (points[j].nearest_center == center){
				new_x += points[j].x;
				new_y += points[j].y;
				point_count++;
			}
		}
		center.x = Math.round(new_x / point_count);
		center.y = Math.round(new_y / point_count);
	}
	svg.selectAll('.center')
	.data(centers)
	.transition()
	.ease('linear')
	.duration(trans_secs * 1000)
	.attr('cx', function(d){return d.x;})
	.attr('cy', function(d){return d.y;});

	//check to see if centroids have failed to move any more (i.e. algorithm complete)
	var all_finalized = true;
	var svg_centers = svg.selectAll('.center')[0];
	for (var i = 0; i < centers.length; i++){
		var center = centers[i];
		var svg_center = {x: Math.round(svg_centers[i].cx.baseVal.value),
			y: Math.round(svg_centers[i].cy.baseVal.value)};
		all_finalized &= (center.x == center.old_x 
			&& center.y == center.old_y 
			&& Math.round(center.x) == svg_center.x 
			&& Math.round(center.y) == svg_center.y
			);
	}
	if (all_finalized){
		stream = false;
		document.getElementById('movecenters').disabled = true;
		document.getElementById('togglestream').disabled = true;
		document.getElementById('final').innerHTML = "Finalized!";
		stop_update = true;
	}
}

function eucDist(a,b){
	return Math.sqrt(Math.pow((a.x - b.x),2) + Math.pow((a.y - b.y),2));
}

function updatePoints(){
	//either creates new svg objects based on clicked points,
	//or re-colors points based on current centroid locations
	if (new_points && !algo_started){
		svg.selectAll('.point')
		.data(points)
		.enter()
		.append('circle')
		.attr('cx', function(d){return d.x;})
		.attr('cy', function(d){return d.y;})
		.attr('r', radius)
		.attr('class','point');
		new_points = false;
	}
	if (algo_started){
		for (var i = [0]; i < points.length; i++){
			var point = points[i];
			var center_candidate = null;
			var center_candidate_dist = 99999;
			var svg_centers = svg.selectAll('.center')[0]
			for (var j = 0; j < centers.length; j++){
				var svg_center = svg_centers[j];
				center_dist = eucDist(point,{x:svg_center.cx.baseVal.value,y:svg_center.cy.baseVal.value});
				if (center_dist < center_candidate_dist){
					center_candidate_dist = center_dist;
					center_candidate = centers[j];
				}
			}
			point.nearest_center = center_candidate;
			point.color = 'light' + point.nearest_center.color;
		}
		svg.selectAll('.point')
		.data(points)
		.attr('style', function(d){return 'fill:' + d.color;});
	}
}

function updateDisplay(){
	document.getElementById('numpoints').innerHTML = points.length;
	document.getElementById('numclusters').innerHTML = Math.round(Math.sqrt(points.length / 2));
}

function toggleStream(){
	stream ^= true;
}

window.setInterval(update,update_ms);
function update(){
	if (stop_update){return true;}
	updatePoints();
	updateDisplay();
	if (stream) { moveCenters(); }
}

Tags: code, d3, javascript, machine learning, programming, web

Exporting Color Scheme Designer Palettes to Paint.Net

posted on: Saturday, November 19, 2011 (10:59 am) by Chase Stevens

If you're like me and use the excellent tool over at Color Scheme Designer in conjunction with Paint.Net, you may have grown frustrated with creating palettes one color at a time by copy-pasting hex values. No longer! Below, please find a short python application I wrote (which even uses a fancy and unnecessary GUI) to create Paint.Net palettes from Color Scheme Designer palettes. Just export your Color Scheme Designer palette to text, copy what the site gives you, paste it into the application, and click "convert and save". The resulting file is ready to import into Paint.Net at your leisure.

from Tkinter import *
from tkFileDialog import asksaveasfilename as save
from tkMessageBox import showinfo as disp

def convert():
    intext = str(text.dump(1.0, END))
    intext = intext.split(' = ')
    colorlist = list()
    for ss in intext:
        if ss[0] == '#':
            colorlist.append(ss[1:])
    filename = save(defaultextension='txt',initialdir='\%HOMEPATH\%\\My Documents\\Paint.NET User Files\\Palettes')
    palette = open(filename, 'w')
    for color in colorlist:
        palette.write('FF%s\n' %color)
    palette.close()
    disp('File Saved', 'File successfully saved as %s.' %filename)
    
root = Tk()
menubar = Menu(root)
menubar.add_command(label="Convert and Save", command=convert)
menubar.add_command(label="Quit", command=quit)
root.config(menu=menubar)
scroll = Scrollbar(root)
scroll.pack(side=RIGHT, fill=Y)
text = Text(root, wrap=WORD, yscrollcommand=scroll.set)
text.pack()
scroll.config(command=text.yview)
root.mainloop()

Tags: code, color, design, internet, programming, python, tkinter, web, web design