Minimum distance between two elements in a circular grid

Question

Given a round array, what is an effective way to determine the minimum distance between two elements?

For example, going from here

[0,0,0,0,0,1] 

Here

 [1,0,0,0,0,0] 

More convenient from outside borders, and from here

 [0,0,0,0,0,1] 

here

 [0,0,0,1,0,0] 

more comfortable inside.

My initial idea was as follows:

 sourceLocation = rotatorElements["pos"].indexOf(1); targetLocation = rotatorElements["pos"].rotate(delta).indexOf(1); var D = Math.abs(targetLocation - sourceLocation); var O = Math.abs(rotatorElements["pos"].length - D); if ((D - O == 0)) direction = 1; else { if (D < O) direction = -1; else direction = 1; } 

Note: rotate rotates a circular array by a certain number of positions.

Answer 1

Edit: I think I answered the question in the title, but what you want is a direction not at a distance. Then:

 function getDirection(from, to, array) { if (from === to) { return 0; } var internal = (Math.max(from, to) - Math.min(from, to) < array.length/2) ? true : false; if (internal && from < to || !internal && from > to ) { return 1; } else { return -1; } } 

Answer 2

Calculating the absolute distance between elements is useful:

 var dist = Math.abs(targetLocation - sourceLocation); 

Then you can simply check if it is less than half the length of the array. If the distance is more than half the length, it is closer to the wrap:

 if (dist < rotatorElements["pos"].length / 2) { // move internally } else { // wrap around } 

Edit:

I pasted the code together:

 function move(sourceLocation, targetLocation, length) { var dist = Math.abs(targetLocation - sourceLocation); var direction = sourceLocation < targetLocation ? 1 : -1; if (dist < length / 2) { console.log('internally, direction =', direction); } else { console.log('wrap, direction =', -direction); } } move(5, 0, 6); move(5, 3, 6); 

Output:

 wrap, direction = 1 internally, direction = -1 

Demo: http://jsfiddle.net/bUCmk/

Answer 3

Here is my solution (in groovy) that gives you direction and distance (moving counterclockwise if the output is negative):

 def move(def start, def target, def length){ def clockwise def counterclockwise if (start > target){ clockwise = length - start + target counterclockwise = start - target } else { clockwise = target - start counterclockwise = length - target + start } if (counterclockwise < clockwise){ return counterclockwise * -1 } return clockwise } 

And this is the result:

 groovy:000> move(0,0,0) ===> 0 groovy:000> move(0,0,4) ===> 0 groovy:000> move(0,1,4) ===> 1 groovy:000> move(0,2,4) ===> 2 groovy:000> move(0,3,4) ===> -1 groovy:000> move(1,0,4) ===> -1 groovy:000> move(1,1,4) ===> 0 groovy:000> move(1,2,4) ===> 1 groovy:000> move(1,3,4) ===> 2 groovy:000> move(2,0,4) ===> 2 groovy:000> move(2,1,4) ===> -1 groovy:000> move(2,2,4) ===> 0 groovy:000> move(2,3,4) ===> 1 groovy:000> move(3,0,4) ===> 1 groovy:000> move(3,1,4) ===> 2 groovy:000> move(3,2,4) ===> -1 groovy:000> move(3,3,4) ===> 0