Last active
December 26, 2015 00:29
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<!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