Medial Axis (Centerline) algorithm for rectangles

by Raul Bojalil

HTML

<canvas width="300" height="300" style="border:1px solid #d3d3d3;"></canvas>

JavaScript

//test data
var rectangles = [
{
x: 0, y: 0, w: 100, h: 10
},
{
x: 80, y: 10, w: 10, h: 100
},
{
x: 90, y: 50, w: 90, h: 10,
},
{
x: 0, y: 70, w: 80, h: 10,
},
{
x: 0, y: 100, w: 80, h: 10
},
{
x: 180, y: 50, w: 10, h: 80
},
{
x: 90, y: 130, w: 100, h: 10, color: "red"
},
{
x: 80, y: 130, w: 10, h: 40, color: "blue"
},
{
x: 80, y: 170, w: 10, h: 40, color: "orange"
},
{
x: 60, y: 210, w: 30, h: 10, color: "orange"
},
{
x: 75, y: 220, w: 15, h: 40, color: "green"
},
{
x: 90, y: 160, w: 50, h: 10, color: "green"
},
{
x: 45, y: 250, w: 30, h: 10, color: "green"
},
{
x: 90, y: 240, w: 30, h: 20, color: "green"
},
{
x: 75, y: 260, w: 15, h: 20, color: "green"
},
{
x: 130, y: 170, w: 10, h: 30
},
{
x: 130, y: 200, w: 30, h: 10, color: "blue"
},
{
x: 160, y: 210, w: 30, h: 10, color: "green"
},
{
x: 190, y: 210, w: 30, h: 10, color: "red"
},
{
x: 220, y: 200, w: 10, h: 30
},
{
x: 220, y: 230, w: 30, h: 10, color: "purple"
},
{
x: 240, y: 240, w: 30, h: 10, color: "purple"
},
{
x: 220, y: 240, w: 15, h: 30
},

];

var collisionMap = new WeakMap();

var centerLines = [];

function getCollision(r1,r2){

		if(r1.x + r1.w === r2.x && r1.y + r1.h === r2.y) return "none";
    if(r2.x + r2.w === r1.x && r2.y + r2.h === r1.y) return "none";

    var dx=(r1.x+r1.w/2)-(r2.x+r2.w/2);
    var dy=(r1.y+r1.h/2)-(r2.y+r2.h/2);
    var width=(r1.w+r2.w)/2;
    var height=(r1.h+r2.h)/2;
    var crossWidth=width*dy;
    var crossHeight=height*dx;
    var collision='none';
    
    if(Math.abs(dx)<=width && Math.abs(dy)<=height){
        if(crossWidth>crossHeight){
            collision=(crossWidth>(-crossHeight))?'bottom':'left';
        }else{
            collision=(crossWidth>-(crossHeight))?'right':'top';
        }
    }
    
    if(collision != 'none') {
    	var c1 = collisionMap.get(r1);
      if(c1) c1.push({ collision, rectangle: r2 });
      else {
      	collisionMap.set(r1, [{ collision, rectangle: r2 }]);
      }
    }
    
    return collision;
}

function...