CODEWITHSUNDEEP
javascriptalgorithm
kojow7
kojow7

Reputation: 11404

Calculating distances between cubes (when wraparound exists)

I have a large cube composed of smaller cubes. The large cube consists of 10 cubes wide, by 10 cubes in length, by 10 cubes in height. For a total of 1000 cubes.

I want to be able to determine which is the closest green cube to the blue cube.

One other thing that is important is that each side of the cube is connected to the opposite side (i.e. row 10 is considered next to row 1). This is the wraparound effect.

So, for example, if the blue cube is at coordinates 9:8:8 and the green cubes are each at 1:2:2, 5:5:3, and 6:3:4. Then the green cube at 1:2:2 should be considered the closest cube. If my calculations are correct, it should have a distance of 10 whereas the other two would each have a distance of 12.

Without the cube wraparound (side 1 connected with side 10) I have been able to come up with the following in JavaScript:

let lowest = 1000;
let lowest_index = -1;

for (i = 0; i < green_cube.length; i++){

    let x_offset = Math.abs(blue_cube.x - green_cube[i].x);
    let y_offset = Math.abs(blue_cube.y - green_cube[i].y);
    let z_offset = Math.abs(blue_cube.z - green_cube[i].z);

    let distance = x_offset + y_offset + z_offset;
    if (distance < lowest){
        lowest = distance;
        lowest_index = i;
    }
}

What is the proper way to code this when taking wraparound into effect?

Update

To clarify, the distance needs to be distance by number of cubes traveled to get from point A to point B. Distance must be traveled only along the X, Y, and Z axis, therefore, diagonal distance will not work. I believe this is referred to as taxicab distance in 3D space.

Upvotes: 0

Views: 312

Answers (5)

kojow7
kojow7

Reputation: 11404

I've come across another solution that also works:

let cube_width = 10;
let mid_point = cube_width / 2;

let x_offset = Math.abs(point1 - point2);
if (x_offset > mid_point){
    x_offset = cube_width - x_offset;
}

I'm having a hard time figuring out whether this one or SirRaffleBuffle's solution is more efficient for time.

Upvotes: 0

user1196549
user1196549

Reputation:

Virtually replicate the green cubes as if they appeared at x, x-10 and x+10 and keep the minimum delta. This is done on the three axis independently.

Upvotes: 0

Andriy
Andriy

Reputation: 15442

In this code I am using distance calculation formula for 2 points in 3d (reference).

enter image description here

const calculateDistance3d = ({x: x1, y: y1, z: z1}, {x: x2, y: y2, z: z2}) => {
  return Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2) + Math.pow(z2 - z1, 2));
}

const calculateLoopedDistance = (cubeA, cubeB) => {
  return calculateDistance3d(cubeA, {
    x: cubeA.x + 10 - Math.abs(cubeB.x - cubeA.x),
    y: cubeA.y + 10 - Math.abs(cubeB.y - cubeA.y), 
    z: cubeA.z + 10 - Math.abs(cubeB.z - cubeA.z)
  });  
};

const getClosest = (green_cube, blue_cube) => {
  let minDistance = 1000; 
  let closestIndex = 0;
  
  blue_cube.forEach((cube, index) => {
    const distance = calculateDistance3d(green_cube, cube);
    const loopedDistance = calculateLoopedDistance(green_cube, cube);
    if (distance < minDistance || loopedDistance < minDistance) {
      minDistance = Math.min(distance, loopedDistance);
      closestIndex = index;
    }
  });
  return closestIndex;
}

console.log(getClosest({x: 9, y: 8, z: 8}, [
  {x: 1, y: 2, z: 2},
  {x: 5, y: 5, z: 3},
  {x: 6, y: 3, z: 4}
]));

console.log(getClosest({x: 9, y: 8, z: 8}, [
  {x: 5, y: 5, z: 3},
  {x: 1, y: 2, z: 2},
  {x: 6, y: 3, z: 4}
]));

At the end of this script there are 2 logs with cube's data. You can test different data there.

I updated / fixed calculateLoopedDistance() function, which was incorrect.

Upvotes: 0

RaffleBuffle
RaffleBuffle

Reputation: 5455

I believe it's often termed wraparound.

To take wraparound into account your distance measure, e.g. for the x dimension, should be:

let x_offset = Math.min((10 + blue.x - green[i].x) % 10, (10 + green[i].x - blue.x) % 10)

x_offset will always be positive.

Upvotes: 1

btilly
btilly

Reputation: 46445

Here is a stupid trick to keep your thinking straight.

Let v be the vector (5, 5, 5) - blue_cube. Add v to every cube's position, adding/subtracting 10 if it goes off an edge. Now the blue cube is at (5, 5, 5) and the shortest path to the other cubes no longer goes off the edge.

In your example, v = (5, 5, 5) - (9, 8, 8) = (-4, -3, -3). The first green cube moves to (1, 2, 2) + (-4, -3, -3) = (-3, -1, -1) = (7, 9, 9) and its distance is 10. The second green cube moves to (5, 5, 3) + (-4, -3, -3) = (1, 2, 0) and its distance is 12. The third green cube moves to (6, 3, 4) + (-4, -3, -3) = (2, 0, 1) and its distance is again 12. So the first is indeed closest.

Upvotes: 0

Related Questions