javascript - Algorithm - locating enough space to draw a rectangle given the x and y axis of all other rectangles -
every rectangle has x , y coordinates, width , height.
the total width of screen maxwidth , total height maxheight.
i have array containg drawn rectangles.
i working on web app users drawing rectangles on screen using thier mouse. using #javascript draw on canvas element.
the challenge rectangles must not intersect @ given point.
i trying avoid kind of case:
or this:
this how output aiming should like:
what need algorithm (preferably in javascript) can locating enough space draw rectangle knowing axis, height , width.
bm67 box packing.
this method use pack rectangles. made myself create sprite sheets.
how works.
you maintain 2 arrays, 1 holds rectangles of available spaces (space array), , other rectangles have placed.
you start adding space array rectangle covers whole area filled. rectangle represents available space.
when add rectangle fit search available space rectangles rectangle fit new rectangle. if can not find rectangle bigger or sane size 1 want add there no room.
once have found place put rectangle, check available space rectangles see if of them overlap new added rectangle. if overlap slice along top, bottom, left , right, resulting in 4 new space rectangles. there optimisation when keep number of rectangles down work without optimisations.
it's not complicated , reasonably efficient compared other methods. particularly when space starts run low.
example
below demo of filling canvas random rectangles. it's on animation loop show process, slowed down.
gray boxes ones fit. red show current spacer boxes. each box has 2 pixel margin. see top of code demo constants.
click canvas restart.
const boxes = []; // added boxes const spaceboxes = []; // free space boxes const space = 2; // space between boxes const minw = 4; // min width , height of boxes const minh = 4; const maxs = 50; // max width , height // demo const addcount = 2; // number add per render cycle const ctx = canvas.getcontext("2d"); canvas.width = canvas.height = 1024; // create random integer const randi = (min, max = min + (min = 0)) => (math.random() * (max - min) + min) | 0; // itterates array const eachof = (array, cb) => { var = 0; const len = array.length; while (i < len && cb(array[i], i++, len) !== true ); }; // resets boxes function start(){ boxes.length = 0; spaceboxes.length = 0; spaceboxes.push({ x : space, y : space, w : canvas.width - space * 2, h : canvas.height - space * 2, }); } // creates random box without position function createbox(){ return { w : randi(minw,maxs), h : randi(minh,maxs) } } // cuts box make space cutter (cutter box) function cutbox(box,cutter){ var b = []; // cut left if(cutter.x - box.x - space > minw){ b.push({ x : box.x, y : box.y, w : cutter.x - box.x - space, h : box.h, }) } // cut top if(cutter.y - box.y - space > minh){ b.push({ x : box.x, y : box.y, w : box.w, h : cutter.y - box.y - space, }) } // cut right if((box.x + box.w) - (cutter.x + cutter.w + space) > space + minw){ b.push({ x : cutter.x + cutter.w + space, y : box.y, w : (box.x + box.w) - (cutter.x + cutter.w + space), h : box.h, }) } // cut bottom if((box.y + box.h) - (cutter.y + cutter.h + space) > space + minh){ b.push({ x : box.x, y : cutter.y + cutter.h + space, w : box.w, h : (box.y + box.h) - (cutter.y + cutter.h + space), }) } return b; } // index of spacer box closest in size box function findbestfitbox(box){ var smallest = infinity; var boxfound; eachof(spaceboxes,(sbox,index)=>{ if(sbox.w >= box.w && sbox.h >= box.h){ var area = sbox.w * sbox.h; if(area < smallest){ smallest = area; boxfound = index; } } }) return boxfound; } // returns array of boxes touching box // removes boxes spacer array function gettouching(box){ var b = []; for(var = 0; < spaceboxes.length; i++){ var sbox = spaceboxes[i]; if(!(sbox.x > box.x + box.w + space || sbox.x + sbox.w < box.x - space || sbox.y > box.y + box.h + space || sbox.y + sbox.h < box.y - space )){ b.push(spaceboxes.splice(i--,1)[0]) } } return b; } // adds space box spacer array. // check if insid, small, or can joined befor adding. // not add if not needed. function addspacerbox(box){ var dontadd = false; // small? if(box.w < minw || box.h < minh){ return } // same or inside eachof(spaceboxes,sbox=>{ if(box.x >= sbox.x && box.x + box.w <= sbox.x + sbox.w && box.y >= sbox.y && box.y + box.h <= sbox.y + sbox.h ){ dontadd = true; return true; } }) if(!dontadd){ var join = false; // check if can joinded eachof(spaceboxes,sbox=>{ if(box.x === sbox.x && box.w === sbox.w && !(box.y > sbox.y + sbox.h || box.y + box.h < sbox.y)){ join = true; var y = math.min(sbox.y,box.y); var h = math.max(sbox.y + sbox.h,box.y + box.h); sbox.y = y; sbox.h = h-y; return true; } if(box.y === sbox.y && box.h === sbox.h && !(box.x > sbox.x + sbox.w || box.x + box.w < sbox.x)){ join = true; var x = math.min(sbox.x,box.x); var w = math.max(sbox.x + sbox.w,box.x + box.w); sbox.x = x; sbox.w = w-x; return true; } }) if(!join){ spaceboxes.push(box) }// add spacer array } } // adds box finding space fit. function locatespace(box){ if(boxes.length === 0){ // first box can go in top left box.x = space; box.y = space; boxes.push(box); var sb = spaceboxes.pop(); spaceboxes.push(...cutbox(sb,box)); }else{ var bf = findbestfitbox(box); // best fit space if(bf !== undefined){ var sb = spaceboxes.splice(bf,1)[0]; // remove best fit spacer box.x = sb.x; // use position box box.y = sb.y; spaceboxes.push(...cutbox(sb,box)); // slice spacer box , add slices spacer array boxes.push(box); // add box var tb = gettouching(box); // find touching spacer boxes while(tb.length > 0){ // , slice them if needed eachof(cutbox(tb.pop(),box),b => addspacerbox(b)); } } } } // draws box array function drawboxes(list,col,col1){ eachof(list,box=>{ if(col1){ ctx.fillstyle = col1; ctx.fillrect(box.x+ 1,box.y+1,box.w-2,box.h - 2); } ctx.fillstyle = col; ctx.fillrect(box.x,box.y,box.w,1); ctx.fillrect(box.x,box.y,1,box.h); ctx.fillrect(box.x+box.w-1,box.y,1,box.h); ctx.fillrect(box.x,box.y+ box.h-1,box.w,1); }) } // show process in action ctx.clearrect(0,0,canvas.width,canvas.height); var count = 0; var handle = settimeout(doit,10); start() function doit(){ ctx.clearrect(0,0,canvas.width,canvas.height); for(var = 0; < addcount; i++){ var box = createbox(); locatespace(box); } drawboxes(boxes,"black","#ccc"); drawboxes(spaceboxes,"red"); if(count < 1214 && spaceboxes.length > 0){ count += 1; handle = settimeout(doit,10); } } canvas.onclick = function(){ cleartimeout(handle); start(); handle = settimeout(doit,10); count = 0; }canvas { border : 2px solid black; }<canvas id="canvas"></canvas>update
improving on above algorithm.
- turned algorithm object
- improved speed finding better fitting spacer via weighting fit on aspect ratio
- added
placebox(box)function adds box without checking if fits. placed @box.x,box.ycoordinates
see code example below on usage.
example
the example same above example have added randomly place boxes before fitting boxes.
demo displays boxes , spacer boxes goes show how works. click canvas restart. hold [shift] key , click canvas restart without displaying intermediate results.
pre placed boxes blue. fitted boxes gray. spacing boxes red , overlap.
when holding shift fitting process stopped @ first box tat not fit. red boxes show area available unused.
when showing progress function keep adding boxes ignoring non fitting boxes until out of room.
const minw = 4; // min width , height of boxes const minh = 4; const maxs = 50; // max width , height const space = 2; const numberboxestoplace = 20; // number of boxes place befor fitting const fixedboxcolor = "blue"; // demo const addcount = 2; // number add per render cycle const ctx = canvas.getcontext("2d"); canvas.width = canvas.height = 1024; // create random integer randi(n) return random val 0-n randi(n,m) returns random int n-m, , iterator can break const randi = (min, max = min + (min = 0)) => (math.random() * (max - min) + min) | 0; const eachof = (array, cb) => { var = 0; const len = array.length; while (i < len && cb(array[i], i++, len) !== true ); }; // creates random box. if place true box gets x,y position , flaged fixed function createbox(place){ if(place){ const box = { w : randi(minw*4,maxs*4), h : randi(minh*4,maxs*4), fixed : true, } box.x = randi(space, canvas.width - box.w - space * 2); box.y = randi(space, canvas.height - box.h - space * 2); return box; } return { w : randi(minw,maxs), h : randi(minh,maxs), } } //====================================================================== // boxarea object using bm67 box packing algorithum // https://stackoverflow.com/questions/45681299/algorithm-locating-enough-space-to-draw-a-rectangle-given-the-x-and-y-axis-of // please leave , above 2 lines copies of code. //====================================================================== // // usage // var area = new boxarea({ // x: ?, // x,y,width height of area // y: ?, // width: ?, // height : ?. // space : ?, // optional default = 1 sets spacing between boxes // minw : ?, // optional default = 0 sets in width of expected box. note optimisation can add smaller may fail // minh : ?, // optional default = 0 sets in height of expected box. note optimisation can add smaller may fail // }); // // add box @ location. not checked fit or overlap // area.placebox({x : 100, y : 100, w ; 100, h :100}); // // tries fit box. if box not fit returns false // if(area.fitbox({x : 100, y : 100, w ; 100, h :100})){ // box added // // resets boxarea removing boxes // area.reset() // // check if area full // area.isfull(); // returns true if there no room of more boxes. // // can check if box can fit @ specific location // area.isboxtouching({x : 100, y : 100, w ; 100, h :100}, area.boxes)){ // box touching box // // list of spacer boxes. note copy of array, changing not effect functionality of boxarea // const spacerarray = area.getspacers(); // // use max min box size fit // // const maxwidththatfits = spacerarray.sort((a,b) => b.w - a.w)[0]; // const minheightthatfits = spacerarray.sort((a,b) => a.h - b.h)[0]; // const minareathatfits = spacerarray.sort((a,b) => (a.w * a.h) - (b.w * b.h))[0]; // // following properties available // area.boxes // array of boxes have been added // x,y,width,height // area boxes fitted const boxarea = (()=>{ const defaultsettings = { minw : 0, // min expected size of box minh : 0, space : 1, // spacing between boxes }; const eachof = (array, cb) => { var = 0; const len = array.length; while (i < len && cb(array[i], i++, len) !== true ); }; function boxarea(settings){ settings = object.assign({},defaultsettings,settings); this.width = settings.width; this.height = settings.height; this.x = settings.x; this.y = settings.y; const space = settings.space; const minw = settings.minw; const minh = settings.minh; const boxes = []; // added boxes const spaceboxes = []; this.boxes = boxes; // cuts box make space cutter (cutter box) function cutbox(box,cutter){ var b = []; // cut left if(cutter.x - box.x - space >= minw){ b.push({ x : box.x, y : box.y, h : box.h, w : cutter.x - box.x - space, }); } // cut top if(cutter.y - box.y - space >= minh){ b.push({ x : box.x, y : box.y, w : box.w, h : cutter.y - box.y - space, }); } // cut right if((box.x + box.w) - (cutter.x + cutter.w + space) >= space + minw){ b.push({ y : box.y, h : box.h, x : cutter.x + cutter.w + space, w : (box.x + box.w) - (cutter.x + cutter.w + space), }); } // cut bottom if((box.y + box.h) - (cutter.y + cutter.h + space) >= space + minh){ b.push({ w : box.w, x : box.x, y : cutter.y + cutter.h + space, h : (box.y + box.h) - (cutter.y + cutter.h + space), }); } return b; } // index of spacer box closest in size , aspect box function findbestfitbox(box, array = spaceboxes){ var smallest = infinity; var boxfound; var aspect = box.w / box.h; eachof(array, (sbox, index) => { if(sbox.w >= box.w && sbox.h >= box.h){ var area = ( sbox.w * sbox.h) * (1 + math.abs(aspect - (sbox.w / sbox.h))); if(area < smallest){ smallest = area; boxfound = index; } } }) return boxfound; } // exposed helper function // returns true if box touching boxes in array // else return false this.isboxtouching = function(box, array = []){ for(var = 0; < array.length; i++){ var sbox = array[i]; if(!(sbox.x > box.x + box.w + space || sbox.x + sbox.w < box.x - space || sbox.y > box.y + box.h + space || sbox.y + sbox.h < box.y - space )){ return true; } } return false; } // returns array of boxes touching box // removes boxes array function gettouching(box, array = spaceboxes){ var boxes = []; for(var = 0; < array.length; i++){ var sbox = array[i]; if(!(sbox.x > box.x + box.w + space || sbox.x + sbox.w < box.x - space || sbox.y > box.y + box.h + space || sbox.y + sbox.h < box.y - space )){ boxes.push(array.splice(i--,1)[0]) } } return boxes; } // adds space box spacer array. // check if inside, small, or can joined befor adding. // not add if not needed. function addspacerbox(box, array = spaceboxes){ var dontadd = false; // box to0 small? if(box.w < minw || box.h < minh){ return } // box same or inside box eachof(array, sbox => { if(box.x >= sbox.x && box.x + box.w <= sbox.x + sbox.w && box.y >= sbox.y && box.y + box.h <= sbox.y + sbox.h ){ dontadd = true; return true; // exits eachof (like break statement); } }) if(!dontadd){ var join = false; // check if can joined eachof(array, sbox => { if(box.x === sbox.x && box.w === sbox.w && !(box.y > sbox.y + sbox.h || box.y + box.h < sbox.y)){ join = true; var y = math.min(sbox.y,box.y); var h = math.max(sbox.y + sbox.h,box.y + box.h); sbox.y = y; sbox.h = h-y; return true; // exits eachof (like break statement); } if(box.y === sbox.y && box.h === sbox.h && !(box.x > sbox.x + sbox.w || box.x + box.w < sbox.x)){ join = true; var x = math.min(sbox.x,box.x); var w = math.max(sbox.x + sbox.w,box.x + box.w); sbox.x = x; sbox.w = w-x; return true; // exits eachof (like break statement); } }) if(!join){ array.push(box) }// add spacer array } } // adds box finding space fit. // returns true if box has been added // returns false if there no room. this.fitbox = function(box){ if(boxes.length === 0){ // first box can go in top left box.x = space; box.y = space; boxes.push(box); var sb = spaceboxes.pop(); spaceboxes.push(...cutbox(sb,box)); }else{ var bf = findbestfitbox(box); // best fit space if(bf !== undefined){ var sb = spaceboxes.splice(bf,1)[0]; // remove best fit spacer box.x = sb.x; // use position box box.y = sb.y; spaceboxes.push(...cutbox(sb,box)); // slice spacer box , add slices spacer array boxes.push(box); // add box var tb = gettouching(box); // find touching spacer boxes while(tb.length > 0){ // , slice them if needed eachof(cutbox(tb.pop(),box),b => addspacerbox(b)); } } else { return false; } } return true; } // adds box @ location box.x, box.y // not check if can fit or overlap. this.placebox = function(box){ boxes.push(box); // add box var tb = gettouching(box); // find touching spacer boxes while(tb.length > 0){ // , slice them if needed eachof(cutbox(tb.pop(),box),b => addspacerbox(b)); } } // returns copy of spacer array this.getspacers = function(){ return [...spaceboxes]; } this.isfull = function(){ return spaceboxes.length === 0; } // resets boxes this.reset = function(){ boxes.length = 0; spaceboxes.length = 0; spaceboxes.push({ x : this.x + space, y : this.y + space, w : this.width - space * 2, h : this.height - space * 2, }); } this.reset(); } return boxarea; })(); // draws box array function drawboxes(list,col,col1){ eachof(list,box=>{ if(col1){ ctx.fillstyle = box.fixed ? fixedboxcolor : col1; ctx.fillrect(box.x+ 1,box.y+1,box.w-2,box.h - 2); } ctx.fillstyle = col; ctx.fillrect(box.x,box.y,box.w,1); ctx.fillrect(box.x,box.y,1,box.h); ctx.fillrect(box.x+box.w-1,box.y,1,box.h); ctx.fillrect(box.x,box.y+ box.h-1,box.w,1); }) } // show process in action ctx.clearrect(0,0,canvas.width,canvas.height); var count = 0; var failedcount = 0; var timeouthandle; var addquick = false; // create new box area const area = new boxarea({x : 0, y : 0, width : canvas.width, height : canvas.height, space : space, minw : minw, minh : minh}); // fit boxes until box cant fit or count on count limit function doit(){ ctx.clearrect(0,0,canvas.width,canvas.height); if(addquick){ while(area.fitbox(createbox())); count = 2000; }else{ for(var = 0; < addcount; i++){ if(!area.fitbox(createbox())){ failedcount += 1; break; } } } drawboxes(area.boxes,"black","#ccc"); drawboxes(area.getspacers(),"red"); if(count < 5214 && !area.isfull()){ count += 1; timeouthandle = settimeout(doit,10); } } // resets area places fixed boxes , starts fitting cycle. function start(event){ cleartimeout(timeouthandle); area.reset(); failedcount = 0; for(var = 0; < numberboxestoplace; i++){ var box = createbox(true); // create fixed box if(!area.isboxtouching(box,area.boxes)){ area.placebox(box); } } if(event && event.shiftkey){ addquick = true; }else{ addquick = false; } timeouthandle = settimeout(doit,10); count = 0; } canvas.onclick = start; start();body {font-family : arial;} canvas { border : 2px solid black; } .info {position: absolute; z-index : 200; top : 16px; left : 16px; background : rgba(255,255,255,0.75);}<div class="info">click canvas reset. shift click add without showing progress.</div> <canvas id="canvas"></canvas>
Comments
Post a Comment