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

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

  1. #1
    Join Date
    Apr 2017
    Posts
    3

    Question 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. #2
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,587

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

    About how many active points are there at any one time?
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C, C++ Compiler: Microsoft VS2017.2

  3. #3
    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. #4
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,587

    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.
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C, C++ Compiler: Microsoft VS2017.2

  5. #5
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,587

    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
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C, C++ Compiler: Microsoft VS2017.2

  6. #6
    Join Date
    Feb 2017
    Posts
    111

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

    Quote Originally Posted by DevC View Post
    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.)
    Last edited by wolle; April 3rd, 2017 at 07:59 AM.

  7. #7
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,587

    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.
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C, C++ Compiler: Microsoft VS2017.2

  8. #8
    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This a Codeguru.com survey!


On-Demand Webinars (sponsored)