1

在处理草图中实现选择算法时，我循环遍历场景中的每个对象并检查它是否在鼠标单击位置的几个像素范围内。有很多物体，而且它们非常小。

正如您可以想象的那样，一旦场景充满了物体，这将变得非常繁重。有没有简单的方法可以加快搜索速度？我可以轻松地制作这个搜索二进制文件吗？我场景中的对象是点，因此多边形命中测试算法似乎不是正确的解决方案。

4

2 回答 2

2

将场景划分为桶，分为 N x 桶和 M y 桶，或者分为 N*M x*y 桶。在前一种情况下，桶存储在两个数组中（一个 x 数组和一个 y 数组）；在后一种情况下，桶存储在数组数组中（外部数组索引 x 坐标，内部数组索引 y 坐标）。在任何一种情况下，桶都存储对桶索引区域内所有点的引用；例如，点 (8, 12) 将在 x-bucket [5, 10] 和 y-bucket [10, 15] 中，否则它将在 x*y 存储桶 ([5, 10] , [10, 15])。

当查找一个点时，要么查找适当的 x 和 y 桶，要么只查找适当的 x*y 桶。在前一种情况下，取intersection(union(x-buckets), union(y-buckets))。您可能需要根据命中半径查找多个存储桶，例如，如果您正在查找半径为 2 的 x 坐标 9，那么您将需要 [5, 10] 和 [10, 15] 存储桶。

使用单独的 x 和 y 存储桶占用更少的空间（N + M 存储桶而不是 N*M 存储桶）并使索引更容易（两个单独的数组与一个嵌套数组），而 x*y 存储桶可以加快查找速度，因为您不需要采取任何固定的十字路口。

存储桶越小，数据结构占用的空间就越多，但检索到的误报就越少。理想情况下，如果您有足够的内存，则存储桶将覆盖与命中半径相同的间隔。

于 2013-05-11T23:20:14.763 回答
1

也许如果你按一个轴对数组进行排序，假设 x 你可以通过提前返回来加快速度，我在这个问题的处理论坛上从thomas.diewald得到了这个例子。它可能适合您的需要。这里只是测试的一部分（您可以查看上面链接中的完整代码）。有一个点的 ArrayList，它具有 x 和 y 字段。看一看

请注意，他正在使用返回标签。

Arrays.sort(points);

  __FIND_NEIGHBORS__:
  for (int i = 0; i < num_points; i++) {
    Point pi = points[i];

    for (int j = i+1; j < num_points; j++) {
      Point pj = points[j];

      // 1. check in x
      float dx = pj.pos.x-pi.pos.x; // always positive -> points are sorted
      if( dx > max_dist ){
        continue __FIND_NEIGHBORS__; // ... no more points within max_dist.
      }

      // 2. check in y
      float dy = Math.abs(pj.pos.y-pi.pos.y); // not always positive
      if( dy > max_dist ){
        continue;
      }  

      // 3. check, could also just draw the line here (Manhattan distance)
      if ((dx*dx+dy*dy) < max_dist_sq) { 
        drawLine(pi, pj);
        connections++;
      }
    }
  }
于 2013-05-13T15:41:32.723 回答