7

我们必须存储数千个点 (x,y,c) c 这是该点的颜色。主要与屏幕上的像素有关。我们必须执行操作：给定 x = i，我们必须改变所有 x = i 点的颜色。同样，给定 y = i，我们必须改变所有 y = i 点的颜色。

我提出了一个二维矩阵的解决方案。然后为 x 和 y 坐标分离哈希表。然后他问我更好的解决方案。我们可以使用哪些更好的数据结构组合？

4

2 回答 2

1

您不需要二维数组和单独的哈希表。如果您的数据很密集，代表所有（或大部分）矩形区域，那么 2D 数组本身就足够了。作为后续，您可以询问哪个坐标最有可能用于查找，然后构造数组以确保外部坐标是那个坐标，以便在该坐标中的查找本地化在内存中，否则您将无法做得更好。相反，对于稀疏数据，哈希表是你能做的最好的。（我假设您正在将坐标散列到点对象数组。）是否提供了有关数据性质或最有可能使用它的方式的更多信息？

于 2013-04-28T06:50:15.063 回答
1

如果没有检索到一个坐标：您可以建议散列 x,y 坐标对。Post 提出一些低碰撞的哈希，就像hash = ( y << 16 ) ^ x;.

但是您希望访问 x 或 y 的数据 wrt 值。存储点并对其有效执行操作的结构是点 QTree 或四叉树。见这里。

点四叉树是对用于表示二维点数据的二叉树的改编。它共享所有四叉树的特征，但它是一棵真正的树，因为细分的中心总是在一个点上。

点四叉树的节点类似于二叉树的节点，主要区别在于它有四个指针（每个象限一个），而不是普通二叉树中的两个（“左”和“右”） . 此外，一个键通常被分解为两部分，指的是 x 和 y 坐标。因此一个节点包含以下信息： 4个指针：quad['NW']、quad['NE']、quad['SW']和quad['SE']点；其中又包含：键；通常表示为x、y坐标值；例如一个名字

然后，您可以使用递归函数来查询 AABB 范围内的所有点。您可以调整此实现QueryRange()

class QuadTree
{
  function queryRange(AABB range)
  {
    Array of XY pointsInRange;  // Prepare an array of results

    // Check objects at this quad level
    for (int p := 0; p < points.size; p++)
    {
      if (range.containsPoint(points[p]))
        pointsInRange.append(points[p]);
    }

    pointsInRange.appendArray(northWest->queryRange(range));
    pointsInRange.appendArray(northEast->queryRange(range));
    pointsInRange.appendArray(southWest->queryRange(range));
    pointsInRange.appendArray(southEast->queryRange(range));

    return pointsInRange;
  }
}
于 2013-04-28T16:18:29.130 回答