5

我正在编写自己的拖放文件管理器。这包括一个 javascript 选取框，当它处于活动状态时计算相交的元素（文件）并通过向它们添加类来选择它们。

我目前在 mousemove 处理程序期间执行检查，循环遍历元素坐标数组并确定哪些坐标与拖放选择框相交。

该函数当前如下所示：

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();
           }
       }
  }
},

上面的代码中有很多脏逻辑，确保只有在选择更改时才操作 DOM。这与问题无关，可以排除。重要的部分是检查元素坐标与选取框坐标的交集逻辑。

另请注意，项目尺寸固定为201px 宽 x 221px 高。

我已经对此进行了测试，并且一切正常，但是我需要支持潜在的数千个文件，这意味着在某些时候我们将开始看到 UI 性能下降。

我想知道是否无论如何都可以在不遍历每个元素的坐标的情况下执行交叉点检测。

在任何给定时间，选取框的坐标定义如下：

 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
                }

存储在 self.cache.items 数组中的每个项目的坐标定义如下：

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


    }

因此，可用的信息将始终是实际网格位置（行/列）以及物理项目位置（网格内以像素为单位的左侧和顶部偏移量）。

总而言之，问题是，是否无论如何都可以从上面定义的一组选取框坐标中检测项目交集，而无需在每次触发 mousemove 事件时循环遍历整个项目坐标数组？

提前感谢您的帮助。

4

4 回答 4

3

以下内容取决于具有所述尺寸的锁定网格。

您正在将鼠标定义的矩形与具有静态边缘尺寸的网格进行比较。因此，给定 x 坐标或 ay 坐标，您应该能够很容易地得出坐标落入哪一列或哪一行（分别）。

当用户启动选择框时，抓住 x 和 y，然后找到开始的行/列。当鼠标在拉动选择框的同时移动时，您会找到（然后更新）完成的行/列。选择该框定义的行和该框（包括）定义的列中的任何内容。如果您随后根据行和列将可选元素保留在二维数组中，您应该能够以这种方式获取您想要的元素。

请注意，这有多少效率更高（或更低）取决于您预期的选择框与总尺寸相比的大小，以及您希望填充网格的程度。当然，如果平均用例是一次选择一半左右的对象，那么您无法有效减少每次必须查看的对象数量。

此外，虽然它很笨拙，但您可以让 mousemove 处理程序不会每次都触发。让它在更新之间暂停一点会大大降低这个特定功能的响应能力，但会显着减少使用的资源量。

于 2013-03-27T21:06:14.357 回答
2

您可以通过为网格中的每个项目编制索引来限制检查的范围，根据需要经常而不是更频繁。您可以使用网格为您提供X、Y 坐标附近或可能在 X1、Y2、X1、Y2 范围内的元素列表。

为了让你开始...

var Grid = function(pixelWidth, pixelHeight, boxSize) {

  this.cellsIn = function(x1, y1, x2, y2) {
    var rv = [];
    for (var x = x1; x < x2; x += boxSize) {
      for (var y = y1; y < y2; y += boxSize) {
        var gx = Math.ceil(x/boxSize);
        var gy = Math.ceil(y/boxSize);
        rv.push(this.cells[gx][gy]);
      }
    }
    return rv;
  } // cellsIn()


  this.add = function(x1, y1, x2, y2, o) {
    var cells = this.cellsIn(x1, y1, x2, y2);
    for (var i in cells) {
      cells[i].push(o);
    }
  } // add()


  this.get = function(x1, y1, x2, y2) {
    var rv = [];
    var rv_index = {};
    var cells = this.cellsIn(x1, y1, x2, y2);
    for (var i in cells) {
      var cell = cells[i];
      for (var oi in cell) {
        if (!rv_index[cell[oi]]) {
          rv_index[cell[oi]] = 1;
          rv.push(cell[oi]);
        }
      }
    }
    return rv;
  } // get()


  this.cells = [];
  for (var x = 0; x < Math.ceil(pixelWidth/boxSize); x++) {
    this.cells[x] = [];
    for (var y = 0; y < Math.ceil(pixelHeight/boxSize); y++) {
      this.cells[x][y] = [];
    }
  }

};

因此，不是遍历所有可能的对象，无论它们是什么，而是遍历给定坐标附近或可能位于给定坐标中的所有对象。

这要求您在项目坐标更改时维护/重新索引网格。您可能希望向上述（或类似的）Grid 类添加一些功能来修改/移动现有对象。但是，据我所知，这种索引是在“空间”中索引对象的最佳方式，即使不是唯一的方式。

免责声明：上面的代码未经测试。但是，我有类似的代码。在此处查看 DemoGrid 函数类：http ://www.thepointless.com/js/ascii_monsters.js

我的 DemoGrid 的功能是相似的（据我记得，已经有一段时间了），但接受x, y, radius作为参数。同样值得注意的是，每次事件触发时，我的鼠标事件都不会触及网格。检查受游戏/主循环的速率限制。

于 2013-03-27T21:10:12.233 回答
2

有几种方法可以解决这个问题。这是一个。首先，您需要某种组织结构中的项目，您可以按行和列快速查找。您可以使用二维数组，或者为简单起见，我将使用哈希表。您可以在创建 的同时self.cache.items或稍后执行此操作，如下所示：

var cacheLookup = {};

function initCacheLookup() {
    var items = self.cache.items;
    for( var i = 0, n = items.length;  i < n;  i++ ) {
        var item = items[i];
        var key = [ item.grid_pos.row, item.grid_pos.column ].join(',');
        cacheLookup[key] = item;
    }
}

然后，当您想要获取与矩形相交的项目时，您可以执行以下操作：

var itemWidth = 201, itemHeight = 221;

