Skip to content

Instantly share code, notes, and snippets.

@NV
Last active December 26, 2015 00:29
Show Gist options
  • Save NV/7064650 to your computer and use it in GitHub Desktop.
Save NV/7064650 to your computer and use it in GitHub Desktop.
2 Rectangles Convex Hull, e.g. find minimum polygon that wraps any two rectangles.
attachPair(document.getElementById('a'), document.getElementById('b'), createPolygon());
attachPair(document.getElementById('c'), document.getElementById('d'), createPolygon());
attachPair(document.getElementById('e'), document.getElementById('f'), createPolygon());
function attachPair(a, b) {
var polygon = createPolygon();
draggable(a, {
onMove: function(e) {
update(a, b, polygon);
}
});
draggable(b, {
onMove: function(e) {
update(a, b, polygon);
}
});
document.body.appendChild(polygon.svg);
a.classList.add('start');
b.classList.add('end');
update(a, b, polygon);
}
function createPolygon() {
var SVGNS = "http://www.w3.org/2000/svg";
var svg = document.createElementNS(SVGNS, 'svg');
var polygon = document.createElementNS(SVGNS, 'polygon');
svg.appendChild(polygon);
svg.setAttribute('width', 1000);
svg.setAttribute('height', 1000);
svg.setAttributeNS("http://www.w3.org/2000/xmlns/", "xmlns:xlink", "http://www.w3.org/1999/xlink");
var points = [];
for (var i = 4; i > 0; i--) {
var point = svg.createSVGPoint();
points.push(point);
polygon.points.appendItem(point);
}
return {
svg: svg,
polygon: polygon
};
}
function addPoint(polygon, point) {
var pt = polygon.ownerSVGElement.createSVGPoint();
pt.x = point.x;
pt.y = point.y;
polygon.points.appendItem(pt);
}
document.getElementById('a').ondragstart = function(e) {
e.dataTransfer.effectAllowed = 'move';
}
var polygon = document.getElementById('polygon');
var points = [];
for (var i = 0; i < polygon.points.numberOfItems; i++) {
points.push(polygon.points.getItem(i));
}
function draggable(elem, opt) {
opt || (opt = {});
elem.addEventListener('mousedown', function(e) {
var x = 0;
var y = 0;
var top = parseInt(elem.style.top || 0);
var left = parseInt(elem.style.left || 0);
var isFirst = true;
function onMove(e) {
if (isFirst) {
isFirst = false;
x = e.clientX;
y = e.clientY;
return;
}
var currentX = e.clientX;
var currentY = e.clientY;
var newTop = Math.max(0, top + (currentY - y));
var newLeft = Math.max(0, left + (currentX - x));
elem.style.top = newTop + 'px';
elem.style.left = newLeft + 'px';
e.preventDefault();
opt.onMove && opt.onMove(e);
}
function onUp() {
window.removeEventListener('mousemove', onMove, false);
window.removeEventListener('mouseup', onUp, false);
}
window.addEventListener('mousemove', onMove, false);
window.addEventListener('mouseup', onUp, false);
e.preventDefault();
}, false)
}
function update(a, b, polygon) {
var ax = parseInt(a.style.left);
var ay = parseInt(a.style.top);
var ax2 = ax + a.offsetWidth;
var ay2 = ay + a.offsetHeight;
var bx = parseInt(b.style.left);
var by = parseInt(b.style.top);
var bx2 = bx + b.offsetWidth;
var by2 = by + b.offsetHeight;
enclose([
{x: ax, y: ay},
{x: ax2, y: ay},
{x: ax2, y: ay2},
{x: ax, y: ay2}
], [
{x: bx, y: by},
{x: bx2, y: by},
{x: bx2, y: by2},
{x: bx, y: by2}
]
, polygon);
}
function enclose(a, b, polygon) {
// make a left topmost rect
if (b[0].x < a[0].x || b[0].x === a[0].x && b[0].y > a[0].y) {
var c = a;
a = b;
b = c;
}
polygon.polygon.points.clear();
var lastP = null;
function add(p) {
if (lastP && p.x === lastP.x && p.y === lastP.y) {
return;
}
addPoint(polygon.polygon, p);
lastP = p;
}
add(a[0]);
if (a[0].y > b[0].y) {
add(b[0]);
add(b[1]);
} else {
add(a[1]);
}
if (a[1].x > b[1].x) {
add(a[1]);
add(a[2]);
} else {
add(b[1]);
add(b[2]);
}
if (a[2].y > b[2].y) {
add(a[2]);
add(a[3]);
} else {
add(b[2]);
add(b[3]);
}
add(a[3]);
}
// http://en.wikipedia.org/wiki/Gift_wrapping_algorithm
function covexHull(points) {
var leftmost = topLeftmost(points);
var pointOnHull = leftmost;
var hull = [];
var length = points.length;
var i = 0;
var k = 0;
do {
var endpoint = points[i];
var j = i;
for (var j = i; j < length; j++) {
var currentAngle = angle(pointOnHull, endpoint);
if (currentAngle < prevAngle) {
k = j;
}
}
prevAngle = currentAngle;
hull.push(pointOnHull);
i++;
} while (endpoint !== leftmost);
return hull;
}
function angle(a, b) {
return Math.atan2(b.y - a.y, b.x - a.x);
}
function topLeftmost(points) {
var j = 0;
var current = points[j];
for (var i = 1; i < points.length; i++) {
var point = points[i];
if (current.x < point.x && current.y < point.y) {
current = point;
j = i;
}
}
points.splice(j, 1);
return current;
}
<!DOCTYPE html>
<html>
<head>
<title>2 Rectangles Convex Hull</title>
<style>
body {
position: relative;
background: rgb(37, 25, 0);
}
div {
position: absolute;
top: 64px;
left: 64px;
width: 64px;
height: 64px;
color: white;
border: 1px solid rgb(255, 0, 255);
opacity: 0.6;
z-index: 9;
}
div:hover {
opacity: 20;
}
svg {
pointer-events: none;
position: absolute;
top: 0;
left: 0;
z-index: 5;
}
polygon {
fill: rgba(91, 157, 217, 0.7);
}
</style>
</head>
<body>
<div id="a" class="draggable" style="top:32px; left:32px; height: 128px">A</div>
<div id="b" class="draggable" style="top:32px; left:128px; width: 128px;">B</div>
<div id="c" class="draggable" style="top:300px; left: 70px; width: 128px; height: 128px">C</div>
<div id="d" class="draggable" style="top:200px; left: 230px; width: 128px; height: 128px">D</div>
<div id="e" class="draggable" style="top:400px; left:128px; width: 128px">E</div>
<div id="f" class="draggable" style="top:400px; left:320px; height: 128px">F</div>
<svg id="svg" width="1000" height="800" viewPort="0 0 120 120" version="1.1" xmlns="http://www.w3.org/2000/svg">
<polygon id="polygon" points="0,0 0,0 0,0 0,0"/>
</svg>
<script src="connect.js"></script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment