0
$\begingroup$

I would like to code for a quadtree type meshing but don't know how to do. If anyone can help or can share any starting code?

$\endgroup$
  • 1
    $\begingroup$ Welcome to SciComp! This question is a little bit broad and open ended. What have you tried and where did you get stuck? What language are you using? Are you having trouble just implementing a quad tree data structure? If you just need a quad mesh then perhaps using an already existing software package is better. If this is the case I recommend taking a look at Gmsh. Its free and easy to use. $\endgroup$ – James Nov 5 '15 at 19:10
  • $\begingroup$ @James I am trying to write my own CFD code. AT the moment, I am using loops for simulation (0 to Lx etc). Now I would like to make Quadtree data structures for multiblock meshing that I am unable to understand how to do that. My intention is to use C++. $\endgroup$ – TheCoder Nov 6 '15 at 12:51
  • $\begingroup$ Do you know how to implement a binary tree in c++? $\endgroup$ – James Nov 8 '15 at 1:30
  • $\begingroup$ I can learn, if you refer some good stuff. At the moment I don't know much. $\endgroup$ – TheCoder Nov 8 '15 at 4:01
  • $\begingroup$ Is the purpose of using a quad tree for adaptive refinement? If so are you using the finite element method? $\endgroup$ – James Nov 8 '15 at 5:09
2
$\begingroup$

Writing C++ code from the ground up for adaptive mesh refinement (as part of a PDE solver) is a relatively complicated endeavor and can easily involve thousands of lines of code for even simple problems. Based on the comments it sounds like you may be fairly new to programming (for example unsure how to implement a binary tree). Of course there is nothing wrong with being new at something - we all were at one point - but I think it is important to understand that this is a pretty large project to take on.

In terms of resources that would be useful for you, I would highly recommend taking a look at Wolfgang Bangerth's video tutorials here. These videos actually run through how finite element codes are developed from the ground up. Even though they are centred around finite elements (and not finite differences like you are doing), they contain a lot of valuable information related to adaptive mesh refinement and PDE solver codes in general. Beyond this any good C++ book can teach you about tree data structures...and there is also stackoverflow.

I mentioned the mesh generating tool called Gmsh in one of my comments and I highly recommend downloading for a number of reasons:

  1. Firstly it is easy to use and even has a GUI and can be used on Windows, Linux, and probably Mac (haven't checked Mac personally).
  2. It will give you an idea how meshes are stored and what information is important in a mesh.
  3. It can create 1D, 2D, and 3D meshes using triangles, quadrilaterals, tetrahedral, ....etc
  4. One strategy that you could use in your code is to start with a coarse mesh that you create using Gmsh, and then have this as an input to your program. Your program then performs adaptive mesh refinement on this coarse mesh while solving your PDE. Doing this has the benefit of simplifying your mesh generating process since you wont have to worry about how to generate an initial mesh on a possibly complicated geometry.

Now as for your specific question about quadtree data structures, what I would do is create a template QuadTree class in C++. For example the incomplete code for this might look something like:

#ifndef QUADTREE_H
#define QUADTREE_H

template<class T>
class Node
{
  public:
    T object;
    Node *parent;
    Node *topLeft;
    Node *topRight;
    Node *bottomLeft;
    Node *bottomRight;

    Node(T obj) : object(obj), parent(NULL), topLeft(NULL), topRight(NULL), bottomLeft(NULL), bottomRight(NULL)
    {
    }

    T* get_T();
    bool isLeaf();
    //   .
    //   .
    // more methods etc
};


template<class T>
class QuadTree
{
  private:
    int numNodes;      //number of node in tree
    int numLeafNodes   //number of leaf nodes in tree
    Node<T> *root;
    Node<T> *iterator;

  public:
    QuadTree();
    QuadTree(T obj);

    void deleteQuadTree(Node<T> *leaf);
    void setTopLeft(T obj);
    void setTopRight(T obj);
    void setBottomLeft(T obj);
    void setBottomRight(T obj);
    Node<T>* get_Node();
    T* get_T();
    bool isLeaf();
    //   .
    //   .
    //   more methods etc
};


//---------------------------------------------------------
// writing out all your implementations for each constructor, method, etc
//---------------------------------------------------------
//  .
//  .
//  .

#endif

By templating this QuadTree we can use it on simple integers (great for testing!) or complicated objects (...that might store information on your quadrilateral elements for example...). I hope this answer is of some help. I may be able to give more suggestions if you have specific questions about what I have written if needed. Your question was a little broad so I wasn't entirely sure where to start but good luck with your project.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.