Forum Moderators: open
Find the optimal number of rectangles needed to cover an irregular rectilinear space.
Given a page marked up with HTML, and an array list of element IDs, create rectangles that cover the entire page with semi-opaque DIVs - covering all areas except those occupied by elements in the array. Imagine the end result as a blanket with holes in it - those holes allowing the user to interact with specified elements on the page, while the rest of the page is greyed out and unresponsive to mouse events.
Also needed is a trigger that makes the blanket appear and disappear.
Similar to a "light box" effect, but different, because the highlighted area is not a new rectangle floating above the blanket, it's part of the underlying page.
Implementation Stipulations
- Must be done with 100% JavaScript
- The blanket must be made out of DIV elements, styled with CSS to have a black background, 50% opaque.
- You may use a helper library, like mootools or Jquery
- The answer must not use Flash, Applets, AJAX, images, etc.
Input
- You are provided with a page marked up with HTML.
- You are also provided with an array list of element IDs, like this:
var holes = ['centerimage','leftnav','photo_of_roger'];
Optimal solution
- The best solution will be fast, efficient, robust, and flexible.
- A good solution will probably need an algorithm for employing an optimally small number of rectangles. But not necessarily
- The "holey blanket" will fit around irregular shapes,
- An excellent solution will employ an OOP programming style and be easy to understand, modify and extend.
- Ideally the show/hide trigger will be an event that can be triggered on the object class, like this:
var holes = ['centerimage','leftnav','photo_of_roger'];
var blanket = new Blanket(holes);
blanket.show();
blanket.hide();
disclaimer
This is not for a school project. It's a hobby thing. There is no prize to the winner, except the satisfaction of an intellectual challenge accomplished.
You are provided with a page marked up with HTML.
around irregular shapes,
You are hypothetically provided with a page marked up with HTML.I'm not going to actually post one here... any page will do
by irregular, I mean rectilinear, but not necessarily rectangular. a hole may be made of one or more rectangles, and they may be separate, adjacent or even overlapping.
Fotiman+astupidname, yes yes good ideas... but...
I'm going to insist that the underlying page not be molested by moving elements up and down the z-index; because the same Blanket object could then be employed to blank out any kind of page defined by any coordinates. Not necessarily those defined by the dimensions of an element.
For instance, the holes might not be HTML elements, they could be arbitrary rectangles:
holes = [
{x:20,y:20,h:100,w:100},
{x:50,y:90,h:75,w:30}
]
but for the purpose of a proof-of-concept, I'll stick with HTML elements as hole definers
molested
For instance, the holes might not be HTML elements, they could be arbitrary rectangles:
inside that container are a bunch of smaller rectangles that cover every space that is not defined as a "hole".
I have a working proof-of-concept now, but it's remarkably unoptimized (is that a word?). Even a few holes in the page produces a blanket comprised of hundreds of teeny tiny rectangles. It works... but the slicing is too aggressive.
You need to find the top-most coordinate. Create a div that is 100% wide, and that tall.
Then do the same for the left, right, and bottom sides. That's four divs.
From there, the extra number of divs should be no more than 25, assuming no more than three holes.
I believe the max number of slices needed is equal to the number of holes times 3, plus 1.
I need to play around with it a bit more before I have anything remotely resembling an optimized solution.
yeah, I think you're right. I was unable to create a test case that needed more than 3n+1.
here's the algorithm I came up with, which reduces (but does not optimize!) the # of shapes needed:
1) divide the page into a grid, with one line along the edge of each hole
2) mark any grid cells that contain a hole with an "x"
3) start in the top left cell. if it contains an x or an o, go to the next cell. read across and down until you get to an empty one.
4) if all the spaces to the right of the cell are empty, then grow the shape to the right. put an "o" in all those cells
5) if all the spaces below the cell(s) are empty, then grow the shape downward. put an "o" in all those cells
6) if the shape has grown as far as it can, push it into the Shapes array. goto 8
7) goto 4
8) if there are any empty cells, goto 3
9) end
I discovered that this algo will fill the space and reduce the number of rectangles needed, but it is not optimal. A few minutes with a pencil + it's not hard to find cases where the optimal result is not achieved by this algo... its deficiency is the cell choice routine in step 3.
Sometimes an optimal result happens from not starting with the top left cell and working left to right. The "cell growing" method feels right to me, but in order to know what sequence to choose the cells, I may have to run the routine using a set of permutations.
or maybe there's another way.
1. Convert all of your holes into x,y coordinates (for top left) + width and height values.
var holes = [
{x: 3, y: 3, w: 4, h: 4},
{x: 5, y: 5, w: 4, h: 4},
{x: 11, y: 4, w: 2, h: 3}
];
..............
..............
..AAAA........
..AAAA....CC..
..AA**BB..CC..
..AA**BB..CC..
....BBBB......
....BBBB......
..............
..............
2. Next, I would convert these to a different set of boxes that could be represented as horizontal boxes like this:
..............
..............
..aaaa........
..aaaa....dd..
..bbbbbb..dd..
..bbbbbb..dd..
....cccc......
....cccc......
..............
..............
That gives me 4 different holes that will be easier to work with (a, b, c, and d):
holes = [
{x:3, y:3, w: 4, h:2},
{x:3, y:5, w: 6, h:2},
{x:5, y:7, w: 4, h:2},
{x: 11, y: 4, w: 2, h: 3}
];
2. Get the x,y,w,h for your bounding box as well (ie - most likely the viewport).
3. Work recursively from the top of the page down. Don't work in grids, rather use the locations of the holes as boundaries for calculating height and width.
I haven't really thought through the rest. By my thought is that you don't want to sweep a grid... rather, you'd want to generate blankets as needed around the holes.
This seems to work if the holes don't overlap. However, once you start overlapping them, there's issues. Also, you'll see a 1px gap between the edge of the hole and the blanket. This is because if they touch, the test for whether they intersect returns true, which causes an infinite loop, so some work to be done there. Also, the logic for working around a hole isn't quite right (it works when the boxes don't overlap though).
This is probably as far as I'm going to take this example. I hope someone else takes up this challenge and cleans this code up or provides another example. :)
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
"http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
<title>Holey Blankets Batman!</title>
<!-- CSS -->
<!-- The YUI Logger is used for debugging. I'm using the 'sam' skin. -->
<link type="text/css" rel="stylesheet" href="http://yui.yahooapis.com/2.7.0/build/logger/assets/skins/sam/logger.css">
<style type="text/css">
/* Reset all (to get rid of collapsing margins) */
* { margin: 0; padding: 0; border: 0; }
#A {
position: absolute;
z-index: 1;
left: 30px;
top: 30px;
width: 40px;
height: 40px;
overflow: hidden;
background: #c00;
}
#B {
position: absolute;
z-index: 2;
left: 50px;
top: 150px;
width: 40px;
height: 40px;
overflow: hidden;
background: #0c0;
}
#C {
position: absolute;
z-index: 3;
left: 110px;
top: 40px;
width: 20px;
height: 30px;
overflow: hidden;
background: #00c;
}
</style>
</head>
<body class="yui-skin-sam">
<p>This text will show through the opaque blanket, but can't be selected.</p>
<div id="A">A</div>
<div id="B">B</div>
<div id="C">C</div>
<!-- Scripts -->
<script type="text/javascript"
src="http://yui.yahooapis.com/2.7.0/build/yahoo-dom-event/yahoo-dom-event.js"></script>
<script type="text/javascript" src="http://yui.yahooapis.com/2.7.0/build/logger/logger-min.js"></script>
<script type="text/javascript">
var FOTI = (function (){ // Namespaced to prevent conflicts. Use whatever you like
var myLogReader = new YAHOO.widget.LogReader();
// Shortcuts for the YUI classes
var D = YAHOO.util.Dom;
var E = YAHOO.util.Event;
var R = YAHOO.util.Region;
var ZBREAKER = 0; // Prevent endless loop...debugging only
return {
/**
* A Blanket covers all elements in a given area except for the regions
* defined by the holes.
* @namespace FOTI
* @class Blanket
* @param {String ¦ HTMLElement ¦ Array} el Accepts a string to use as an ID for getting a DOM reference, an actual DOM reference, or an Array of IDs and/or HTMLElements.
* @constructor
*/
Blanket: function(el) {
var i, l,
isShowing = false, // private flag, set when the blanket is shown
holes = D.get(el), // get the hole elements
viewPortRegion = new R(0, D.getViewportWidth(), D.getViewportHeight(), 0),
swatches = []; // the collection of swatches that make up the blanket
if (!YAHOO.lang.isArray(holes)) {
holes = [ holes ]; // Make sure holes is an array
}
// Convert elements to regions
for (i = 0, l = holes.length; i < l; i++) {
holes[i] = D.getRegion(holes[i]);
}
/**
* Hide the blankets.
*/
this.hide = function () {
if (!isShowing) {
return;
}
isShowing = false;
D.setStyle(swatches, 'display', 'none');
}
/**
* Show the blankets.
*/
this.show = function () {
if (isShowing) {
return;
}
isShowing = true;
if (swatches.length > 0) {
// If we already built the collection of swatches, we just
// need to set the display to make it visible
D.setStyle(swatches, 'display', 'block');
return;
}
/*
* Attempt to cover a region. If the region intersects with one
* of the hole regions, attempt to work around the hole.
* @param {YAHOO.util.Region} r The region to attempt to cover
* @param {Array} aRegions The array of regions that don't get covered
*/
function cover(r, aRegions) {
var i,
rtop, // the region above a hole
rleft, // the region to the left of a hole
rright, // the region to the right of a hole
rbottom, // the region below a hole
swatch, // A swatch of the blanket
intersectingRegion = null;
YAHOO.log('Cover ' + r);
// Determine if this region intersects with any holes
for (i = 0, l = aRegions.length; i < l && ZBREAKER++ < 1000; i++) {
intersectingRegion = r.intersect(aRegions[i]);
if (intersectingRegion != null) {
intersectingRegion = aRegions[i];
break;
}
}
if (intersectingRegion == null) {
// Ok to box this region
// Create div to cover this region
swatch = document.createElement('div');
D.setStyle(swatch, 'background', '#000');
D.setStyle(swatch, 'opacity', 0.5);
D.setStyle(swatch, 'position', 'absolute');
D.setStyle(swatch, 'z-index', 100); // TODO: how is this determined?
D.setStyle(swatch, 'left', r.left + 'px');
D.setStyle(swatch, 'top', r.top + 'px');
D.setStyle(swatch, 'height', r.height + 'px');
D.setStyle(swatch, 'width', r.width + 'px');
document.body.appendChild(swatch);
// Record the region/blanket so we can hide it
swatches[swatches.length] = swatch;
YAHOO.log('Added blanket to region ' + r);
//alert('added');
return;
}
// If there was an intersectingRegion, define the regions around that region
// Make 4 new regions (top left right bottom) and call cover on each
// Note, need to be 1 pixel away from intersectingRegion so
// they don't intersect... need to address this somehow.
rtop = new R(r.top, r.right, intersectingRegion.top - 1, r.left);
rleft = new R(intersectingRegion.top - 1, intersectingRegion.left - 1, intersectingRegion.bottom + 1, r.left);
rright = new R(intersectingRegion.top - 1, r.right, intersectingRegion.bottom + 1, intersectingRegion.right + 1);
rbottom = new R(intersectingRegion.bottom + 1, r.right, r.bottom, r.left);
cover(rtop, aRegions);
cover(rleft, aRegions);
cover(rright, aRegions);
cover(rbottom, aRegions);
return;
}
cover(viewPortRegion, holes);
};
}
};
})();
var blanket = new FOTI.Blanket(['A', 'B', 'C']);
YAHOO.util.Event.on(['A', 'B', 'C'], 'mouseover', blanket.show);
YAHOO.util.Event.on(['A', 'B', 'C'], 'click', blanket.hide);
</script>
</body>
</html>
I approached the problem a quite differently - I'll post my partially finished prototype tomorrow
<html>
<head>
<style>
*{
border:0;
}
body{
background:#fff;
padding:0;
margin:0;
border:0;
}
#elem1{
background:#999;
margin:20px 20px 20px 100px;
padding:20px;
height:30px;
width:100px;
border:0;
}
#elem2{
background:#999;
margin:2px 20px 20px 100px;
padding:20px;
height:30px;
width:200px;
border:0;
}
.blackout{
position:absolute;
display:block;
background:#fee;
border:1px solid red;
}
</style>
<script src="mootools-1.2.1-core.js"></script>
<script src="mootools-1.2-more.js"></script>
<script>
window.addEvent('domready',function(){
var elems = $$('.h');
var hlines = new Array;
var vlines = new Array;
var shapes = new Array;
// add the top and bottom of the page
wcoords = window.getCoordinates();
hlines.push(wcoords['top']);
hlines.push(wcoords['bottom']);
vlines.push(wcoords['left']);
vlines.push(wcoords['right']);
elems.each(function(elem){
coords = elem.getCoordinates();
elem.t = coords['top'];
elem.r = coords['right'];
elem.b = coords['bottom'];
elem.l = coords['left'];
hlines.push(elem.t);
hlines.push(elem.b);
vlines.push(elem.l);
vlines.push(elem.r);
});
// remove dupes
hlines = hlines.unique().sort(sortNumber);
vlines = vlines.unique().sort(sortNumber);
// create grid
var grid = new Array()
for(var i=0;i<hlines.length-1;i++){
grid[i] = new Array();
for(var j=0;j<vlines.length-1;j++){
grid[i][j] = 'x';
}
}
// put an "o" where the holes are
elems.each(function(elem){
for(var i=0;i<grid.length;i++){
for(var j=0;j<grid[i].length;j++){
if(elem.t >= hlines[i] && elem.b <=hlines[i+1] && elem.l <= vlines[j] && elem.r >= vlines[j+1]){
grid[i][j] = 'o';
}
}
}
});
gridshow(grid);
//alert(hlines.length + ',' + grid.length);
//alert(vlines.length + ',' + grid[1].length);
// we'll leave the optimizing for later.
for(var i=0;i<grid.length;i++){
for(var j=0;j<grid[i].length;j++){
if(grid[i][j]=='x'){
var shape = {
'x':vlines[j],
'y':hlines[i],
'w':vlines[j+1] - vlines[j],
'h':hlines[i+1] - hlines[i]
};
shapes.push(shape);
//alert(shape.x +','+ shape.y+','+shape.w+','+shape.h);
}
}
}
var blanket = new Element('div',{
styles:{
'position':'absolute',
'top':'0',
'left':'0'
}
});
blanket.inject(document.body,'bottom');
shapes.each(function(shape){
//alert(shape.x +','+ shape.y+','+shape.w+','+shape.h);
var s = new Element('div',{
styles:{
'position':'absolute',
'left':shape.x,
'top':shape.y,
'height':shape.h,
'width':shape.w,
'background':'#eee',
'border':'0'
}
});
s.inject(blanket,'top');
});
});
function gridshow(grid){
var str ='';
for(var i=0;i<grid.length;i++){
for(var j=0;j<grid[i].length;j++){
str += grid[i][j];
}
str += '\n';
}
alert(str);
}
function sortNumber(a,b){return a - b;}
Array.prototype.unique = function () {
var r = new Array();
o:for(var i = 0, n = this.length; i < n; i++)
{
for(var x = 0, y = r.length; x < y; x++)
{
if(r[x]==this[i])
{
continue o;
}
}
r[r.length] = this[i];
}
return r;
}
</script>
</head>
<body>
<div id="elem1" class="h">one</div>
<div id="elem2" class="h">two</div>
<table><tr><td><a href="" class='h'>three</a></td></tr></table>
<p>lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum </p>
<p>lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum </p>
<blockquote class='h'>this is a test</blockquote>
<p>lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum </p>
<blockquote class='h'>this is a test</blockquote>
<p>lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum </p>
<p>lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum lorem ipsum </p>
<div>test </div>
<div>test </div>
<div>test </div>
</body>
</html>
