How to find selected elements within a javascript marquee selection box without using a loop?

Question

I am writing my own drag and drop file manager. This includes a javascript marquee selection box which when active calculates the elements (files) that are intersected and selects them by adding a class to them.

I currently perform the check during a mousemove handler, loop through an array of element coordinates and determine which ones are intersected by the drag and drop selection box.

The function currently looks like this:

selectItems : function(voidindex){

                        var self = this;
                        var coords = self.cache.selectioncoords;

    for(var i=0, len = self.cache.items.length; i<len; i++){
           var item = self.cache.items[i];
           var itemcoords = item.box_pos;

           if(coords.topleft.x < (itemcoords.x+201) && coords.topright.x > itemcoords.x && coords.topleft.y < (itemcoords.y+221) && coords.bottomleft.y > itemcoords.y){
               if(!item.selected){
                  item.selected = true;
                  item.html.addClass('selected').removeClass('activebutton');
                  self.cache.selecteditems.push(i);
                  self.setInfo();
               }
           }
           else{
               if(item.selected){
                  item.selected = false;
                  if(!voidindex || voidindex !== i){
                      item.html.removeClass('selected');
                  }
                  var removeindex = self.cache.selecteditems.indexOf(i);
                  self.cache.selecteditems.splice(removeindex, 1);
                  self.setInfo();
           }
       }
  }
},

There is lots of dirty logic in the code above which ensures that the DOM is only manipulated when the selection changes. This is not relevant to the question and can be exluded. The important part is the intersection logic which checks the coordinates of the element versus the coordinates of the marquee selection box.

Also please note that the item dimensions are fixed at 201px width by 221px height.

I have tested this and all works perfectly, however I have the need to support potentially thousands of files which would mean that at some point we will start seeing UI performance decrease.

I would like to know if there is anyway to perform intersection detection without looping through the coordinates of each element.

The coordinates of the marquee box are defined as follows at any given time:

 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
                }

And the coordinates of each item, stored in the self.cache.items array are defined as follows:

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


    }

So the information available will always be the actual grid position (row/column) as well as the physical item position (left and top offsets in pixels within the grid).

So to summarize, the question is, is there anyway to detect item intersection from a set of marquee selection box coordinates as defined above without looping through the whole array of item coordinates every time the mousemove event fires?

Thanks in advance for any help.

Answer 1

The following depends upon a locked grid with the dimensions as described.

You are comparing a mouse-defined rectangle against a grid with static edge sizes. Thus, given an x coordinate or a y coordinate, you should be able to derive pretty easily which column or row (respectively) the coordinate falls into.

When the user starts the select box, grab that x and y, and find the row/column of the start. When the mouse moves while pulling the select box, you find (and then update) the row/column of the finish. anything that is both within the rows defined by that box and within the columns defined by that box (inclusive) is selected. If you then keep your selectable elements in a two-dimensional array according to rows and columns, you should be able to just grab the ones you want that way.

Mind, how much more (or less) efficient this is depends on the size of your expected selection boxes as compared to the total size, and the degree to which you expect the grid to be populated. Certainly, if the average use case is selecting half or so of the objects at a time, there's not a whole lot you can do to cut down efficiently on the number of objects you have to look at each time.

Also, though it is kludgy, you can have the mousemove handler not fire every time. Letting it pause a bit between updates will reduce the responsiveness of this particular function a fair bit, but it'll cut down significantly on the amount of resources that are used.