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

Comments are closed.


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.

Twisted Oak Studios

2050 Gottingen Street

Halifax NS B3K 3A9

contact@twistedoakstudios.com