Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C/++/# 3d space filling tree

  1. Apr 5, 2017 #1
    Hi all,

    I need an algorithm that fills a 3d lattice from any point, always expanding (no return allowed as in ref. http://msl.cs.illinois.edu/~lavalle/papers/KufLav09.pdf). The cells must be visited just once.
    My efforts are contained in the attached file. It works ***almost*** correct. Some gaps remain, though. No matter my attempts I could not fix the code. Could you help me, fixing the code or cite an alternate reference?

    The executable (Tree.exe) can use the mouse for orbital rotations and the following keys and conventions:

    1 shows root
    2 shows x axis
    3 shows y axis
    4 shows z axis
    5 shows xy plane
    6 shows yz plane
    7 shows zx plane
    8 shows octant spirals
    q selects the first octant only
    a shows positive axes
    pgup increases dimension
    pgdwn decreases dimension

    The not visited positions are shown as a white dot.

    The relevant algorithm is contained in the functions expandTree() and isAllowed() in file 'forum.c'.

    Thanks for any help.
     

    Attached Files:

  2. jcsd
  3. Apr 5, 2017 #2

    jedishrfu

    Staff: Mentor

    I would ask that you not to provide a zip file but instead post your code here / not all of it just the piece you think has the problem. We have a code tags that will colorize it (syntax highlight) your listing.

    What have you tried as far as debugging?

    Have you used print statements to see whats going on and whether it makes sense?

    or are you just looking at what is produced and then are lost?
     
  4. Apr 5, 2017 #3
    Thank you for the prompt answer, jedishrfu.

    I debugged the code using Eclipse without success.

    Below is the relevant code, the dirs[] array contains the six von Neumann directions (1,0,0; -1,0,0, ...):

    Code (Java):

    boolean isAllowed(int dir)
    {
        // Expansion algorithm
        //
        int s0 = (tree.x * tree.y < 0) ? 1 : 0;
        int s1 = (tree.y * tree.z < 0) ? 1 : 0;
        int s2 = (tree.z * tree.x < 0) ? 1 : 0;
        //
        int sx = sgn(tree.x);
        int sy = sgn(tree.y);
        int sz = sgn(tree.z);
        //
        if(tree.x != 0)
        {
            if(tree.y != 0)
            {
                if(tree.z != 0)
                {
                    // 3d spiral
                    //
                    switch(level % 3)
                    {
                        case 0:
                            if(sx < 0)
                            {
                                if(dir == 1) return true;
                            }
                            else
                            {
                                if(dir == 0) return true;
                            }
                            break;
                        case 1:
                            if(sy < 0)
                            {
                                if(dir == 3) return true;
                            }
                            else
                            {
                                if(dir == 2) return true;
                            }
                            break;
                        case 2:
                            if(sz < 0)
                            {
                                if(dir == 5) return true;
                            }
                            else
                            {
                                if(dir == 4) return true;
                            }
                            break;
                    }
                }
                else
                {
                    // xy plane
                    //
                    if(level % 2 == s0)
                    {
                        if(sx < 0)
                        {
                            if(dir == 1) return true;
                        }
                        else
                        {
                            if(dir == 0) return true;
                        }
                    }
                    else
                    {
                        if(sy < 0)
                        {
                            if(dir == 3) return true;
                        }
                        else
                        {
                            if(dir == 2) return true;
                        }
                    }
                    //
                    if(level % 3 == 0 && dir > 3)
                        return true;
                }
            }
            else if(tree.z != 0)
            {
                // zx plane
                //
                if(level % 2 == s2)
                {
                    if(sz < 0)
                    {
                        if(dir == 5) return true;
                    }
                    else
                    {
                        if(dir == 4) return true;
                    }
                }
                else
                {
                    if(sx < 0)
                    {
                        if(dir == 1) return true;
                    }
                    else
                    {
                        if(dir == 0) return true;
                    }
                }
                //
                if(level % 3 == 2 && (dir == 2 || dir == 3))
                    return true;
            }
            else
            {
                // x axis
                //
                if(sx < 0)
                {
                    if(dir == 1) return true;
                }
                else
                {
                    if(dir == 0) return true;
                }
                //
                if(level % 2 == 0)
                {
                    if(sx < 0)
                    {
                        if(dir == 2) return true;
                    }
                    else
                    {
                        if(dir == 3) return true;
                    }
                    //
                    if(sx < 0)
                    {
                        if(dir == 5) return true;
                    }
                    else
                    {
                        if(dir == 4) return true;
                    }
                }
                else
                {
                    if(sx < 0)
                    {
                        if(dir == 3) return true;
                    }
                    else
                    {
                        if(dir == 2) return true;
                    }
                    //
                    if(sx < 0)
                    {
                        if(dir == 4) return true;
                    }
                    else
                    {
                        if(dir == 5) return true;
                    }
                }
            }
        }
        else if(tree.y != 0)
        {
            if(tree.z != 0)
            {
                // yz plane
                //
                if(level % 2 == s1)
                {
                    if(sy < 0)
                    {
                        if(dir == 3) return true;
                    }
                    else
                    {
                        if(dir == 2) return true;
                    }
                }
                else
                {
                    if(sz < 0)
                    {
                        if(dir == 5) return true;
                    }
                    else
                    {
                        if(dir == 4) return true;
                    }
                }
                //
                if(level % 3 == 1 && dir < 2)
                    return true;
            }
            else
            {
                // y axis
                //
                if(sy < 0)
                {
                    if(dir == 3) return true;
                }
                else
                {
                    if(dir == 2) return true;
                }
                //
                if(level % 2 == 0)
                {
                    if(sy < 0)
                    {
                        if(dir == 1) return true;
                    }
                    else
                    {
                        if(dir == 0) return true;
                    }
                    //
                    if(sy < 0)
                    {
                        if(dir == 4) return true;
                    }
                    else
                    {
                        if(dir == 5) return true;
                    }
                }
                else
                {
                    if(sy < 0)
                    {
                        if(dir == 0) return true;
                    }
                    else
                    {
                        if(dir == 1) return true;
                    }
                    //
                    if(sy < 0)
                    {
                        if(dir == 5) return true;
                    }
                    else
                    {
                        if(dir == 4) return true;
                    }
                }
            }
        }
        else if(tree.z != 0)
        {
            // z axis
            //
            if(sz < 0)
            {
                if(dir == 5) return true;
            }
            else
            {
                if(dir == 4) return true;
            }
            //
            if(level % 2 == 0)
            {
                if(sz < 0)
                {
                    if(dir == 0) return true;
                }
                else
                {
                    if(dir == 1) return true;
                }
                //
                if(sz < 0)
                {
                    if(dir == 3) return true;
                }
                else
                {
                    if(dir == 2) return true;
                }
            }
            else
            {
                if(sz < 0)
                {
                    if(dir == 1) return true;
                }
                else
                {
                    if(dir == 0) return true;
                }
                //
                if(sz < 0)
                {
                    if(dir == 2) return true;
                }
                else
                {
                    if(dir == 3) return true;
                }
            }
        }
        else
        {
            // Root
            //
            return true;
        }
        return false;
    }

    void expandTree()
    {
        int i;
        for(i = 0; i < 6; i++)
        {
            int type = getType(i);
            {
                last.x = tree.x;
                last.y = tree.y;
                last.z = tree.z;
                //
                tree.x += dirs[i].x;
                tree.y += dirs[i].y;
                tree.z += dirs[i].z;
                //
                if(abs(tree.x) == n / 2 + 1 || abs(tree.y) == n / 2 + 1 || abs(tree.z) == n / 2 + 1)
                {
                    tree.x -= dirs[i].x;
                    tree.y -= dirs[i].y;
                    tree.z -= dirs[i].z;
                    continue;
                }
                else
                {
                    plotLine(last, tree);
                    //
                    level++;
                    expandTree();
                    level--;
                    //
                    tree.x -= dirs[i].x;
                    tree.y -= dirs[i].y;
                    tree.z -= dirs[i].z;
                }
            }
        }
    }

     
     
  5. Apr 5, 2017 #4

    jedishrfu

    Staff: Mentor

    I think you probably need to try print statements to get an idea of what its doing as its running then identify the first point where it goes wrong. From there you can use the debugger to run to that spot in your code and step through your logic.

    A key part of debugging is knowing how your algorithm is supposed to work by doing it yourself step by step.

    I often step thru my code and manually step through my algorithm checking both until I spot the error. Usually its something simple like a < instead of a <= or checking the wrong variable like checking x when it should have been y ( common error during copy/paste and tweak the coding ).
     
  6. Apr 5, 2017 #5

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Some explanation would help. What does isAllowed do? Where is it used? Where is the point in changing tree and then changing it back no matter what happens - but with separate code for both cases?
    Which things do not get visited?

    Where is tree defined, where does the program start, and why do you use global variables?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: 3d space filling tree
  1. Binary tree (Replies: 5)

Loading...