For the beginning we have two points with coordinates x, y, z: start(0, 0, 0) and randomly generated r(x, y, z) where x, y, z are random integers from 0 to 100.

There is a function (already written by me) that calculates distance between two dots.

I need to write another function that takes only distance as an argument. We need to call the first function using different coordinates inside start point (to change distance between points) until we find the coordinates of r (that is distance should be equal to 0).

What is the best algorithm in this case?

CodePudding user response：

I was curious as for performance for calculating all points (in 3d space of integers) that match (the naive algorithm).

function distance_squared(x, y, z) {
  return x * x   y * y   z * z;
}

var r_squared = 9230
for (var x = 0; x <= 100; x  ) {
  for (var y = 0; y <= 100; y  ) {
    for (var z = 0; z <= 100; z  ) {
      if (distance_squared(x, y, z) == r_squared) {
        console.log(x, y, z)
      }
    }
  }
}

// console.log(distance_squared(79,42,35))

Now combined with a recent question about isometric projection of 3D coordinates, gives:

function Coords_3D_To_2D(x, y, z) {
  return {
    w: ((x - y) * (Math.sqrt(3) / 2)),
    h: (((-x - y) / 2) - z)
  }
}

function distance_squared(x, y, z) {
  return x * x   y * y   z * z;
}


function Projectile(x, y, speed, direction, duration) {
  Object.assign(this, {
    x,
    y,
    speed,
    direction,
    duration
  });
  this.draw = ctx => {
    ctx.arc(this.x, this.y, 3.75, 0, 2 * Math.PI);
    ctx.fillStyle = 'white';
    ctx.fill();
  }
  this.update = ctx => {
    ctx.beginPath();
    this.x  = Math.cos(this.direction) * this.speed;
    this.y  = Math.sin(this.direction) * this.speed;
    this.draw(ctx);
    this.duration--;
  }
  this.isDone = () => this.duration <= 0;
}



const canvas = document.createElement("canvas");
const ctx = canvas.getContext("2d");
document.body.appendChild(canvas);
canvas.width = window.innerWidth;
canvas.height = window.innerHeight;
var x0 = canvas.width / 2
var y0 = canvas.height / 2;
var projectileArray = []


;
(function update() {
  ctx.fillStyle = "black";
  ctx.fillRect(0, 0, canvas.width, canvas.height);

  for (var i = 0; i < projectileArray.length; i  ) {
    let bullet = projectileArray[i];
    bullet.update(ctx)
  }
  projectileArray = projectileArray.filter(bullet => !bullet.isDone());



  requestAnimationFrame(update);
})();

document.addEventListener("keydown", event => {
  if (event.code in {
      Space: false,
    }) {
    let bullet = new Projectile(x0, y0, 3, 2, 1500)
    projectileArray.push(bullet);
  }
  // console.log("boom")
});



var r_squared = 9230
for (var x = 0; x <= 100; x  ) {
  for (var y = 0; y <= 100; y  ) {
    for (var z = 0; z <= 100; z  ) {
      if (distance_squared(x, y, z) == r_squared) {
        // console.log(x, y, z)
        var cord = Coords_3D_To_2D(x, y, z)
        let bullet = new Projectile(x0   cord.w, y0   cord.h, 1, -Math.PI * 1.5, 500)
        projectileArray.push(bullet);

      }
    }
  }
}

body {
  margin: 0;
  padding: 0;
  overflow: hidden;
}

CodePudding user response：

Given the distance r, what we should learn is to find all nonnegative integer solutions of x^2 y^2 z^2=r^2 and then pick some solution randomly.

We can just enumerate x and y from 1 to r separately, and the check whether r^2-x^2-y^2 is a perfect square number.

The complexity is O(r^2)