D3 Examples - D2 Shape Distribution

D2 Shape Distribution

Robert Osada, Thomas Funkhouser, Bernard Chazelle, and David Dobkin released a paper in 2002 detailing a method for measuring the similarity between 3D shapes.

The paper proposes creating probability distributions from shapes which might be easily compared with metrics like Earth Mover's Distance. Such probability distributions promise to capture a shape's signature. Figures like a square

The D2 shape function generates a distribution of distances between randomly sampled points from a 3D model (or 2D model!).

The D3 function generates a distribution of the square root of the area of sampled triangles

The D4 function similarly operates on the cube root of volumes of sampled tetrahedrons.

Some basic characteristics of objects like straight lines, squares, and crosses can be studied for simple line drawings.

xxxxxxxxxx
 
<!DOCTYPE html>
<meta charset="utf-8">
<style>
​
rect {
  stroke: #000;
  cursor: crosshair;
}
​
.line {
  pointer-events: none;
  fill: none;
  stroke: #3182BD;
  stroke-width: 3px;
  stroke-linejoin: round;
  stroke-linecap: round;
}
​
path {
  fill: none;
  pointer-events: none;
}
​
#main {
  stroke: #000;
  stroke-width: 4px;
}
​
#ghost {
  stroke: #aaa;
  stroke-width: 2px;
}
​
.axis {
  pointer-events: none;
}
​
.axis path,
.axis line {
  fill: none;
  stroke: #000;
  shape-rendering: crispEdges;
}
​
</style>
<svg width="960" height="500">
<rect id="background"></rect>
<g id="histogram">
  <g id="paths">
    <path id="ghost"></path>
    <path id="main"></path>
  </g>
</g>
</svg>
<script src="https://d3js.org/d3.v3.min.js"></script>
<script>
"use strict";
var margin = 40,
    outerSize = 960,
    innerSize = outerSize/2 - margin * 2;
​
var lines = [],
    previous = [], data = [],
    N = 750, // number of samples
    activeLine;
​
var x = d3.scale.linear()
          .clamp(true)
          .domain([0, Math.SQRT2*innerSize])
          .range([0, innerSize]);
​
var y = d3.scale.linear()
          .domain([0, 0.4])
          .range([innerSize, 0]);
​
var xAxis = d3.svg.axis()
            .scale(x)
            .orient("bottom");
​
var yAxis = d3.svg.axis()
    .scale(y)
    .orient("left");
​
var renderPath = d3.svg.line()
    .x(function(d) { return d[0]; })
    .y(function(d) { return d[1]; })
    .interpolate("monotone");
​
var svg = d3.select("svg");
​
var background = d3.select("#background")
    .style("fill", "#fcfcfc")
    .attr("width", innerSize)
    .attr("height", innerSize)
    .attr("transform", "translate(" + (margin) + "," + (margin) + ")")
​
background
    .call(d3.behavior.drag()
      .on("dragstart", dragstarted)
      .on("drag", dragged)
      .on("dragend", dragended));
​
var pane = svg.append("g")
              .attr("transform", "translate(" + (margin) + "," + (margin) + ")");
​
var histogram = d3.select("#histogram")
                 .attr("transform", "translate(" + (innerSize + margin*2) + "," + (0) + ")");
​
var paths = d3.select("#paths")
              .attr("transform", "translate(" + (margin) + "," + (margin) + ")");
​
histogram.append("g")
    .attr("class", "x axis")
    .attr("transform", "translate(" + margin + "," + (innerSize + margin) + ")")
    .call(xAxis)
  .append("text")
    .attr("x", innerSize)
    .attr("y", 30)
    .attr("dy", ".71em")
    .style("text-anchor", "end")
    .text("distance (px)");
​
histogram.append("g")
    .attr("class", "y axis")
    .attr("transform", "translate(" + (margin) + "," + margin + ")")
    .call(yAxis)
  .append("text")
    .attr("x", 0)
    .attr("transform", "rotate(-90)")
    .attr("y", -40)
    .attr("dy", "-.71em")
    .style("text-anchor", "end")
    .text("density");
​
var plot = d3.svg.line()
    .x(function(d) { return x(d.x + d.dx/2); })
    .y(function(d) { return y(d.y); })
    .interpolate("monotone");
​
function update() {
  var samples,
      t, i,
      distances = [];
​
  t = d3.sum(lines, function(l) { return getPath(l).getTotalLength(); });
​
  // add even number of points, sampled from new path
  samples = shuffle(d3.merge(lines.map(function(l) {
    var n = Math.floor(N*(getPath(l).getTotalLength()/t)); // constant sample resolution
    return d3.range(0, n-1).map(function(d) {
      return samplePath(getPath(l));
    });
  })));
​
  for (i = 0; i < samples.length - 1; i++) {
    distances.push(distance(samples[i], samples[i+1]));
  }
​
  previous = data;
​
  // bin data for histogram display
  data = d3.layout.histogram()
    .frequency(false)
    .bins(x.ticks(15))
    (distances);
​
  histogram.select("#main").datum(data) 
      .attr("class", "graph")
      .attr("d", plot);
​
  histogram.select("#ghost").datum(previous) 
    .attr("class", "graph")
    .attr("d", plot);
}
​
function length(path) {
  return path.getTotalLength();
}
​
function samplePath(path) {
  var n = length(path);
  return getPoint(path.getPointAtLength(Math.random()*n));
}
​
function dragstarted() {
  activeLine = pane.append("path").datum([]).attr("class", "line");
}
​
function dragged() {
  activeLine.datum().push(d3.mouse(this));
  activeLine.attr("d", renderPath);
}
​
function dragended() {
  lines.push(activeLine);
  activeLine = null;
  update();
}
​
// access D3 selection to find DOM element
function getPath(line) {
  return line[0][0];
}
​
function getPoint(p) {
  return [p.x, p.y];
}
​
function distance(a, b) {
  return Math.pow((a[0] - b[0])*(a[0] - b[0]) + (a[1] - b[1])*(a[1] - b[1]), 0.5);
}
​
// Fisher–Yates shuffle
function shuffle(array) {
  var i = array.length, j, t;
  while (--i > 0) {
    j = ~~(Math.random() * (i + 1));
    t = array[j];
    array[j] = array[i];
    array[i] = t;
  }
  return array;
}
​
</script>
​
    