Best data structure for point traversal

Question

Looking for a C++ solution.

I had thoughts whether to ask this question over here or MathExchange etc. but since it's more of a programming based question thus posting here.

Real problem:

I have an XML with field as:

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

Where x and y, I am storing as QPointf object. Also, I require the name=01 value which I am mapping together with the QPointf object to create a map.

Now there are certain operations that I need to do on this map :

• First I need to get all the points(QPointf) and draw over an image.
• Second, I will modify the x and y value of certain points getting the points from the GUI.
• When I get the points from GUI, I need to check x and y value in each Qpointf inside map.

Problem in simpler form:

I am looking for a data structure such that instead of having a map of key and QPointf, it makes parsing and looking for x and y value of points(QPointf) easier. Just that the QPointf and key should form a unique pair with each other, so that parsing through the entire list of points to find certain (x,y) and modifying it is faster and even when x and y value of QPointf is modified the key attached to it is same.

PS: I hope I was clear with the problem, if there is anything unclear then please edit/comment so that the question can be improved.

Answer 1

So if I understood correctly you just want an easy way to store your points data.

This isn't the best in terms of performance but if you are not planing on changing it every frame it will work no problem:

#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;
}

Answer 2

My guess is here that your most important aspect is finding a certain set of x and y points when a user uses the UI. There are many acceleration structures possible, but I would probably recommend a point index grid. That is, you partition the indices of points into 2D buckets. When a user chooses a point in the UI, you can do a quick look-up on what bucket the point is in, and you can then iterate over only the points present in that bucket to find the actual point.

As for your data, I would store it in an array:

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

Now you would create a point index grid that refers to the points array. Implementing one yourself might be worthwhile, but otherwise I know that there exists an OpenVDB version that works.

---

I made a small dirty implementation so you can see the principle. I have no checks for inputs, so if you're not careful you will access out of the bounds of the vector (e.g., calling pointIndexGrid.indicesForPoint(5, 5) gives segmentation fault).

#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;
    }
}

This prints out:

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

So to find a point at a specific (x, y):

1. Partition all points using the PointIndexGrid.
2. Use pointIndexGrid.indicesForPoint(x, y).
3. Iterate through all indices there (and look up the points in the points-array).
4. Grab the point that you want.