7

何千もの点 (x,y,c) を保存する必要があります。ここで c はその点の色です。主に画面上のピクセルに関連しています。操作を実行する必要があります。x = i が与えられた場合、x = i を持つすべてのポイントの色を変更する必要があります。同様に、y = i が与えられた場合、y = i を持つすべての点の色を変更する必要があります。

2D-matrix のソリューションを提案しました。次に、x 座標と y 座標のハッシュ テーブルを分離します。それから彼は私にもっと良い解決策を求めました。どのようなデータ構造のより良い組み合わせを使用できますか?

4

2 に答える 2

1

1 つの座標を取得できない場合: 座標の x、y ペアのハッシュを提案できます。Post は、 と同様に、衝突の少ないハッシュを提案しhash = ( y << 16 ) ^ x;ます。

しかし、x または y のデータ wrt 値にアクセスしたいとします。ポイントを格納し、効率的に操作を実行するための構造は、ポイント QTree または Quad Tree です。ここ を参照してください。

ポイント四分木は、2 次元のポイント データを表すために使用されるバイナリ ツリーを適応させたものです。すべての四分木の機能を共有しますが、サブディビジョンの中心が常に点にあるため、真のツリーです。

点四分木のノードは二分木のノードに似ていますが、主な違いは、通常の二分木のように 2 つ (「左」と「右」) ではなく、4 つのポインター (各象限に 1 つ) を持つことです。 . また、キーは通常、x 座標と y 座標を参照して 2 つの部分に分解されます。したがって、ノードには次の情報が含まれます。 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 に答える
1

2D 配列と個別のハッシュテーブルの両方は必要ありません。データが高密度で、長方形領域のすべて (または大部分) を表している場合、2D 配列だけで十分です。フォローアップとして、ルックアップに使用される可能性が最も高い座標を尋ねてから、配列を構造化して、その座標でのルックアップがメモリ内でローカライズされるようにします。逆に、まばらなデータの場合は、ハッシュテーブルが最適です。(座標を点オブジェクトの配列にハッシュしていると仮定しています。) データの性質や、データがどのように使用される可能性が最も高いかについて、おそらくより多くの情報が提供されましたか?

于 2013-04-28T06:50:15.063 に答える