Can Anyone Help Me Fix My 3D Space Filling Tree Algorithm?

In summary: if(sx > 0) { // if(dir == 2) return true; else
  • #1
intervoxel
195
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.
 

Attachments

  • forum.zip
    2.2 MB · Views: 247
Technology news on Phys.org
  • #2
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 what's going on and whether it makes sense?

or are you just looking at what is produced and then are lost?
 
  • #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, ...):

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;
            }
        }
    }
}
 
  • #4
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 ).
 
  • #5
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?
 

Related to Can Anyone Help Me Fix My 3D Space Filling Tree Algorithm?

1. What is a 3D space filling tree?

A 3D space filling tree is a data structure that is used to represent and store information about objects in a three-dimensional space. It is a hierarchical tree structure where each node represents a region in the 3D space and its children represent smaller sub-regions within that region.

2. How does a 3D space filling tree work?

A 3D space filling tree works by recursively dividing the space into smaller and smaller regions until each region contains only a single object or a small number of objects. This allows for efficient storage and retrieval of information about objects in the 3D space.

3. What are the advantages of using a 3D space filling tree?

One advantage of using a 3D space filling tree is its ability to efficiently store and retrieve information about objects in a 3D space. It also allows for fast spatial queries, such as finding all objects within a certain region or finding the closest object to a given point.

4. How is a 3D space filling tree different from a regular tree?

A 3D space filling tree is different from a regular tree in that it represents a three-dimensional space instead of a one-dimensional sequence of data. It also uses a different algorithm for dividing and organizing the data, taking into account the spatial relationships between objects in the 3D space.

5. What are some real-world applications of 3D space filling trees?

Some real-world applications of 3D space filling trees include computer graphics and animation, virtual reality, robotics, and geographic information systems. They are also used in physics simulations, molecular modeling, and data compression.

Back
Top