An answer to this question on the Scientific Computing Stack Exchange.

Question

I am graduate student and recently tried to implement quad-tree based AMR. Well I have implemented simple Poisson Solver on node-based quadtree, but I am not sure that my data structure is right. To be honest, I am not sure about my coding skills. So I'll just post some of my structures.

class node
{
  double x,y;
  cell *NW,*NE,*SW,*SE;
}
class cell
{
  double x,y;
  cell *NW,*NE,*SW,*SE;
  node *nw,*ne,*sw,*se;
}

So I stored information of four cells(the smallest) that shares the node. Therefore I can easily access to neighboring nodes. However, I think this is inefficient in memory, since it stores too many things. So what I am curious about is that, is their more efficient way of making quadtree structure that stores both node and cell? Thanks in advance.

Answer

Since the quad-tree has logarithmic height, the overall space cost is small.

If your mesh were the same everywhere, you could do implicit packing, as in a heap. For a binary tree, that looks like this:

   a
 b   c
d e f g
a b c d e f g

The position of each node in the linear format can be calculated with simple mathematics. This can be easily extended to a quad-tree.

However, if the quad-tree does not all have the same resolution, then this trick does not apply.

It is probably best to stick with a simple data structure for now. This will aid in debugging and you can adjust later if profiling suggests that's a good idea.