Connect side-by-side Rects to one big Rect

Question

I have a problem with the following Game-Maps:

I want to save all the land area (near yellow) in an array, so that the computer later knows whether a click by the user is on the water (x / y coordinate of the mouse pointer not in the array) or in the country (x / y coordinate the cursor not in the array) . I've already made (basic visual representation): As can be seen, the land area is covered with equally large rectangles, which are stored as follows in the array:

{x:upper left corner - X-postion, y: upper left corner - Ypostion, x1:width of the rect, y1: height of the rect}
example: {x:0, y:0, x1:3, y2: 2}

These obejcts are all stored in one big array. But it takes too long to determine if a point in the array (land area) or not in the array (water area) is. (Takes 45 milliseconds) I would now like to merge these small individual rectangles, so larger rectangles formed, which can be compared with the mouse postion faster. Like this handmade example: If its possible these little rectangle-objects should be add to one big rect (like the green or brown one). Til yet I couldn't find anything to do this, so that I hope you can help me. There is one more problem: The array, where I saved all the small rects is very big (over 100.000 Elements). They all are stored like this:

[{x:0, y: 0, x1:3, y1:2},{x:0, y: 2, x1:3, y1:2},{x:0, y: 4, x1:3, y1:2}]

It's not a problem if a solution takes more than 10 Minutes or something like that.

You are asking for a bit rate reduction (encoding) algorithm. Which can be done in many ways including the handmade one just like you have started doing and it's still legit since you will do it only once and will probably take much shorter than thinking and implementing the best algorithm. — Redu, May 01 '16 at 17:52
@Naresh Teli I did image processing based on the colors to get the red marked rectangles. Or what do you mean? — , May 01 '16 at 18:19
it give you an idea what i want to say http://stackoverflow.com/questions/6735470/get-pixel-color-from-canvas-on-mouseover — Naresh Teli, May 01 '16 at 18:27
If you stored the map as a 2D array of booleans `isLand`, a click on (x,y) would have an immediate answer in `isLand[x][y]`. Storing the map as a list of coordinates of squares isn't efficient, at least not for checking whether certain coordinates are on land or not. — m69's been on strike for years, May 01 '16 at 18:47
I think your problem can be restated as the problem in this question: http://stackoverflow.com/questions/8035960/combine-smaller-rectangles-into-larger-ones — Dandelion, May 01 '16 at 19:18
You are about to find a set of rectangles covering a rectilinear polygon. Finding a set with optimum number of rectangles is np-hard. You can find some approximate algorithms in wikipedia: https://en.wikipedia.org/wiki/Polygon_covering#Covering_a_rectilinear_polygon_with_rectangles — Dandelion, May 01 '16 at 19:36

markE · Accepted Answer · 2016-05-02T03:31:09.993

Here's an implementation of @m69's idea.

Create an array representing every pixel's island / isNotLand status.

You can use getImageData to fetch every pixel's RGBA info. The yellowish land has a high red value while ocean has a low red value, so use the red value to determine land vs ocean. Put those isLand/isNotLand values into an array (land).

var land;
var data=context.getImageData(0,0,canvas.width,canvas.height).data;
land=new Array(data.length/4);
for(var i=0;i<data.length;i+=4){
    var red=data[i];
    land[i/4]=(red>200)?true:false;
}

Then you can test if the mouse is over land or ocean efficiently like this:

function isLand(x,y){
    return(land[mouseY*canvas.width+mouseX]);    
}

Example code and a Demo:

var canvas=document.getElementById("canvas");
var ctx=canvas.getContext("2d");
var cw=canvas.width;
var ch=canvas.height;
function reOffset(){
    var BB=canvas.getBoundingClientRect();
    offsetX=BB.left;
    offsetY=BB.top;        
}
var offsetX,offsetY;
reOffset();
window.onscroll=function(e){ reOffset(); }
window.onresize=function(e){ reOffset(); }

var isDown=false;
var startX,startY;

var land;
var img=new Image();
img.crossOrigin='anonymous';
img.onload=start;
img.src="https://dl.dropboxusercontent.com/u/139992952/multple/map2.jpg";
function start(){   
    cw=canvas.width=img.width;
    ch=canvas.height=img.height;

    ctx.drawImage(img,0,0);

    var data=ctx.getImageData(0,0,cw,ch).data;
    land=new Array(data.length/4);
    for(var i=0;i<data.length;i+=4){
        var red=data[i];
        land[i/4]=(red>200)?true:false;
    }
    
    $("#canvas").mousemove(function(e){handleMouseMove(e);});

}

function isLand(x,y){
    return(land[mouseY*cw+mouseX]);    
}

function handleMouseMove(e){
  // tell the browser we're handling this event
  e.preventDefault();
  e.stopPropagation();
  // is land under mouse?
  mouseX=parseInt(e.clientX-offsetX);
  mouseY=parseInt(e.clientY-offsetY);
  if(isLand(mouseX,mouseY)){
      ctx.fillStyle='red';
      ctx.fillRect(mouseX,mouseY,1,1);
  }else{
      ctx.fillStyle='blue';
      ctx.fillRect(mouseX,mouseY,1,1);
  }
}

body{ background-color: ivory; }
#canvas{border:1px solid red; }

<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
<h4>Move mouse over map.<br>Land draws a red rect. Ocean draws a blue rect</h4>
<canvas id="canvas" width=300 height=300></canvas>

Connect side-by-side Rects to one big Rect

1 Answers1