$(window).on("load", function() { function ComputeGeometricMedian(rectPt, canvasSize) { function Candidate(pt, rectPt) { this.point = pt; this.distance = 0.0; for(var j = 0; j < rectPt.length; ++j) { this.distance += this.point.distance(rectPt[j]); } } // Find Geometric Median using GA var candidates = []; for(var i = 0; i < 500; ++i) { candidates.push(new Candidate(new Victor(Math.random()*canvasSize, Math.random()*canvasSize), rectPt)); } for(var generation = 0; generation < 20; ++generation) { candidates.sort(function(a, b){return a.distance - b.distance}); //////////////////////////////////////////////////////////////////////////////////////////////////////// // For the next generation, // Keep the best 20 candidates. The next 20*19/2 will be their kids. Then, add new genes for the rest. //////////////////////////////////////////////////////////////////////////////////////////////////////// var base = 20; for(var i = 0; i < 20; ++i) { for(var j = i+1; j < 20; ++j) { // Take the midpoint of dad and mom var kid = candidates[i].point.clone().add(candidates[j].point); kid.multiply(new Victor(0.5, 0.5)); candidates[base++] = new Candidate(kid, rectPt); } } while(base < candidates.length) { candidates[base++] = new Candidate(new Victor(Math.random()*canvasSize, Math.random()*canvasSize), rectPt); } } return candidates[0].point; } var ctx; // context for 2d graphics var canvas = document.getElementById('my_canvas'); var canvasSize = 256; canvas.width = canvasSize; canvas.height = canvasSize; ctx = canvas.getContext('2d'); var tlCorner = [ new Victor(0, 0), new Victor(canvasSize/2, 0), new Victor(canvasSize/2, canvasSize/2), new Victor(0, canvasSize/2) ]; var rectPt = []; var velocity = []; var initVelocity = new Victor(5, 5); for(var j = 0; j < 4; ++j) { rectPt.push(tlCorner[j].clone().add(new Victor(Math.random()*canvasSize/2, Math.random()*canvasSize/2))); velocity.push(new Victor(Math.random()*2 - 1, Math.random()*2 - 1).normalize().multiply(initVelocity)); } var t = 0; function draw() { if(t++ > 300) { for(var j = 0; j < 4; ++j) { velocity[j] = new Victor(Math.random()*2 - 1, Math.random()*2 - 1).normalize().multiply(initVelocity); } t = 0; } // update vertices for(var j = 0; j < 4; ++j) { velocity[j].multiply(new Victor(0.99, 0.99)); // deceleration rectPt[j].add(velocity[j]); var posRelativeToTLCorner = rectPt[j].clone().subtract(tlCorner[j]); if(posRelativeToTLCorner.x <= 0 || posRelativeToTLCorner.x >= canvasSize/2) { // clamp value rectPt[j].x = tlCorner[j].x + Math.min(Math.max(posRelativeToTLCorner.x, 1), canvasSize/2 - 1); velocity[j].x = -velocity[j].x; } if(posRelativeToTLCorner.y <= 0 || posRelativeToTLCorner.y >= canvasSize/2) { // clamp value rectPt[j].y = tlCorner[j].y + Math.min(Math.max(posRelativeToTLCorner.y, 1), canvasSize/2 - 1); velocity[j].y = -velocity[j].y; } } // avoid the rectangle degenerates to a triangle for(var j = 0; j < 4; ++j) { var prevDir = rectPt[j ? j-1 : 3].clone().subtract(rectPt[j]).normalize(); var nextDir = rectPt[(j+1)%4].clone().subtract(rectPt[j]).normalize(); if(prevDir.dot(nextDir) < -0.99) { rectPt[j].add(velocity[j]); } } ctx.fillStyle="#000"; ctx.clearRect(0, 0, canvas.width, canvas.height); ctx.strokeStyle = '#eee'; ctx.lineWidth = 5; ctx.beginPath(); ctx.moveTo(rectPt[0].x, rectPt[0].y); ctx.lineTo(rectPt[1].x, rectPt[1].y); ctx.lineTo(rectPt[2].x, rectPt[2].y); ctx.lineTo(rectPt[3].x, rectPt[3].y); ctx.closePath(); ctx.stroke(); ctx.strokeStyle = '#ec0'; ctx.lineWidth = 3; ctx.beginPath(); ctx.moveTo(rectPt[0].x, rectPt[0].y); ctx.lineTo(rectPt[2].x, rectPt[2].y); ctx.closePath(); ctx.stroke(); ctx.beginPath(); ctx.moveTo(rectPt[1].x, rectPt[1].y); ctx.lineTo(rectPt[3].x, rectPt[3].y); ctx.closePath(); ctx.stroke(); ctx.stroke(); var geometricMedian = ComputeGeometricMedian(rectPt, canvasSize); // console.log("geometricMedian " + geometricMedian); ctx.fillStyle = '#f00'; ctx.beginPath(); ctx.arc(geometricMedian.x, geometricMedian.y, 10, 0, Math.PI*2); ctx.closePath(); ctx.fill(); window.requestAnimationFrame(draw); } window.requestAnimationFrame(draw); });