Search Algorithm for Finding Special Cells

[pslarsen]

I am writing a programme which has to find specific cells with special properties. I don’t know where the cell are located by I have a pretty good idea so my programme can actually make qualified guesses. When I have guessed on a cell and it’s not the right one I have to check the cells lying beside it until I find the right cell. With help from a propagating sphere I have made a vector which solved the problem but I was wondering if one can make some kind of spiral algorithm. To explain what I mean I have made an example of an identical problem in two dimensions - this is seen in the drawing.

First I guess on some cell (start) and then I search all nearby cells one by one until I find the specific cell (end). To the right of the drawing you see the algorithm I could use, I just have to scale it the right way a loop.

Can I extent this idea to 3dimensions? If not, can you proof why? My guess is that the answer lies in graph theory – I just don’t know much about that..

/Peter

 

[Mensanator]

I am writing a programme which has to find specific cells with special properties. I don’t know where the cell are located by I have a pretty good idea so my programme can actually make qualified guesses. When I have guessed on a cell and it’s not the right one I have to check the cells lying beside it until I find the right cell. With help from a propagating sphere I have made a vector which solved the problem but I was wondering if one can make some kind of spiral algorithm. To explain what I mean I have made an example of an identical problem in two dimensions - this is seen in the drawing.

First I guess on some cell (start) and then I search all nearby cells one by one until I find the specific cell (end). To the right of the drawing you see the algorithm I could use, I just have to scale it the right way a loop.

Can I extent this idea to 3dimensions? If not, can you proof why? My guess is that the answer lies in graph theory – I just don’t know much about that..

/Peter

You just re-discovered Ulam's Spiral.

You ought to be able to extend it to three dimensions.

For example, your starting point is the center of a 3x3 grid in two-dimensions.
It's also the center of a 3x3x3 cube in three-dimensions.

To do the next "ring", it is the center of a 5x5 grid or a 5x5x5 cube.

The next "ring" is a 7x7 grid or a 7x7x7 cube.

And so on.

