c++ - 点遍历的最佳数据结构

寻找C ++解决方案。

我曾想过要问这个问题还是MathExchange等问题，但是因为它更多的是基于编程的问题，因此请在这里发布。

实际问题：

我有一个字段为XML：

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

在x和y处，我存储为QPointf对象。另外，我需要与name=01对象一起映射的QPointf值来创建映射。

现在，我需要在此地图上执行某些操作：

首先，我需要获取所有要点（QPointf）并绘制图像。
其次，我将修改某些点的x和y值，以从GUI获取点。
当我从GUI获取点时，需要检查地图中每个Qpointf中的x和y值。

简单形式的问题：

我正在寻找一种数据结构，而不是使用key和QPointf的映射，它使解析和寻找points（QPointf）的x和y值更加容易。只是QPointf和键应该彼此形成唯一的对，这样即使在修改了QPointf的x和y值时，解析整个点列表以查找某些(x,y)并对其进行修改也更快了。是一样的

PS：我希望我对这个问题很清楚，如果有任何不清楚的地方，请编辑/评论，以便可以改善问题。

最佳答案

我的猜测是，您最重要的方面是在用户使用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)的点：

使用PointIndexGrid对所有点进行分区。
使用pointIndexGrid.indicesForPoint(x, y)。
遍历那里的所有索引（并在points数组中查找点）。
抓住要点。

QPointF

c++ - 点遍历的最佳数据结构