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

[DevC]

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.

[2kaud]

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

[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!).

[2kaud]

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.

[2kaud]

One simple way of doing this is

#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

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)

[wolle]

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

https://isocpp.org/blog/2013/02/b-tr...rs-from-google

(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.)

[2kaud]

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.

[DevC]

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.