|
<!DOCTYPE html> |
|
<meta charset="utf-8"> |
|
<title>Zero Dimension Diagrams</title> |
|
<style> |
|
|
|
#background { |
|
fill: none; |
|
stroke: none; |
|
pointer-events: all; |
|
} |
|
|
|
.marker { |
|
fill: red; |
|
stroke: steelblue; |
|
stroke-width: 1.5px; |
|
} |
|
|
|
circle, |
|
.line { |
|
fill: none; |
|
stroke: steelblue; |
|
stroke-width: 1.5px; |
|
} |
|
|
|
.red-line { |
|
fill: none; |
|
stroke: orange; |
|
stroke-width: 1.5px; |
|
stroke-opacity: 0.4; |
|
} |
|
|
|
circle { |
|
fill: #fff; |
|
fill-opacity: .2; |
|
cursor: move; |
|
} |
|
|
|
.dot { |
|
fill: black; |
|
stroke: steelblue; |
|
stroke-width: 1.5px; |
|
} |
|
|
|
.ghost { |
|
fill: none; |
|
stroke: steelblue; |
|
stroke-width: 1.5px; |
|
} |
|
|
|
|
|
.invisible-dot { |
|
fill: none; |
|
stroke: none; |
|
stroke-width: 1.5px; |
|
} |
|
|
|
.selected { |
|
fill: #ff7f0e; |
|
stroke: #ff7f0e; |
|
} |
|
|
|
#buttons { |
|
position: absolute; |
|
top: 20px; |
|
left: 20px; |
|
z-index: 2; |
|
} |
|
|
|
button { |
|
display: block; |
|
width: 10em; |
|
} |
|
|
|
button:focus { |
|
outline: none; |
|
} |
|
|
|
.axis path, |
|
.axis line { |
|
fill: none; |
|
stroke: grey; |
|
stroke-width: 1; |
|
shape-rendering: crispEdges; |
|
} |
|
|
|
#chart1 { |
|
position: absolute; |
|
margin-top: 20px; |
|
left: 0px; |
|
} |
|
|
|
#chart2{ |
|
position: absolute; |
|
margin-top: 20px; |
|
left: 500px; |
|
} |
|
|
|
#chart3 { |
|
position: absolute; |
|
left: 450px; |
|
top: 70px; |
|
} |
|
|
|
#slider { |
|
-webkit-appearance: slider-vertical; |
|
width: 20px; |
|
height: 354px; |
|
} |
|
|
|
|
|
</style> |
|
<body> |
|
|
|
<div id="buttons"> |
|
<button id="create">Create Dgm<sub>0</sub>(F)</button> |
|
</div> |
|
<container id="chart1"> |
|
</container> |
|
<container id = "chart3"> |
|
<input type="range" id="slider" min="0" max="350" step="1" value="20" /> |
|
</container> |
|
<container id="chart2"> |
|
</container> |
|
<script type="text/javascript" src="https:d3js.org/d3.v3.min.js"></script> |
|
<script> |
|
|
|
|
|
/** |
|
* Author: Brooks Mershon |
|
* October 12, 2014 |
|
* Version 1.3 |
|
* |
|
* Created as part of a project for MATH 412: Topology with Applications taught at Duke University. |
|
* |
|
* Heavily modified from Mike Bostock's http://bl.ocks.org/mbostock/4342190, "Spline Editor." |
|
|
|
* Copyright (c) 2014 Brooks Mershon |
|
* The MIT License - http://opensource.org/licenses/MIT |
|
* |
|
* |
|
* */ |
|
|
|
(function() { |
|
|
|
var margin = {top: 50, right: 50, bottom: 50, left: 50}, |
|
width = 450 - margin.left - margin.right, |
|
height = 450 - margin.top - margin.bottom; |
|
|
|
var epsilon = 1, |
|
points = []; |
|
for(var i = 1; i < 5; i++) { |
|
points.push([i * width / 5, 50 + Math.random() * (height - 100)]); |
|
} |
|
|
|
var dragged = null, |
|
selected = points[0]; |
|
|
|
var svg = d3.select("#chart1").append("svg") |
|
.attr("width", width + margin.left + margin.right) |
|
.attr("height", height + margin.top + margin.bottom) |
|
.append("svg:g") |
|
.attr("transform", "translate(" + margin.left + "," + margin.top + ")"); |
|
|
|
svg.append("rect") |
|
.attr("id", "background") |
|
.attr("width", width + margin.left + margin.right) |
|
.attr("height", height + margin.bottom + margin.top) |
|
.on("mousedown", mousedown); |
|
|
|
/* |
|
spline edited by user via control points to produce our function F |
|
*/ |
|
var line = d3.svg.line(); |
|
line.interpolate("basis"); |
|
svg.select("path").attr("d", line); |
|
|
|
|
|
/* |
|
Set up second SVG containing the plot of birth/death pairs after running 0-dimensional persistence |
|
on the user defined function. |
|
*/ |
|
|
|
var svg_2 = d3.select("#chart2").append("svg") |
|
.attr("width", width + margin.left + margin.right) |
|
.attr("height", height + margin.top + margin.bottom) |
|
.append("g") |
|
.attr("transform", "translate(" + margin.left + "," + margin.top + ")"); |
|
|
|
svg_2.append("rect") |
|
.attr("id", "background") |
|
.attr("width", width + margin.left + margin.right) |
|
.attr("height", height + margin.bottom + margin.top) |
|
|
|
svg_2.append("line") |
|
.attr("x1", 0) |
|
.attr("x2", width) |
|
.attr("y1", height) |
|
.attr("y2", 0) |
|
.attr("stroke", "#808080") |
|
.attr("stroke-width", 2) |
|
|
|
/* |
|
Set up height-line which user scrubs back and forth to reveal components forming |
|
*/ |
|
|
|
svg.append("line") |
|
.attr("x1", 0) |
|
.attr("x2", width) |
|
.attr("y1", height) |
|
.attr("y2", height) |
|
.attr("stroke", "red") |
|
.attr("stroke-width", 2) |
|
.attr("id", "height-line") |
|
.attr("stroke-dasharray", "5, 5") |
|
|
|
|
|
/* |
|
Use SVG clipping to cover up the user-defined function for all points along curve greater than the current height |
|
*/ |
|
|
|
svg.append("svg:clipPath") |
|
.attr("id", "clipper") |
|
.append("svg:rect") |
|
.attr("x", 0) |
|
.attr("y", 0) |
|
.attr("width", width+40) |
|
.attr("height", height) |
|
.attr('id', 'clip-rect'); |
|
|
|
var clipGroup = svg.append("svg:g") |
|
.attr("clip-path", "url(#clipper)") |
|
|
|
|
|
clipGroup.append("path") |
|
.datum(points) |
|
.attr("class", "line") |
|
.call(redraw); |
|
|
|
d3.select(window) |
|
.on("mousemove", mousemove) |
|
.on("mouseup", mouseup) |
|
.on("keydown", keydown); |
|
|
|
d3.select("#create") |
|
.on("click", createDgm0) |
|
|
|
|
|
/* |
|
Append axes to both SVGs |
|
*/ |
|
var x = d3.scale.linear().range([0, width]); |
|
var y = d3.scale.linear() |
|
.range([height, 0]).domain([0, height]); |
|
|
|
|
|
/* |
|
Set up axes for both svg and svg_2 |
|
*/ |
|
|
|
var xAxis = d3.svg.axis() |
|
.scale(x) |
|
.orient("bottom"); |
|
|
|
var yAxis = d3.svg.axis() |
|
.scale(y) |
|
.orient("left"); |
|
|
|
svg.append("g") |
|
.attr("class", "x axis") |
|
.attr("transform", "translate(0," + height + ")") |
|
.call(xAxis); |
|
|
|
svg.append("g") |
|
.attr("class", "y axis") |
|
.call(yAxis) |
|
.append("text") |
|
.attr("transform", "rotate(-90)"); |
|
|
|
|
|
var x_2 = d3.scale.linear().range([0, height]).domain([0, height]); |
|
var y_2 = d3.scale.linear() |
|
.range([height, 0]).domain([0, height]); |
|
|
|
|
|
var xAxis_2 = d3.svg.axis() |
|
.scale(x_2) |
|
.orient("bottom"); |
|
|
|
var yAxis_2 = d3.svg.axis() |
|
.scale(y_2) |
|
.orient("left"); |
|
|
|
svg_2.append("g") |
|
.attr("class", "x axis") |
|
.attr("transform", "translate(0," + height + ")") |
|
.call(xAxis_2) |
|
.append("text") |
|
.attr("x", width) |
|
.attr("y", -20) |
|
.attr("dy", ".71em") |
|
.style("text-anchor", "end") |
|
.text("Birth"); |
|
|
|
svg_2.append("g") |
|
.attr("class", "y axis") |
|
.call(yAxis_2) |
|
.append("text") |
|
.attr("transform", "rotate(-90)") |
|
.attr("y", 6) |
|
.attr("dy", ".71em") |
|
.style("text-anchor", "end") |
|
.text("Death"); |
|
|
|
|
|
|
|
d3.select("#slider").on("input", function() { |
|
dragLineTo(+this.value) |
|
}) |
|
|
|
|
|
function redraw() { |
|
|
|
svg.select("path").attr("d", line); |
|
|
|
svg.selectAll("#marker").remove(); |
|
svg.selectAll(".red-line").remove(); |
|
|
|
var circle = svg.selectAll("circle") |
|
.data(points); |
|
|
|
|
|
|
|
circle.enter().append("circle") |
|
.attr("r", 1e-6) |
|
.on("mousedown", function(d) { selected = dragged = d; redraw(); }) |
|
.transition() |
|
.duration(2000) |
|
.ease("elastic") |
|
.attr("r", 6.5); |
|
|
|
|
|
circle |
|
.attr("id", "control-point") |
|
.classed("selected", function(d) { return d === selected; }) |
|
.attr("cx", function(d) { return d[0]; }) |
|
.attr("cy", function(d) { return d[1]; }); |
|
|
|
|
|
circle.exit().remove(); |
|
|
|
|
|
if (d3.event) { |
|
d3.event.preventDefault(); |
|
d3.event.stopPropagation(); |
|
} |
|
|
|
svg.node().focus(); |
|
|
|
} |
|
|
|
function mousedown() { |
|
|
|
var circle = d3.selectAll("circle") |
|
.transition() |
|
.duration(500) |
|
.attr("r", 6.5); |
|
|
|
m = d3.mouse(svg.node()); |
|
if (points.length == 0 || m[0] >= points[points.length - 1][0]) { |
|
points.push(selected = dragged = m); |
|
} |
|
redraw(); |
|
} |
|
|
|
/* |
|
Ensure spline passes vertical line test, using epsilon to nudge points |
|
*/ |
|
function mousemove() { |
|
if (!dragged) return; |
|
var m = d3.mouse(svg.node()); |
|
var previous = points[points.indexOf(dragged) - 1]; |
|
var next = points[points.indexOf(dragged) + 1]; |
|
if(!previous) previous = [0,0]; |
|
if(!next) next = [width, height]; |
|
dragged[0] = Math.max(previous[0] + epsilon, Math.min(next[0] - epsilon, m[0])); |
|
dragged[1] = Math.max(0, Math.min(height, m[1])); |
|
redraw(); |
|
} |
|
|
|
function mouseup() { |
|
if (!dragged) return; |
|
mousemove(); |
|
dragged = null; |
|
} |
|
|
|
function keydown() { |
|
if (!selected) return; |
|
switch (d3.event.keyCode) { |
|
case 8: // backspace |
|
case 46: { // delete |
|
var i = points.indexOf(selected); |
|
points.splice(i, 1); |
|
selected = points.length ? points[i > 0 ? i - 1 : 0] : null; |
|
redraw(); |
|
break; |
|
} |
|
} |
|
} |
|
|
|
function dragLineTo(y){ |
|
svg.select("#height-line") |
|
.attr("y1", height - y) |
|
.attr("y2", height - y) |
|
|
|
d3.select("#clip-rect") |
|
.attr("y", height - y) |
|
} |
|
|
|
/* |
|
Create Dgm0: |
|
Hide spline control-points |
|
Sample along path and create a vector of the critical values |
|
Plot markers at local extrema and endpoints on path |
|
Label markers with height order index (i.e. [0] is the "lowest" point) and x,y coordinates |
|
Draw linear interpolation between endpoints, local extrema |
|
*/ |
|
function createDgm0() { |
|
|
|
if (points.length < 2) { |
|
return; |
|
} |
|
|
|
redraw(); |
|
|
|
//shrink control-points |
|
var circle = d3.selectAll("circle") |
|
.transition() |
|
.duration(2000) |
|
.attr("r", 0); |
|
|
|
var cPoints = findCriticalPoints(d3.select("path")); |
|
|
|
|
|
// sort critical points from left to right |
|
cPoints.sort(function (a, b) { |
|
return a[0] - b[0] |
|
}); |
|
|
|
|
|
var tooltip = d3.select("body") |
|
.append("div") |
|
.style("position", "absolute") |
|
.style("z-index", "10") |
|
.style("visibility", "hidden") |
|
.text(""); |
|
|
|
/* |
|
Linear interpolation between local maxima and endpoints |
|
*/ |
|
|
|
var connectingLine = d3.svg.line(); |
|
|
|
var coordinates = coordinatesOnly(cPoints); //strip off index |
|
|
|
svg.append("path") |
|
.datum(coordinates) |
|
.attr("class", "red-line") |
|
|
|
connectingLine.interpolate("linear"); |
|
|
|
svg.select(".red-line").attr("d", connectingLine); |
|
|
|
var marker = svg.selectAll("marker") |
|
.data(cPoints) |
|
|
|
var markerWidth = 8; |
|
|
|
marker.enter().append("rect") |
|
.transition() |
|
.duration(1000) |
|
.ease("elastic") |
|
.attr("id", "marker") |
|
.attr("width", markerWidth) |
|
.attr("height", markerWidth) |
|
|
|
marker |
|
.attr("class", "marker") |
|
.attr("x", function(d) { return d[0] - markerWidth/2}) |
|
.attr("y", function(d) { return d[1] - markerWidth/2}) |
|
.on("mouseover", function(d){ |
|
tooltip.text("[" + d[2] + "] " + "(" + d[0].toPrecision(3) + ", " + (height - d[1]).toPrecision(3) + ")"); |
|
return tooltip.style("visibility", "visible"); |
|
}) |
|
.on("mousemove", function(){ return tooltip.style("top", (event.pageY-10)+"px").style("left",(event.pageX+20)+"px");}) |
|
.on("mouseout", function(){ return tooltip.style("visibility", "hidden");}); |
|
|
|
marker.exit().remove(); |
|
|
|
var edges = [], |
|
F = [], |
|
H = []; |
|
|
|
for(var i = 0; i < cPoints.length - 1; i++) { |
|
var a = cPoints[i]; |
|
var b = cPoints[i + 1]; |
|
|
|
var a_height_index = a[2]; // grab height-index, which is used for indexing into Function values (height) array |
|
var b_height_index = b[2]; |
|
|
|
|
|
edges.push([a_height_index, b_height_index, i]); |
|
H.push(height - Math.min(a[1], b[1])); //min value corresponds to the "higher" of the two endpoints |
|
} |
|
|
|
//sort critial points in height-order |
|
cPoints.sort(function (a, b) { |
|
return b[1] - a[1] |
|
}); |
|
|
|
for(var i = 0; i < cPoints.length; i++) { |
|
F.push(height - cPoints[i][1]); |
|
} |
|
|
|
var pairs = findBirthDeathPairs(cPoints, edges, F, H); |
|
|
|
plotPairs(pairs); |
|
|
|
} |
|
|
|
/* |
|
Returns array containing [x,y, height-index, left/right-index] points for local extrema and endpoints for the given path argument |
|
Points are returned in order of increasing x values (left-most to right-most) |
|
*/ |
|
function findCriticalPoints(path) { |
|
|
|
var dt = 0.2, |
|
pathNode = path.node(), |
|
pathLength = pathNode.getTotalLength(), |
|
criticalPoints = [], |
|
previous, current, next; |
|
|
|
previous = pointFromSVGPoint(pathNode.getPointAtLength(0)); |
|
criticalPoints.push(previous); |
|
|
|
for (var i = dt; i + dt < pathLength; i += dt) { |
|
|
|
var current = pointFromSVGPoint(pathNode.getPointAtLength(i)); |
|
next = pointFromSVGPoint(pathNode.getPointAtLength(i + dt)); |
|
//check for local min or local max |
|
if ((current[1] > previous[1] && current[1] > next[1]) || current[1] < previous[1] && current[1] < next[1]) { |
|
criticalPoints.push(current); |
|
} |
|
previous = current; |
|
} |
|
|
|
var endpoint = pointFromSVGPoint(pathNode.getPointAtLength(pathLength)); |
|
criticalPoints.push(endpoint); |
|
|
|
// label critical points with left/right-index |
|
for(var i = 0; i < criticalPoints.length; i++) { |
|
criticalPoints[i][3] = i; |
|
} |
|
|
|
//sort vertices in order to name them in increasing height-order |
|
criticalPoints.sort(function (a, b) { |
|
return b[1] - a[1] |
|
}); |
|
|
|
// label critical points in height order |
|
for(var i = 0; i < criticalPoints.length; i++) { |
|
criticalPoints[i][2] = i; |
|
} |
|
|
|
// sort points to return them in left/right order |
|
criticalPoints.sort(function (a, b) { |
|
return a[0] - b[0] |
|
}); |
|
|
|
return criticalPoints.slice(0); // return clone of criticalPoints array |
|
} |
|
|
|
function pointFromSVGPoint(d) { |
|
return [d.x, d.y, 0, 0] |
|
} |
|
|
|
function coordinatesOnly(points) { |
|
var v = []; |
|
for (var i = 0; i < points.length; i++) { |
|
v.push([points[i][0], points[i][1]]); |
|
} |
|
|
|
return v; |
|
} |
|
|
|
/* |
|
Pass in array of criticalPoints, sort them, and find the birth/death pairs created |
|
*/ |
|
function findBirthDeathPairs(vertices, edges, F, H) { |
|
|
|
// sorted vertices now correspond to u array |
|
vertices.sort(function (a, b) { |
|
return b[1] - a[1] //y axis is inverted! |
|
}); |
|
|
|
|
|
// edges should come in in order of their greatest endpoint f-value |
|
edges.sort(function (a, b) { |
|
var diff = H[a[2]] - H[b[2]]; |
|
// if greatest endpoints are equal, break tie by choosing edge with |
|
// higher f-value between the two non-equal endpoints (corresponding to the "younger" local minimum) |
|
return (diff == 0) ? (b[0] - a[0]) + (b[1] - a[1]) : diff; |
|
}); |
|
|
|
var u = [], |
|
pairs = []; |
|
|
|
/* |
|
Fill vector v with all points. Each point is it's own component initially. |
|
*/ |
|
for(var i = 0; i < vertices.length; i++) { |
|
u.push(i); |
|
} |
|
|
|
for(var j = 0; j < edges.length; j++) { |
|
|
|
var e = edges[j], |
|
a = e[0], //initial vertex of edge |
|
b = e[1]; //final vertex of edge |
|
|
|
while (a != u[a]) {a = u[a]}; |
|
while (b != u[b]) {b = u[b]}; |
|
|
|
|
|
if(a < b) { |
|
u[b] = a; |
|
pairs.push([F[b], H[e[2]], b]); //[f(vertex b), f(edge)] |
|
} else if (a > b) { |
|
u[a] = b; |
|
pairs.push([F[a], H[e[2]], a]); // [f(vertex a, f(edge)] |
|
} |
|
|
|
} |
|
|
|
// Find dots of infinite persistence, tag them as dying at -1 |
|
for(var i = 0; i < u.length; i++) { |
|
if(u[i] == i) { |
|
pairs.push([F[i],-1, i]) |
|
} |
|
} |
|
return pairs; |
|
} |
|
|
|
/* |
|
Plot dots of both finite and infinite persistence in svg_2 |
|
Label dots that do not fall on the diagonal with their height-order index |
|
*/ |
|
function plotPairs(pairs) { |
|
|
|
svg_2.selectAll(".ghost").transition().attr("width", 1e-6).attr("height", 1e-6).remove(); |
|
|
|
svg_2.selectAll(".label").remove(); |
|
svg_2.selectAll(".invisible-dot").remove() |
|
|
|
|
|
// turn previous dots into "ghosts" |
|
svg_2.selectAll(".dot").attr("class", "ghost") |
|
|
|
var dot = svg_2.selectAll(".dot") |
|
.data(coordinatesOnly(pairs)); |
|
|
|
var dotRadius = 7.5, epsilon = 0.0000001; |
|
|
|
dot.enter().append("rect") |
|
.attr("width", dotRadius) |
|
.attr("height", dotRadius) |
|
|
|
dot |
|
.attr("class", function(d) { return (Math.abs(d[0] - d[1]) < epsilon) ? "invisible-dot" : "dot"}) |
|
.attr("x", function(d) { return d[0] - dotRadius/2; }) |
|
.attr("y", function(d) { return ((d[1] == -1) ? height : height - d[1]) - dotRadius/2; }) |
|
|
|
//dot.exit().remove(); |
|
|
|
var label = svg_2.selectAll("label") |
|
.data(pairs) |
|
|
|
label.enter() |
|
.append("text") |
|
|
|
var epsilon = 0.000001; |
|
|
|
label |
|
.text(function(d) { return (Math.abs(d[0] - d[1]) < epsilon) ? "" : "[" + d[2] + "]" }) |
|
.attr("class", "label") |
|
.attr("x", function(d) { return d[0]}) |
|
.attr("y", function(d) { return (height - d[1]) - 20}) // d[1] = height - (distance from top of group in the svg) |
|
.attr("font-family", "sans-serif") |
|
.attr("font-size", "11px") |
|
.attr("fill", "black") |
|
.attr("class", "label"); |
|
|
|
label.exit().remove(); |
|
|
|
} |
|
})(); |
|
</script> |