Equation to calculate intersected cells in a grid, given a selection rectangle

227 Views Asked by At

I am looking for an equation which will calculate which cells (returned either as a pure index or as a row/col) are intersected by a selection rectangle when provided with the box coordinates of each and every cell as well as the box coordinates of the selection rectangle itself.

Since this is for use in javascript programming I will describe the information available to me and thus, to the equation.

Cell coordinates, defined as:

item : {
       box_pos : {
             x : 0,
             y : 0
       },
       grid_pos : {
              row : 1,
              column : 1
       }
 }

I have this data for each and ever cell in the grid. It contains the x/y position of the top-left corner as well as the row/column positions.

NOTE: The cells are of fixed size 201 height by 221 width

I also have the coordinates of the selection box/marquee defined like so:

    selectioncoords : {
                        topleft : {
                            x : 0,
                            y : 0
                        },
                        topright : {
                            x : 0,
                            y : 0
                        },
                        bottomleft : {
                            x : 0,
                            y : 0
                        },
                        bottomright : {
                            x : 0,
                            y : 0
                        },
                        width : 0,
                        height : 0
 }

I also have the width of the grid in pixels. Lets call this gridwidth as well as the total number of columns, columncount and total cells, cellcount

Now I know that this is heavily programming related but I am actually after an equation specifically, rather than code. Currently I can achieve the correct behaviour by looping through all cells and checking to see if they fit within the selection box's coordinates. This however is resource heavy when dealing with huge numbers of cells.

Is there any way given the selection box coords, cell size, columncount, grid width and cell coordinates, to ascertain which cells would be intersected by the selection box via a mathematical equation. Removing the need to loop through thousands of cells continuously.

Thanks in advance.