Efficient/fast data structures for dynamic set of 2D points
 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Efficient/fast data structures for dynamic set of 2D points

1. Junior Member
Join Date
Apr 2017
Posts
3

## Efficient/fast data structures for dynamic set of 2D points

Hi,

I'm hoping someone could provide advice about suitable efficient data structure and fast algorithms to store, create, destroy, and scan a set of dynamic points on a regular 2D grid (relating to modelling flood water on a gridded surface). In brief:

• Points (pixels) on a regular 2D grid can be active or inactive.
• I want to store only the active points (because the dimensions of the 2D grid can be very, very large, and a high percentage of pixels will be inactive).
• Active points can become inactive (and vice versa ) and so I need to create/destroy points.
• I want to scan points in row/column order.

I'm not a computer scientist but a hydrologist who codes (mostly in C++). Any advice gratefully received. Thanks.

2. ## Re: Efficient/fast data structures for dynamic set of 2D points

About how many active points are there at any one time?

3. Junior Member
Join Date
Apr 2017
Posts
3

## Re: Efficient/fast data structures for dynamic set of 2D points

A roughly estimate is that 10% of the grid could become active. Currently modelling a 20 x 20 km region on a 50 m resolution so 16,000 points, but would like to get down to a 2 m resolution (10^7 points!).

4. ## Re: Efficient/fast data structures for dynamic set of 2D points

Have a look at this http://forums.codeguru.com/showthrea...nsional-arrays and post #7.

It's about multi-dimensional arrays - but the idea of how to store the data is applicable also to just 2 dimensions.

There are other ways of doing this - such as having a vector points etc.

As you just want points to be active/inactive you don't actually need to store a value for each point - just the co-ords. So the idea could be revamped using a set rather than a map. I'll work something up on these lines and post it.

5. ## Re: Efficient/fast data structures for dynamic set of 2D points

One simple way of doing this is

Code:
```#include <set>
#include <iostream>
using namespace std;

using TypeD = unsigned short int;

struct dimg {
TypeD dim1;
TypeD dim2;

dimg(TypeD d1, TypeD d2) : dim1(d1), dim2(d2) {}
};

class myGrid
{
public:
void setp(TypeD d1, TypeD d2)
{
grid.emplace(d1, d2);
}

void unsetp(TypeD d1, TypeD d2)
{
grid.erase(dimg(d1, d2));
}

bool exists(TypeD d1, TypeD d2) const
{
return grid.count(dimg(d1, d2));
}

auto begin() const
{
return grid.begin();
}

auto end() const
{
return grid.end();
}

private:
set<dimg> grid;
};

bool operator<(const dimg& ld, const dimg& rd)
{
if (ld.dim1 < rd.dim1)
return true;

if (ld.dim1 == rd.dim1)
if (ld.dim2 < rd.dim2)
return true;

return false;
}

int main()
{
myGrid arr;

arr.setp(2, 3);
arr.setp(1, 1);

cout << "arr(1, 1): " << (arr.exists(1, 1) ? "Exists" : "Not exists") << endl;
cout << "arr(2, 2): " << (arr.exists(2, 2) ? "Exists" : "Not exists") << endl;
cout << "arr(2, 3): " << (arr.exists(2, 3) ? "Exists" : "Not exists") << endl;

for (const auto& g : arr)
cout << "(" << g.dim1 << ", " << g.dim2 << ")" << endl;

arr.setp(2, 2);
arr.unsetp(1, 1);

cout << endl;
cout << "arr(1, 1): " << (arr.exists(1, 1) ? "Exists" : "Not exists") << endl;
cout << "arr(2, 2): " << (arr.exists(2, 2) ? "Exists" : "Not exists") << endl;
cout << "arr(2, 3): " << (arr.exists(2, 3) ? "Exists" : "Not exists") << endl;

for (const auto& g : arr)
cout << "(" << g.dim1 << ", " << g.dim2 << ")" << endl;
}```
This produces the display
Code:
```arr(1, 1): Exists
arr(2, 2): Not exists
arr(2, 3): Exists
(1, 1)
(2, 3)

arr(1, 1): Not exists
arr(2, 2): Exists
arr(2, 3): Exists
(2, 2)
(2, 3)```
Last edited by 2kaud; April 3rd, 2017 at 08:40 AM. Reason: Type def in code

6. Member
Join Date
Feb 2017
Posts
35

## Re: Efficient/fast data structures for dynamic set of 2D points

Originally Posted by DevC
A roughly estimate is that 10% of the grid could become active. Currently modelling a 20 x 20 km region on a 50 m resolution so 16,000 points, but would like to get down to a 2 m resolution (10^7 points!).
Like 2kaud I think an std::set is a good solution since you want the points sorted. This will work fine for the current resolution but not so good when you scale up. With that many points the binary tree based std::set will start becoming inefficient. So for the higher resolution I suggest you look for a B-tree based set implementation instead, like for example

(Also since dim1 and dim2 are quite small numbers what you can do to save space is pack both into just one 32-bit unsigned int using 16 bits for each.)
Last edited by wolle; April 3rd, 2017 at 07:59 AM.

7. ## Re: Efficient/fast data structures for dynamic set of 2D points

what you can do to save space is pack both into just one 32-bit unsigned int using 16 bits for each.
Or make the type of dim1, dim2 as unsigned short int. This reduces the size of dimg from 8 bytes to 4 bytes (on Windows VS) and saves having to pack/unpack from a single 32 bit. The arguments of the various class functions also need to be changed as appropriate to prevent compiler warnings.

I've changed the code in post #5 to reflect this using a new type TypeD which can be changed if needed.

8. Junior Member
Join Date
Apr 2017
Posts
3

## Re: Efficient/fast data structures for dynamic set of 2D points

Thanks 2kaud and wolle! This is immensely helpful, has saved me a lot of time searching the web, and will save me even more time waiting for models to run. Much appreciated.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•