var tl = selectioncoords.topleft, br = selectioncoords.bottomright;
var left = Math.floor( tl.x / itemWidth ) + 1;
var right = Math.floor( br.x / itemWidth ) + 1;
var top = Math.floor( tl.y / itemHeight ) + 1;
var bottom = Math.floor( br.y / itemHeight ) + 1;

var selecteditems = [];
for( var row = top;  row <= bottom;  row++ ) {
    for( var col = left;  col <= right;  col++ ) {
        var key = [ row, col ].join(',');
        var item = cacheLookup[key];
        if( item ) {
            selecteditems.push( item );
        }
    }
}
// Now selecteditems has the items intersecting the rectangle

这里可能有一两个错误，但这应该很接近。

好吧，正如我所说，这是一种方法。它有一个可能有趣的属性，即它不依赖于self.cache.items数组中项目的顺序。但是那个cacheLookup哈希表听起来可能不是最有效的解决方案。

让我猜一猜：该数组不是已经按行和列的正确顺序排列（反之亦然）吗？例如，如果您的网格是四宽，那么第一行将是数组元素 0-3，第二行是 4-7，第三行是 8-11，等等。或者它可以是类似的排列方式沿着列向下排列。

假设它是按行顺序排列的，那么您根本不需要哈希表。该initCacheLookup()功能消失了，而是搜索代码如下所示：

var nCols = 4/*whatever*/;  // defined somewhere else
var itemWidth = 201, itemHeight = 221;

var tl = selectioncoords.topleft, br = selectioncoords.bottomright;
var left = Math.floor( tl.x / itemWidth );
var right = Math.floor( br.x / itemWidth );
var top = Math.floor( tl.y / itemHeight ) * nCols;
var bottom = Math.floor( br.y / itemHeight ) * nCols;

var items = self.cache.items;
var selecteditems = [];
for( var iRow = top;  iRow <= bottom;  iRow += nCols ) {
    for( var col = left;  col <= right;  col++ ) {
        var index = iRow + col;
        if( index < items.length ) {
            selecteditems.push( items[index] );
        }
    }
}
// Now selecteditems has the items intersecting the rectangle

这段代码会快一点，也更简单。而且它完全不依赖于item.box_posand item.grid_pos。您可能根本不需要这些数据字段，因为它们很容易从项目索引、网格列数以及项目高度和宽度计算出来。

一些相关说明：

不要硬编码201和221在代码中。仅将它们存储在变量中一次，然后在需要项目高度和宽度时使用这些变量。

您的数据结构中有很多重复。我建议您无情地消除所有重复的数据，除非有特殊需要。具体来说：

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
}

这里一半以上的数据是重复的或可以计算的。这就是你所需要的：

selectioncoords: {
    left: 0,
    right: 0,
    top: 0,
    bottom: 0
}

我提出这个问题的原因是在处理代码时有点令人困惑：“我想要左边缘。我是从topleft.x还是得到它bottomleft.x？它们真的像看起来一样吗？我该如何选择？”

此外，如上所述，如果项目存储在顺序数组中，则可能根本不需要item.box_posand 。item.grid_pos如果需要它们，您可以只存储一个并从中计算另一个，因为两者之间存在直接关系：

box_pos.x === ( grid_pos.column - 1 ) * itemWidth
box_pos.y === ( grid_pos.row - 1 ) * itemHeight
于 2013-03-27T21:15:11.653 回答
0

如果系统设置为

  • self.cache.items 从左到右，从上到下排序
    • (0,0),(1,0),(2,0),(0,1),(1,1),(1,2),(0,2),(1,2),(2 ,2)
  • 每个空间都有一个项目
    • 好 - (0,0),(1,0),(2,0),(0,1),(1,1),(1,2),(0,2),(1,2), (2,2)
    • 坏 - (0,0),(2,0)(1,2),(1,3),(2,1),(2,3)
  • 我们需要知道总列数。

所以代码让你开始。

// Some 'constants' we'll need.
number_of_columns = 4;
item_width = 201;
item_height = 221;

// First off, we are dealing with a grid system, 
// so that means that if given the starting x and y of the marquee,
// we can determine which element in the cache to start where we begin.
top_left_selected_index = Math.floor(selectioncoords.topleft.x / item_width) + (Math.floor(selectioncoords.topright.y / item_height) * number_of_columns );

// Now, because the array is in order, and there are no empty cache points, 
// we know that the lower bound of the selected items is `top_left_selected_index`
// so all we have to do is walk the array to grab the other selected.

number_columns_selected = (selectioncoords.bottomright.x - selectioncoords.topleft.x) / item_width;
// if it it doesn't divide exactly it means there is an extra column selected
if((selectioncoords.bottomright.x - selectioncoords.topleft.x) % item_width > 0){
  number_columns_selected += 1;
}

// if it it doesn't divide exactly it means there is an extra column selected
number_rows_selected = (selectioncoords.bottomright.y - selectioncoords.topleft.y) / item_height;
if((selectioncoords.bottomright.y - selectioncoords.topleft.y) % item_height > 0){
  number_rows_selected += 1;
}

// Outer loop handles the moving the pointer in terms of the row, so it
// increments by the number of columns.
// EX: Given my simple example array, To get from (1,0) to (1,1) 
// requires an index increase of 3
for(i=0; i < number_rows_selected; i++){
  // Inner loop marches through the the columns, so it is just one at a time.
  // Added j < number_of_columns in case your marquee stretches well past your content
  for(j=0; j < number_columns_selected && j < number_of_columns; j++){
    // Do stuff to the selected items.
    self.cache.items[top_left_selected_index + (i * number_of_columns) + j];
  }
}
于 2013-03-27T21:49:16.303 回答