Skip to content

Instantly share code, notes, and snippets.

@bmershon
Forked from mbostock/.block
Last active May 7, 2016 14:30
Show Gist options
  • Save bmershon/13a116651b27062dc32b to your computer and use it in GitHub Desktop.
Save bmershon/13a116651b27062dc32b to your computer and use it in GitHub Desktop.
D2 Shape Distribution
license: gpl-3.0

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.

<!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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment