This is a followup to this post I made a while ago about minkowski sums. I thought I’d show a few examples of minkowski sums with javascript, to give a better idea of what they look like. There won’t be too much discussion in this post; it’s mostly code. scroll to the bottom if you want to see the result. First, some helper functions for drawing things and vector math: And now some code so that we can draw, drag and drop things: and some definitions for basic shapes: look, shapes! And here’s some code to sum them: Try dragging the shapes around here: And look at the results here (the top is the individual shapes, the bottom is the summed shape): — —
Minkowski sums: examples
var closeStyle = 'fill';
function close(ctx) {
ctx.closePath();
if(closeStyle == 'stroke') ctx.stroke();
if(closeStyle == 'fill') ctx.fill();
}
function getCanvas(id) {
var canvas = document.getElementById(id);
var ctx = canvas.getContext("2d");
ctx.setTransform(1,0,0,-1,canvas.width/2, canvas.height/2);
return ctx;
}
function draw_circle(ctx, x, y, r) {
ctx.beginPath();
ctx.arc(x,y,r,0,2*Math.PI);
close(ctx);
}
function draw_polygon(ctx, pts) {
if(pts.length == 0) return;
ctx.beginPath();
ctx.moveTo(pts[0].x,pts[0].y);
for(var i=1; i < pts.length;++i) {
ctx.lineTo(pts[i].x,pts[i].y);
}
close(ctx);
}
function addPoints(a, b) {
return {x: a.x + b.x, y:a.y + b.y};
}
function subPoints(a,b) {
return {x:a.x - b.x, y:a.y - b.y};
}
//dot product
function dot(a,b) {
return a.x*b.x + a.y*b.y;
}
function length(v) {
return Math.sqrt(dot(v,v));
}
function perp(a) {
return {x:a.y, y: - a.x};
}
function scale(v,s) {
return {x:v.x*s, y:v.y*s};
}
function normalized(v) {
return scale(v,1/length(v));
}
function initCanvas(id, drag_shapes, other_shapes, colour) {
var canvas = document.getElementById(id);
var ctx = getCanvas(id);
ctx.strokeStyle = colour;
ctx.fillStyle = colour;
var getPos = function(e) { return {x: e.pageX - canvas.offsetLeft - canvas.width/2, y: -e.pageY + canvas.offsetTop + canvas.height/2}; }
var redraw = function() {
ctx.save();
ctx.setTransform(1,0,0,1,0,0);
ctx.clearRect(0,0,canvas.width,canvas.height);
ctx.restore();
for (var i=0;i<other_shapes.length;++i) { other_shapes[i].draw(ctx); };
for (var i=0;i<drag_shapes.length;++i) { drag_shapes[i].draw(ctx); };
window.setTimeout(redraw, 1000/60); //don't use this in real code. it's wrong, but good enough
};
canvas.onmousedown = function (e) {
var pos = getPos(e);
for (var i=0;i<drag_shapes.length;++i) {
var shape = drag_shapes[i];
if(shape.contains(pos)) {
canvas.onmousemove = function(e2) {
var p2 = getPos(e2);
var delta = subPoints(p2,pos);
shape.move(delta);
pos = p2;
}
break;
}
}
}
canvas.onmouseup = function(e) { canvas.onmousemove = null; };
redraw();
}
function circle(x,y,r) {
return {
pos: function() {return {x:x,y:y}},
radius: r,
move: function(delta) {
x += delta.x;
y += delta.y;
},
draw: function(ctx) { draw_circle(ctx, x, y, this.radius); },
contains: function(p) {
p = subPoints(this.pos(),p);
return (p.x*p.x+p.y*p.y) < this.radius*this.radius;
},
support: function(d) {
return addPoints(this.pos(), scale(normalized(d), this.radius));
}
}
}
function point(x,y) {
return circle(x,y,5);
}
function line(start,end) {
return {
start: start,
end: end,
draw: function(ctx) {
ctx.beginPath();
ctx.moveTo(start.pos().x, start.pos().y);
ctx.lineTo(end.pos().x, end.pos().y);
ctx.stroke();
},
support: function(d) {
x = dot(subPoints(this.end.pos(),this.start.pos()), d);
return x > 0 ? this.end.pos() : this.start.pos();
}
}
}
c0 = circle(0,0,20);
c1 = circle(-20, -20, 10);
l0s = point(30,30);
l0e = point(10,10);
l0 = line(l0s, l0e);
l1s = point(10, -30);
l1e = point(10, -10);
l1 = line(l1s, l1e);
initCanvas("shapes", new Array(c0,c1, l0s,l0e,l1s,l1e), new Array(l0,l1), "black");
function addLine(shape, line) {
return {
draw: function(ctx) {
var p0 = line.start.pos();
var p1 = line.end.pos();
ctx.save();
ctx.translate(p0.x, p0.y);
shape.draw(ctx);
ctx.restore();
ctx.save();
ctx.translate(p1.x, p1.y);
shape.draw(ctx);
ctx.restore();
var supDir = perp(subPoints(p1,p0));
var sup0 = shape.support(supDir);
var sup1 = shape.support(scale(supDir, -1));
draw_polygon(ctx, [addPoints(sup0, p0), addPoints(sup1, p0), addPoints(sup1, p1), addPoints(sup0, p1)]);
},
support: function(d) {
return addPoints(shape.support(d), line.support(d));
}
}
}
function addCircles(c0, c1) {
return {
pos: function() { return addPoints(c0.pos(), c1.pos()); },
radius: c0.radius + c1.radius,
draw: function(ctx) { draw_circle(ctx, this.pos().x, this.pos().y, this.radius); },
support: function(d) { return addPoints(c0.support(d), c1.support(d)); }
}
}
sum0 = addLine(c0, l0);
sum1 = addLine(c1, l1);
sum2 = addLine(sum0, l1);
sum3 = addCircles(c0, c1);
sum4 = addLine(l0, l1);
sum5 = addLine(addLine(addCircles(c0, c1), l0), l1);
initCanvas("control", [c0,c1, l0s, l0e, l1s, l1e], [l0, l1], "black");
initCanvas("sum0parts", [], [c0, l0], "green");
initCanvas("sum1parts", [], [c1,l1], "blue");
initCanvas("sum2parts", [], [c0,l0,l1], "magenta");
initCanvas("sum3parts", [], [c0,c1], "yellow");
initCanvas("sum4parts", [], [l0,l1], "cyan");
initCanvas("sum5parts", [], [c0,c1,l0,l1], "white");
initCanvas("sum0", [], [sum0], "green");
initCanvas("sum1", [], [sum1], "blue");
initCanvas("sum2", [], [sum2], "magenta");
initCanvas("sum3", [], [sum3], "yellow");
initCanvas("sum4", [], [sum4], "cyan");
initCanvas("sum5", [], [sum5], "white");
Discuss on Reddit
Twisted Oak Studios offers consulting and development on high-tech interactive projects. Check out our portfolio, or Give us a shout if you have anything you think some really rad engineers should help you with.
Archive
