Skip to content

Instantly share code, notes, and snippets.

@zahlenteufel
Last active July 29, 2016 23:47
Show Gist options
  • Save zahlenteufel/ab5c353868aaa747fda0f1d0a0fbebd1 to your computer and use it in GitHub Desktop.
Save zahlenteufel/ab5c353868aaa747fda0f1d0a0fbebd1 to your computer and use it in GitHub Desktop.
Minimum Enclosing Rectangle
<canvas id="myCanvas" width="500" height="500"></canvas>
// https://jsfiddle.net/gastonbm/ryu8kwyj/
var points = [[100, 100], [270,300], [150, 400], [300,100], [370, 200]];
var c = document.getElementById("myCanvas");
var ctx = c.getContext("2d");
function drawPoint(x, y) {
ctx.beginPath();
ctx.arc(x, y, 4, 0, 2*Math.PI);
ctx.fillStyle = "#000000";
ctx.fill();
ctx.stroke();
}
function drawPoints() {
for (i = 0; i < points.length; i++) {
drawPoint(points[i][0], points[i][1]);
}
}
function drawLine(x1, y1, x2, y2, color) {
ctx.moveTo(x1, y1);
ctx.lineTo(x2, y2);
ctx.stroke();
}
function drawClosed(points, isBest) {
ctx.beginPath();
if (isBest)
ctx.globalAlpha=0.2;
ctx.strokeStyle = '#ff0000';
ctx.moveTo(points[0][0], points[0][1]);
ctx.lineTo(points[1][0], points[1][1]);
ctx.lineTo(points[2][0], points[2][1]);
ctx.lineTo(points[3][0], points[3][1]);
ctx.lineTo(points[0][0], points[0][1]);
if (isBest)
ctx.fill();
ctx.stroke();
ctx.globalAlpha=1;
}
function applym(M, v) {
return [M[0][0] * v[0] + M[0][1] * v[1], M[1][0] * v[0] + M[1][1] * v[1]];
}
function rotate(angle, points) {
var rotMatrix = [[Math.cos(angle), -Math.sin(angle)], [Math.sin(angle), Math.cos(angle)]];
var res = [];
for (var i = 0; i < points.length; i++) {
res.push(applym(rotMatrix, points[i]));
}
return res;
}
function calculateMinRectangle(points) {
var minX = Infinity, maxX = -Infinity, minY = Infinity, maxY = -Infinity;
for (var i=0; i<points.length; i++) {
minX = Math.min(minX, points[i][0]);
minY = Math.min(minY, points[i][1]);
maxX = Math.max(maxX, points[i][0]);
maxY = Math.max(maxY, points[i][1]);
}
var area = (maxX - minX) * (maxY - minY);
return [area, [[minX, minY], [maxX, minY], [maxX, maxY], [minX, maxY]]];
}
//var minRect = calculateMinRectangle(points);
//drawClosed(minRect);
var minArea = Infinity;
var bestRect;
for (i = 0; i < points.length; i++) {
for (j = i+1; j < points.length; j++) {
var dy = points[i][1] - points[j][1];
var dx = points[i][0] - points[j][0];
var angle = Math.atan2(dy, dx);
var transformedPoints = rotate(-angle, points);
var areaAndMinRect = calculateMinRectangle(transformedPoints);
var area = areaAndMinRect[0];
var rect = rotate(angle, areaAndMinRect[1]);
if (area < minArea) {
bestRect = rect;
}
drawClosed(rect);
}
}
drawClosed(bestRect, true);
drawPoints();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment