block by nitaku bf434557e0ad8fd70579

Gosper Clustering

Full Screen

Some random colors (on the left) are clustered according to the Euclidean distance of their corresponding RGB vectors. The image on the right shows the result of the process. Reload the page to create different colors.

In both cases, a Gosper Displacement is used for compactness. Because of this displacement, clusters can be appreciated as contiguous regions of cells having similar colors.

Clustering is provided by the hierarchical clustering feature of the clusterfck library.

index.js

(function() {
  var clusters, height, items, leaves, original, result, scale, svg, tree, width;

  svg = d3.select('svg');

  width = svg.node().getBoundingClientRect().width;

  height = svg.node().getBoundingClientRect().height;

  svg.attr({
    viewBox: "" + (-width / 2) + " " + (-height / 2) + " " + width + " " + height
  });

  items = d3.range(147).map(function(d) {
    return [70 + Math.random() * 150, 70 + Math.random() * 150, 70 + Math.random() * 150];
  });

  console.debug('Computing hierarchical clustering...');

  clusters = clusterfck.hcluster(items, clusterfck.EUCLIDEAN_DISTANCE, clusterfck.AVERAGE_LINKAGE);

  tree = tree_utils.binary_to_std(clusters);

  leaves = tree_utils.get_leaves(tree);

  console.debug('Computing the Space-Filling Curve layouts...');

  scale = 28;

  sfc_layout.displace(items, sfc_layout.GOSPER, scale, scale, -Math.PI / 6);

  sfc_layout.displace(leaves, sfc_layout.GOSPER, scale, scale, -Math.PI / 6);

  console.debug('Drawing...');

  original = svg.append('g').attr('transform', 'translate(-240,0)');

  result = svg.append('g').attr('transform', 'translate(240,0)');

  original.selectAll('.cell').data(items).enter().append('path').attr('class', 'cell').attr('d', jigsaw.hex_generate_svg_path(scale)).attr('transform', function(d) {
    return "translate(" + d.x + "," + d.y + ")";
  }).attr('fill', function(d) {
    return d3.rgb(d[0], d[1], d[2]);
  });

  result.selectAll('.cell').data(leaves).enter().append('path').attr('class', 'cell').attr('d', jigsaw.hex_generate_svg_path(scale)).attr('transform', function(d) {
    return "translate(" + d.x + "," + d.y + ")";
  }).attr('fill', function(d) {
    return d3.rgb(d.value[0], d.value[1], d.value[2]);
  });

}).call(this);

index.html

<!DOCTYPE html>
<html>
	<head>
        <meta charset="utf-8">
        <meta name="description" content="Gosper Clustering" />
        <title>Gosper Clustering</title>
		<link type="text/css" href="index.css" rel="stylesheet"/>
        <script src="//d3js.org/d3.v3.min.js"></script>
        <script src="//wafi.iit.cnr.it/webvis/tmp/clusterfck.js"></script>
        <script src="//wafi.iit.cnr.it/webvis/libs/jigmaps/zip.js"></script>
        <script src="//wafi.iit.cnr.it/webvis/libs/jigmaps/tree_utils.js"></script>
        <script src="//wafi.iit.cnr.it/webvis/libs/jigmaps/sfc_layout.js"></script>
        <script src="//wafi.iit.cnr.it/webvis/libs/jigmaps/jigsaw.js"></script>
	</head>
	<body>
        <svg height="500" width="960"></svg>
        <script src="index.js"></script>
	</body>
</html>

index.coffee

svg = d3.select('svg')
width = svg.node().getBoundingClientRect().width
height = svg.node().getBoundingClientRect().height

# translate the viewBox to have (0,0) at the center of the vis
svg
  .attr
    viewBox: "#{-width/2} #{-height/2} #{width} #{height}"
    
items = d3.range(147).map (d) -> [
  70+Math.random()*150,
  70+Math.random()*150,
  70+Math.random()*150
]

console.debug 'Computing hierarchical clustering...'
clusters = clusterfck.hcluster(
  items,
  clusterfck.EUCLIDEAN_DISTANCE,
  clusterfck.AVERAGE_LINKAGE
)
tree = tree_utils.binary_to_std(clusters)
leaves = tree_utils.get_leaves(tree)


console.debug 'Computing the Space-Filling Curve layouts...'
scale = 28
sfc_layout.displace(items, sfc_layout.GOSPER, scale, scale, -Math.PI/6)
sfc_layout.displace(leaves, sfc_layout.GOSPER, scale, scale, -Math.PI/6)


console.debug 'Drawing...'

original = svg.append('g')
  .attr('transform', 'translate(-240,0)')
  
result = svg.append('g')
  .attr('transform', 'translate(240,0)')

original.selectAll('.cell')
    .data(items)
  .enter().append('path')
    .attr('class', 'cell')
    .attr('d', jigsaw.hex_generate_svg_path(scale))
    .attr('transform', (d) -> "translate(#{d.x},#{d.y})")
    .attr('fill', (d) -> d3.rgb(d[0],d[1],d[2]))
    
result.selectAll('.cell')
    .data(leaves)
  .enter().append('path')
    .attr('class', 'cell')
    .attr('d', jigsaw.hex_generate_svg_path(scale))
    .attr('transform', (d) -> "translate(#{d.x},#{d.y})")
    .attr('fill', (d) -> d3.rgb(d.value[0],d.value[1],d.value[2]))

index.css

svg {
  background: white;
}

.cell {
  stroke: white;
  stroke-width: 3;
}
.label {
  fill: #333;
  font-family: sans-serif;
  text-anchor: middle;
  pointer-events: none;
}