Find the nearest 3d point

Question

Let's say I have a player located at: X: 100, Y: 100, Z: 100and I want to find which of the following points is the closest and get it's ID.:

ID: 1, X: 200; Y: 200; Z: 100,
ID: 2, X: 150; Y: 300; Z: 300,
ID: 3, X: 300; Y: 200; Z: 100,
ID: 4, X: 50; Y: 100; Z: 200

How could I do it? What are the maths behind it? If it helps, I already have the following code:

var returnVehicles = [];
        mp.vehicles.forEachInRange(player.position, 100, (vehicle) => {
                if(vehicle.ownerID == player.id) {
                    returnVehicles.push(vehicle.position, vehicle.id);
                }
            }
        );

It loops through the vehicles in a range of a 100 and adds into an array the IDs and positions of the ones that belong to the player. However, I don't know what to do with this.

Someone recommend me the .sort() method, but that doesn't seem to work, as it only gets the smallest coordinate, not the nearest.

@EDIT: MY FULL CODE

function distance3D(posA, posB) {
    const dX = posA.X - posB.X;
    const dY = posA.Y - posB.Y;
    const dZ = posA.Z - posB.Z;
    return Math.sqrt(dX * dX + dY * dY + dZ * dZ);
}

const vehiclesAndDistances = [];

function lockPlayerVehicle (player) {
    let vehicle = player.vehicle;
    if (vehicle) {
        //IRRELEVANT
    }
    else {
        mp.vehicles.forEachInRange(player.position, 40, (vehicle) => {
                if(vehicle.ownerID == player.id) {
                    vehiclesAndDistances.push({vehicle, distance: distance3D(player, vehicle),});
                }
            }
        );
        vehiclesAndDistances.sort((a, b) => a.distance - b.distance);
        player.outputChatBox("Lista Pequena: " + String(vehiclesAndDistances[0]));
        console.log(vehiclesAndDistances[0], vehiclesAndDistances[0].vehicle.model)
    };
}
mp.events.add("keypress:DOWNARROW", lockPlayerVehicle);

Answer 1

For a small number of vehicles, simply using the Pythagorean algorithm to find the distance between the vehicle and the player is enough. (For more than a few (or if you need to loop this often) you could need to look into a space-partitioning algorithm such as quadtrees to make the lookup more effective.)

// Assumes posA and posB are both objects with X, Y, Z members.
function distance3D(posA, posB) {
  const dX = posA.X - posB.X;
  const dY = posA.Y - posB.Y;
  const dZ = posA.Z - posB.Z;
  return Math.sqrt(dX * dX + dY * dY + dZ * dZ);
}

// Stores objects of shape `{vehicle: ..., distance: number}`
const vehiclesAndDistances = [];

mp.vehicles.forEachInRange(player.position, 100, (vehicle) => {
  if (vehicle.ownerID == player.id) {
    vehiclesAndDistances.push({
      vehicle,
      distance: distance3D(player, vehicle),
    });
  }
});
// Sort the array by the distance
vehiclesAndDistances.sort((a, b) => a.distance - b.distance);

EDIT: As discussed in the comments, if you only need the nearest point, you can reformulate this as

let closestDistance = undefined;
let closestVehicle = undefined;

mp.vehicles.forEachInRange(player.position, 100, (vehicle) => {
  if (vehicle.ownerID === player.id) {
    const distance = distance3D(player, vehicle);
    if (closestDistance === undefined || distance < closestDistance) {
      closestVehicle = vehicle;
      closestDistance = distance;
    }
  }
});

Answer 2

You can use the distance formula. Apply it to each point and choose the minimum. Time complexity is linear, but you're probably running this in a loop per frame, so the overall complexity is quadratic. There are optimizations available. See

• Closest point to a given point
• Finding nearest point in an efficient way

Possible micro-optimizations that don't change the time complexity include avoiding the square root operation, saving the min in one pass, etc.

const dist = (a, b) => Math.sqrt(
  (b.X - a.X) ** 2 +
  (b.Y - a.Y) ** 2 +
  (b.Z - a.Z) ** 2
);

const closest = (target, points, eps=0.00001) => {
  const distances = points.map(e => dist(target, e));
  const closest = Math.min(...distances);
  return points.find((e, i) => distances[i] - closest < eps);
};

const player = {X: 100, Y: 100, Z: 100};
const points = [
  {ID: 1, X: 200, Y: 200, Z: 100},
  {ID: 2, X: 150, Y: 300, Z: 300},
  {ID: 3, X: 300, Y: 200, Z: 100},
  {ID: 4, X: 50,  Y: 100, Z: 200}
];

console.log(closest(player, points));

You can generalize dist to work in any dimension as follows:

const dist = (a, b) => Math.sqrt(
  Object.keys(a).map(k => (b[k] - a[k]) ** 2)
    .reduce((a, e) => a + e)  
);

Answer 3

You can use euclidean distance calculating formula. Put all the coordinates in an array and use map to create a new array of distance which is derived by implementing euclidean formula. You can sort the element of the array in ascending or descending order and find the distance

let currData = [{
    ID: 1,
    X: 200,
    Y: 200,
    Z: 100
  },
  {
    ID: 2,
    X: 150,
    Y: 300,
    Z: 300
  },
  {
    ID: 3,
    X: 300,
    Y: 200,
    Z: 100
  },
  {
    ID: 4,
    X: 50,
    Y: 100,
    Z: 200
  }
]

const vehlPos = {
  X: 250,
  Y: 400,
  Z: 600
};

let getDist = currData.map((item) => {
  const xdiff = Math.pow((vehlPos.X - item.X), 2);
  const ydiff = Math.pow((vehlPos.Y - item.Y), 2);
  const zdiff = Math.pow((vehlPos.Z - item.Z), 2);
  return Math.sqrt(xdiff + ydiff + zdiff)
});

console.log(getDist)

Answer 4

You could convert your objects to points and use vector functions.

Here is a somewhat-complete example of a 3D vector class.

const main = () => {
  const player = { X: 100, Y: 100, Z: 100 };
  const points = [
    { ID: 1, X: 200, Y: 200, Z: 100 },
    { ID: 2, X: 150, Y: 300, Z: 300 },
    { ID: 3, X: 300, Y: 200, Z: 100 },
    { ID: 4, X:  50, Y: 100, Z: 200 }
  ];

  console.log(findClosestPoint(player, points));
};

const findClosestPoint = (player, points) => {
  let { X, Y, Z } = player;
  const pos = new Vector3D(X, Y, Z),
    minDist = points.reduce((res, point, index) => {
      let { X, Y, Z } = point;
      const value = pos.distanceTo(new Vector3D(X, Y, Z));
      return value < res.value ? { index, value } : res;
    }, { index: -1, value: Number.MAX_VALUE });
  console.log('Min distance:', minDist.value);
  return points[minDist.index];
};

class Vector3D {
  constructor (x, y, z) {
    this.x = x;
    this.y = y;
    this.z = z;
  }
  distanceTo (other) {
    return Math.sqrt(
      Math.pow(this.x - other.x, 2) +
      Math.pow(this.y - other.y, 2) +
      Math.pow(this.z - other.z, 2)
    );
  }
}

main();

.as-console-wrapper { top: 0; max-height: 100% !important; }

Output

Min distance: 111.80339887498948
{
  "ID": 4,
  "X": 50,
  "Y": 100,
  "Z": 200
}