Good data structure to represent a 2D map/grid that you can zoom in and out of?

I've built a 2D grid in 开发者_Python百科java where each cell can have a certain attribute, say color. At each iteration of the main loop, that color can possibly change.

What I want to be able to do:

- when zoomed in, it will show a small subset of the grids and the actual color of each grid.

- as you zoom out and see more cells at once, the cells will start to get too small to be seen individually, so I want to be able to just represent that area(a collection of cells) as a single color (say the most often occurring one in that collection)

One thing I thought of for doing this would be to use a hierarchical tree/pyramid structure, where at the leaves you have each cell. Each parent node contains summary information of each of its children. So to draw the map at a high zoom level, I'd only need to go down a few levels in the tree instead of looking at each cell individually. However, propagation of changes from leaves to parents and subsequently to each higher level seems like it'd take quite awhile in a large grid for every loop iteration.

Is there a better way to do this? This problem seems like it should have been handled before by people in the graphics/gaming world but I'm having trouble even finding the right keywords to Google, so any help or direction is appreciated. Thanks.

Perhaps quadtree would be a helpful search term.

http://www.google.com/m/url?client=safari&ei=idePTdD_LuWJiAKbgM3pAQ&hl=en&oe=UTF-8&q=http://en.wikipedia.org/wiki/Quadtree&ved=0CBMQFjAA&usg=AFQjCNEjIDTtDl-nIhlMVz6WemoQ_w8jYg

I think you're on the right track. What you propose is a typical implementation of a 2D scene graph and determining bounds of parent nodes.

Keep in mind that even though leaf nodes might change colors, the change may not be propogated all the way up due to previous state. What you need to be sure to do is track dirty leaves so you don't do the update for everything when its not necessary.

I think you should implement what you propose and then see if performance is really an issue. How many cells are in your grid?