Minkowski sums: examples

posted by harrison on November 29, 2012

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:

 
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)); 
} 

And now some code so that we can draw, drag and drop things:

 
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(); 
} 

and some definitions for basic shapes:

 
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(); 
        } 
    } 
} 

look, shapes!

 
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"); 

And here’s some code to sum them:

 
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)); } 
    } 
} 

Try dragging the shapes around here:

And look at the results here (the top is the individual shapes, the bottom is the summed shape):

 
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

More interesting posts (8 of 33 articles)

Or check out our Portfolio.