Last active
October 26, 2015 12:52
-
-
Save beardicus/7c815e13b5b15058aecc to your computer and use it in GitHub Desktop.
Vector Edge Trace
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<!DOCTYPE html> | |
<html><head><meta charset="utf-8"> | |
<style> | |
body { | |
margin: 0; | |
} | |
#canvas { | |
position: absolute; | |
visibility: hidden; | |
} | |
#video { | |
position: absolute; | |
top: 0px; | |
left: 0px; | |
background: black; | |
} | |
#svg { | |
position: absolute; | |
top: 0px; | |
left: 480px; | |
background: #ccc; | |
} | |
.line { | |
fill: none; | |
stroke: #999; | |
stroke-width: 1px; | |
} | |
.point { | |
fill: #F00; | |
} | |
</style> | |
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.6/d3.min.js"></script> | |
<script src="https://cdnjs.cloudflare.com/ajax/libs/jsfeat/0.0.8/jsfeat-min.js"></script> | |
<script src="simplify.js"></script> | |
</head> | |
<body> | |
<canvas id='canvas' width='480' height='360'></canvas> | |
<video id='video' width='480' height='360'></video> | |
<svg id="svg" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" ></svg> | |
<script src="script.js"></script> | |
</body> | |
</html> |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var width = 480, | |
height = 360, | |
data = [], | |
canvas, | |
context, | |
img_u8 = new jsfeat.matrix_t(width, height, jsfeat.U8C1_t), | |
video, | |
radius = 1; | |
window.onload = function(event) { | |
init(); | |
}; | |
function init() { | |
video = document.getElementById('video'); | |
canvas = document.getElementById('canvas'); | |
context = canvas.getContext('2d'); | |
// check for getUserMedia support | |
navigator.getMedia = navigator.getUserMedia || navigator.webkitGetUserMedia || navigator.mozGetUserMedia || navigator.msGetUserMedia || navigator.oGetUserMedia; | |
navigator.getMedia({video: true, audio: false}, videoFeed, videoError); | |
video.addEventListener('play', function() { | |
tick(this, context, width, height); | |
}, false); | |
} | |
function videoFeed(stream) { | |
var vendorURL = window.URL || window.webkitURL; | |
video.src = vendorURL.createObjectURL(stream); | |
video.play(); | |
} | |
function videoError(e) { | |
// wah! | |
} | |
function tick(v,c,w,h) { | |
var kernel_size = (radius + 1) << 1, | |
canvasImage, | |
start = new Date().getTime(); | |
context.drawImage(v,0,0,w,h); // draw video feed to canvas | |
canvasImage = context.getImageData(0, 0, width, height); | |
// run jsfeat image processing doodads | |
jsfeat.imgproc.grayscale(canvasImage.data, width, height, img_u8); | |
jsfeat.imgproc.gaussian_blur(img_u8, img_u8, kernel_size, 0); | |
jsfeat.imgproc.canny(img_u8, img_u8, 5, 100); | |
trace(); | |
render(); | |
var end = new Date().getTime(); | |
var time = end - start; // TODO display framerate or ms | |
setTimeout(tick, 0, video, context, width, height); | |
} | |
function trace() { | |
var point, nextpoint; | |
data = []; | |
for (var i = 0; i <= img_u8.data.length; i++) { | |
if (img_u8.data[i] == 255) { | |
// start pathfinding | |
point = {x: i % width, y: i / width | 0}; | |
img_u8.data[i] = 0; | |
// start a line | |
var line = []; | |
line.push(point); | |
while (nextpoint = lineGobble(point)) { | |
line.push(nextpoint); | |
point = nextpoint; | |
} | |
data.push(line); | |
} | |
} | |
} | |
function lineGobble(point) { | |
var neighbor = [ | |
[0,-1], // n | |
[1,0], // s | |
[0,1], // e | |
[-1,0], // w | |
[-1,-1],// nw | |
[1,-1], // ne | |
[1,1], // se | |
[-1,1], // sw | |
]; | |
var checkpoint = {}; | |
for (var i = 0; i < neighbor.length; i++) { | |
checkpoint.x = point.x + neighbor[i][0]; | |
checkpoint.y = point.y + neighbor[i][1]; | |
var result = checkpixel(checkpoint); | |
if (result) { | |
return checkpoint; | |
} | |
} | |
return false; | |
} | |
function checkpixel(point) { | |
if (0 <= point.x < width) { | |
if (0 <= point.y < height) { | |
// point is "in bounds" | |
var index = (point.y * width) + point.x; | |
if (img_u8.data[index] == 255) { | |
img_u8.data[index] = 0; | |
return true; | |
} | |
} | |
} | |
return false; | |
} | |
// D3 svg display stuff below | |
var line = d3.svg.line() | |
.x(function(d) { return d.x; }) | |
.y(function(d) { return d.y; }); | |
var svg = d3.select('#svg') | |
.attr("width", width) | |
.attr("height", height); | |
function render () { | |
data = data.map(function(d) { | |
if (d.length > 1) { | |
return simplify(d, 1); | |
} else { | |
return d; | |
} | |
}); | |
// set up a group for each line, and put the path in it | |
groups = svg.selectAll('g') | |
.data(data); | |
groups.exit().remove(); | |
groups.enter() | |
.append('g') | |
.append('path'); | |
groups | |
.select('path') | |
.attr("class", "line") | |
.attr("d", line); | |
// for each group, add a dot for each point in the path | |
circles = groups.selectAll('circle') | |
.data(function(d){return d;}); | |
circles.exit().remove(); | |
circles.enter() | |
.append('circle'); | |
circles | |
.attr("class", "point") | |
.attr("cx", function (d) { return d.x; }) | |
.attr("cy", function (d) { return d.y; }) | |
.attr("r", 1.5); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
(c) 2013, Vladimir Agafonkin | |
Simplify.js, a high-performance JS polyline simplification library | |
mourner.github.io/simplify-js | |
*/ | |
(function () { 'use strict'; | |
// to suit your point format, run search/replace for '.x' and '.y'; | |
// for 3D version, see 3d branch (configurability would draw significant performance overhead) | |
// square distance between 2 points | |
function getSqDist(p1, p2) { | |
var dx = p1.x - p2.x, | |
dy = p1.y - p2.y; | |
return dx * dx + dy * dy; | |
} | |
// square distance from a point to a segment | |
function getSqSegDist(p, p1, p2) { | |
var x = p1.x, | |
y = p1.y, | |
dx = p2.x - x, | |
dy = p2.y - y; | |
if (dx !== 0 || dy !== 0) { | |
var t = ((p.x - x) * dx + (p.y - y) * dy) / (dx * dx + dy * dy); | |
if (t > 1) { | |
x = p2.x; | |
y = p2.y; | |
} else if (t > 0) { | |
x += dx * t; | |
y += dy * t; | |
} | |
} | |
dx = p.x - x; | |
dy = p.y - y; | |
return dx * dx + dy * dy; | |
} | |
// rest of the code doesn't care about point format | |
// basic distance-based simplification | |
function simplifyRadialDist(points, sqTolerance) { | |
var prevPoint = points[0], | |
newPoints = [prevPoint], | |
point; | |
for (var i = 1, len = points.length; i < len; i++) { | |
point = points[i]; | |
if (getSqDist(point, prevPoint) > sqTolerance) { | |
newPoints.push(point); | |
prevPoint = point; | |
} | |
} | |
if (prevPoint !== point) newPoints.push(point); | |
return newPoints; | |
} | |
// simplification using optimized Douglas-Peucker algorithm with recursion elimination | |
function simplifyDouglasPeucker(points, sqTolerance) { | |
var len = points.length, | |
MarkerArray = typeof Uint8Array !== 'undefined' ? Uint8Array : Array, | |
markers = new MarkerArray(len), | |
first = 0, | |
last = len - 1, | |
stack = [], | |
newPoints = [], | |
i, maxSqDist, sqDist, index; | |
markers[first] = markers[last] = 1; | |
while (last) { | |
maxSqDist = 0; | |
for (i = first + 1; i < last; i++) { | |
sqDist = getSqSegDist(points[i], points[first], points[last]); | |
if (sqDist > maxSqDist) { | |
index = i; | |
maxSqDist = sqDist; | |
} | |
} | |
if (maxSqDist > sqTolerance) { | |
markers[index] = 1; | |
stack.push(first, index, index, last); | |
} | |
last = stack.pop(); | |
first = stack.pop(); | |
} | |
for (i = 0; i < len; i++) { | |
if (markers[i]) newPoints.push(points[i]); | |
} | |
return newPoints; | |
} | |
// both algorithms combined for awesome performance | |
function simplify(points, tolerance, highestQuality) { | |
var sqTolerance = tolerance !== undefined ? tolerance * tolerance : 1; | |
points = highestQuality ? points : simplifyRadialDist(points, sqTolerance); | |
points = simplifyDouglasPeucker(points, sqTolerance); | |
return points; | |
} | |
// export as AMD module / Node module / browser or worker variable | |
if (typeof define === 'function' && define.amd) define(function() { return simplify; }); | |
else if (typeof module !== 'undefined') module.exports = simplify; | |
else if (typeof self !== 'undefined') self.simplify = simplify; | |
else window.simplify = simplify; | |
})(); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment