ポイントトラバーサルに最適なデータ構造

Question

C++ソリューションを探しています。

ここでこの質問をするか、MathExchangeなどで質問するかは、プログラミングベースの質問の方が多いので、ここに投稿しています。

本当の問題：

xとyが、私はQPointfオブジェクトとして格納しています

<part name='01' x='351' y='151'/> 

：

私は、フィールドでのXMLを持っています。また、マップを作成するためにQPointfオブジェクトと一緒にマップしているname=01値が必要です。

は今、私はこのマップで実行する必要がある特定の操作があります。

• まず私はすべてのポイント（QPointf）を取得し、画像を上に描画する必要があります。
• 第2に、GUIからポイントを取得する特定のポイントのxとyの値を変更します。
• GUIからポイントを取得するとき、マップ内の各Qpointfのxとyの値をチェックする必要があります。

単純な形で問題：

I代わりkeyとQPointfのマップを有すると、それは解析することができるようにデータ構造を探していると点のxとyの値を探しています（QPointf ） より簡単に。ちょうどQPointfとキーがお互いにユニークなペアを形成するので、特定の(x,y)を見つけるためにポイントのリスト全体を解析し、それを修正する方が速く、QPointfのxとyの値が変更されても、同じ。

PS：明らかに問題があれば、不明な点があれば編集/コメントして問題を改善することができます。

Answer 1

私の推測はここにあるあなたの最も重要な側面が発見されていることをユーザーがUIを使用するときのxとyの特定のセット。可能な加速構造はたくさんありますが、おそらくpoint index gridをお勧めします。つまり、ポイントのインデックスを2Dバケットに分割します。ユーザーがUIでポイントを選択すると、そのポイントが入っているバケットをすばやく参照できるので、そのバケットにあるポイントだけを繰り返して実際のポイントを見つけることができます。

あなたのデータについては、私は、配列に格納します：

struct NamePoint { 
    int name, x, y; 
}; 
std::vector<NamePoint> points; 

は今、あなたはpoints配列を指し、ポイントインデックスのグリッドを作成します。あなた自身を実装することは価値があるかもしれませんが、それ以外の場合は、OpenVDBバージョンが存在することがわかります。

---

あなたが原則を見ることができるように、私は小さな汚い実装を行いました。私は入力をチェックしていないので、注意しないとベクトルの範囲外にアクセスします（たとえば、pointIndexGrid.indicesForPoint(5, 5)を呼び出すとセグメンテーション違反が発生します）。

#include <iostream> 
#include <vector> 
#include <limits> 

struct NamePoint { 
    int name, x, y; 
}; 

template <typename T> // Just so any array type can work 
struct PointIndexGrid { 
    using ArrayType = T; 
    using size_type = typename ArrayType::size_type; 

    PointIndexGrid(const ArrayType& points, int gridSize) 
     : mGridSize(gridSize) 
    { 
     // Find the domain. We will create a 2D vector which will all contain another vector with indices. 
     maxX = maxY = std::numeric_limits<int>::min(); 
     minX = minY = std::numeric_limits<int>::max(); 
     for (const auto& p : points) { 
      maxX = p.x > maxX ? p.x : maxX; 
      maxY = p.y > maxY ? p.y : maxY; 
      minX = p.x < minX ? p.x : minX; 
      minY = p.x < minY ? p.x : minY; 
     } 

     // create buckets 
     int nbrXBuckets = (maxX - minX)/mGridSize + 1; // Due to integer arithmetics we round down -- lets add one extra just in case 
     int nbrYBuckets = (maxY - minY)/mGridSize + 1; 
     for (int n = 0; n < nbrXBuckets; ++n) { 
      mBuckets.emplace_back(std::vector<std::vector<size_type>>(nbrYBuckets)); 
     } 

     // Partition points 
     for (size_type i = 0; i < points.size(); ++i) { 
      int xBucket = (points[i].x - minX)/mGridSize; // this is the method how to easily calculate the bucket. Pure arithmetics -- goes fast 
      int yBucket = (points[i].y - minY)/mGridSize; 
      mBuckets[xBucket][yBucket].emplace_back(i); 
     } 
    } 

    std::vector<size_type> indicesForPoint(int x, int y) 
    { 
     int xBucket = (x - minX)/mGridSize; // Same as above 
     int yBucket = (y - minY)/mGridSize; 
     return mBuckets[xBucket][yBucket]; 
    } 

private: 
    int mGridSize; 
    int maxX, minX; 
    int maxY, minY; 
    std::vector<std::vector<std::vector<size_type>>> mBuckets; 
}; 

int main() { 
    std::vector<NamePoint> points; 
    points.emplace_back(NamePoint{1, 1, 1}); 
    points.emplace_back(NamePoint{2, 1, 2}); 
    points.emplace_back(NamePoint{3, 1, 2}); 
    points.emplace_back(NamePoint{4, 2, 2}); 
    points.emplace_back(NamePoint{5, 3, 3}); 

    PointIndexGrid<std::vector<NamePoint>> pointIndexGrid(points, 2); 

    std::cout << "Indices for (1, 1): " << std::endl; 
    for (const auto& i : pointIndexGrid.indicesForPoint(1, 1)) { 
     std::cout << " " << i << std::endl; 
    } 

    std::cout << "Indices for (3, 3): " << std::endl; 
    for (const auto& i : pointIndexGrid.indicesForPoint(3, 3)) { 
     std::cout << " " << i << std::endl; 
    } 
} 

これはアウト出力します

Indices for (1, 1): 
0 
1 
2 
3 
Indices for (3, 3): 
4 

をだから、特定の(x, y)でポイントを見つけるために：

1. パーティションPointIndexGridを使用して、すべてのポイントを。
2. pointIndexGrid.indicesForPoint(x, y)を使用してください。
3. すべてのインデックスを反復処理します（points配列内のポイントを参照してください）。
4. 希望のポイントを取得します。

Answer 2

私が正しく理解していれば、ポイントデータを簡単に保存することができます。

これはパフォーマンスの面で最高ではないですが、あなたはそれをすべてのフレームを変更するに滑走されていない場合、それは何の問題動作しません：

#include <map> 
typedef std::map<int, std::pair<float, float>> PointContainer; 

QPointf* fromPointContainer(PointContainer points) 
{ 
    QPointf array = new QPointf[points.size()]; 
    for (size_t i; i < points.size(); i++) 
     array[i] = QPointf(points[i].first, points[i].second); 
    return array; 
} 

int main() { 
    PointContainer points; 
    points[0] = { 1.6f/*x*/, 5.8f/*y*/ }; 
    QPointf* array = fromPointContainer(points); 
    //render here 
    delete array;//don't forget to delete the array allocated with new 
    return 0; 
}