It might be a bit tricky doing it in 3-D. Each time you increase your search space, say from a 3x3x3 cube to a 5x5x5 cube, you just want to crawl over the surface, no need to re-check the interior points (as would happen if you just did an Ulam's Spiral on each of the 5 layers).

 

[pslarsen]

Are you sure its called Ulam's Spiral? Everything I find has something to do with primes and wiki says: http://en.wikipedia.org/wiki/Ulam_spiral

 

[CRGreathouse]

Are you sure its called Ulam's Spiral? Everything I find has something to do with primes and wiki says: http://en.wikipedia.org/wiki/Ulam_spiral

Just ignore the primes and focus on the way they draw the spiral -- it's the same.

 

[pslarsen]

I must admit that it haven't help me at all - its just a duplicate of my 2d example. I will try to ask the question in another way:

Is it possible to make a CONTINUOUS spiral in a symmetric squared grid which has the size NxNxN where N is an posive odd integer, starting in the center ((N+1)/2,(N+1)/2,(N+1)/2). The spiral has to take neighbor points before everything else..

 

[pslarsen]

if YES: Can you link an example? Can you describe why - mathematically?
if NO : Why not?

 

[Mensanator]

if YES: Can you link an example? Can you describe why - mathematically?
if NO : Why not?

I don't know of any examples in 3D, but it's not that hard to extend it since you already know how do do the spiral. (Well, I assume you know, based on your drawing. That is obviously what you want, but I don't know if you can actually implement it. If not I can give you tips.)

Anyway, assume the target cell is the reference (x,y,z coordinates are {0,0,0}).

Draw your spiral as before holding z constant at 0. Stop when you complete the 3x3 square. This square represents the middle slice of the cube. Upon completion, you are on one edge of the cube at coordinates {a,b,0}. Go down 1 in the z direction. You're at {a,b,-1}.

Draw the spiral again only in the reverse direction (spiraling inwards). When you stop, you'll be at {0,0,-1}, the center of the bottom face. Go up in the z direction by 2. Now you're at {0,0,1}, the center of the top face. Do the spiral again in the forward direction until you've made another 3x3 square. This completes all 3 layers of the 3x3x3 cube.

If doing the spiral in the reverse direction is too difficult, remember, you always know where the center of the top face of the cube is, it's always at {0,0,z}. If you're not too strict on it being continuous, you can always got the center and always draw your spirals in the forward direction.

This 3x3x3 cube would then be all the interior cells of the enclosing 5x5x5 cube. Again, the easiest way is simpy goto {0,0,z+1} and draw the spiral to a size of 5x5. Now, you're at a corner of the 5x5x5 cube, so go down 1 in the z direction. While on the middle levels, we don't need to draw the entire spiral (still need reverse, though) only 4 sides. When the fourth side is complete, instead of turning inwards, just go forwards 1 step. You'll be back at your starting point. Go down 1 in the z direction and repeat the 4 sides. Do this for all the middle layers.

Now, you're on the bottommost layer, at a corner of the cube {c,d,-2}. If you have the full reverse spiral algorithm simply execute that or recenter at {0,0,-2} and do it in the forwards direction.

From this point on, further 3D layers (7x7x7, 9x9x9, etc.) are simply repetions of the 5x5x5 algorithm.

It's a doddle. I'd give you an actual example, but my Turtle Graphics doesn't do 3D.

 

[Gerenuk]

It doesn't seem that you need a perfectly continuous walk. But you can search shell by shell. I made a way to check all points of a shell:

shell=2

print -shell,-shell,-shell
print shell,shell,shell

for x in range(-shell,shell): # x will be -shell ... shell-1
  for y in range(-shell+1,shell+1): # y will be -shell+1 ... shell
    print x,y,shell
    print y,x,-shell
    print x,-shell,y
    print y,shell,x
    print -shell,y,x
    print shell,x,y

This will print the coordinates of a shell with a center at 0,0,0

EDIT: And btw, if you ever need something similar where however you do not have a specific center, then have a look at
http://en.wikipedia.org/wiki/Z-order_(curve)
or
http://en.wikipedia.org/wiki/Hilbert_curve

 

[Hurkyl]

You can't tour blocks arranged in a cube -- there are more than two blocks that have an odd number of neighbors.

 

[Gerenuk]

You can't tour blocks arranged in a cube -- there are more than two blocks that have an odd number of neighbors.

It's not that easy. The problem posed here is a Hamiltonian path. Not an Eulerian path. Also diagonal jumps can make paths easier.

EDIT: I even believe that my above algorithm can easily give a Hamiltonian spiral (start with -N,-N,-N and work through the sheets; end with +N,+N,+N). However you have to allow for for a short diagonal step at the corners of the cube.

 

[Hurkyl]

Er... yah, I totally flaked on that one, nevermind!

 

[pslarsen]

EDIT: I even believe that my above algorithm can easily give a Hamiltonian spiral (start with -N,-N,-N and work through the sheets; end with +N,+N,+N). However you have to allow for for a short diagonal step at the corners of the cube.

Ok thanks.. I don't have time to check it out right now but I will take a look at it later.

If anyone should be interested this is how I solve the problem right now:
First I create a list with programme seen below (maybe it is bad coding - I wrote in 10mins). When this programme has created a list I can use this list in every run and it is quite fast.

# This is a very simple programme which has the purpose of creating a list used within the search algorithm
# in the dynamic fracturing programme.
use strict;
use warnings;
unlink("SEARCH.LST");

my $dim = 19; # defines the dimensions of the cell
my @cell_center = (($dim+1)/2,($dim+1)/2,($dim+1)/2); # the center of the cell

# First we have to create the symmetric grid. This is quite easy:

my $count = 0;
my @coordvector = ();
for my $ii (1..$dim) {
	for my $jj (1..$dim) {
		for my $kk (1..$dim) {
	    	$coordvector[$count][0] = $ii;
	    	$coordvector[$count][1] = $jj;
	    	$coordvector[$count][2] = $kk;
	    	$count++;
    	}
	}
}

# Now the grid has been created. With help of the distance equation ||v|| = sqrt(x**2+y**2+z**2) we will determine the list.

my @distance_constant = ();
$distance_constant[0] = 0.5;
for my $n_search (1..int(sqrt(3)*int($dim/2))+1) {
	$distance_constant[$n_search] = $distance_constant[$n_search-1] + 1;
	for my $ijk (0..$count-1) {
		my $two_point_distance = sqrt( ($coordvector[$ijk][0]-$cell_center[0])**2 + ($coordvector[$ijk][1]-$cell_center[1])**2 + ($coordvector[$ijk][2]-$cell_center[2])**2);	
		if ( $two_point_distance < $distance_constant[$n_search] && $two_point_distance > $distance_constant[$n_search-1] ) {
			open(SEARCH,">>","SEARCH.LST");
				print SEARCH $coordvector[$ijk][0]-$cell_center[0]," ",$coordvector[$ijk][1]-$cell_center[1]," ",$coordvector[$ijk][2]-$cell_center[2],"\n";
			close(SEARCH);
		}
	}
}

 

[pslarsen]

by the way - it is written in Perl.

 

[pslarsen]

So this problem is actually not that much for the sake of programming but more the solution of the analytical mathematical problem.. e.g. through graph theory...
/Peter

 

[Gerenuk]

Wow, that seems like an overkill. I suggest the following equivalent(?) program

my $maxshell=9;

print 0,0,0;
for my $shell (1..$maxshell) {
  print -$shell,-$shell,-$shell;
  print $shell,$shell,$shell;
  for my $x (-$shell..$shell-1) { 
    for my $y (-$shell+1..$shell) {
      print $x,$y,$shell;
      print $y,$x,-$shell;
      print $x,-$shell,$y;
      print $y,$shell,$x;
      print -$shell,$y,$x;
      print $shell,$x,$y;
    }
  }
}

You have to replace the print statements by an appropriate function that writes to your file.

Unfortunately my perl is slightly different, so I cannot check this program directly.

Well, this program uses a different distance metric that spheres of course. It slowly increases the size of the cube to consider.

As for the mathematical spiral problem. You could also spiral if you wish.
Look at the cube like
http://finitegeometry.org/sc/index_files/GridCube165C3.jpg
(with the big difference that all your cubes have odd dimensions.
You could start at the center and spiral outwards. Then finally switch to the opposite sides of the cube and spiral back to the center. This way you search shell by shell. I guess you might still need a diagonal step somewhere.

But still I find my suggestion for going sheet-wise much cleaner. In the above program I trace out 6 dim x (dim-1) sheets and add the two missing corners. A similar approach works for some snaky line that traces out the shell of the cube.