JavaScript. Как найти максимально приближённое значение массива в многомерном массиве?

Question

У меня есть многомерный массив с локациями:

const locations = [
    [55.79749504565197, 37.5407153847656],
    [51.66109513550912, 39.19964245473753],
    [57.62662119485742, 39.89367465100093],
    [58.04855727216249, 38.85813673976128],
    [57.00040249293972, 40.973840485275254],
    [51.73096145146215, 36.192820361190755],
    [53.243644660620774, 34.36328412094874]
]

И есть массив [55.75222, 37.61556]. Нужно найти максимально приближённый к нему массив в многомерном массиве. Из примеров это будет locations[0]. Если у нас будет [57.4, 41.2], то должен быть locations[4]

Answer 1

const locations = [
  [55.79749504565197, 37.5407153847656],
  [51.66109513550912, 39.19964245473753],
  [57.62662119485742, 39.89367465100093],
  [58.04855727216249, 38.85813673976128],
  [57.00040249293972, 40.973840485275254],
  [51.73096145146215, 36.192820361190755],
  [53.243644660620774, 34.36328412094874],
  [60.6, 65.8]
];

const locateUser = (cities, me) => {

  const min = {
    distance: Infinity,
    index: null,
    city: null
  };
  
  for (let i = 0; i < cities.length; i++) {
    const city = cities[i];
    const s = Math.sqrt((me[0] - city[0]) ** 2 + (me[1] - city[1]) ** 2);
    if (s < min.distance) {
      min.distance = s;
      min.index = i;
      min.city = city;
    }
  }
  
  
  return min.city;
};

const result = locateUser(locations, [70.7, 70.9]);
console.log(result);

Answer 2

Догадка

В вопросе не сказано в чём заданы координаты. Похоже это широта/долгота в градусах:

55.79749504565197  / 37.5407153847656   - точка в Москве
51.66109513550912  / 39.19964245473753  - точка в Воронеже
57.62662119485742  / 39.89367465100093  - точка в Ярославле
58.04855727216249  / 38.85813673976128  - точка в Рыбинске
57.00040249293972  / 40.973840485275254 - точка в Иваново
51.73096145146215  / 36.192820361190755 - точка в Курске
53.243644660620774 / 34.36328412094874  - точка в Брянске

Вероятность того что так случайно точки попали в города России очень мала.

Теорема Пифагора

Если это широты и долготы, нельзя искать ближайшую точку используя теорему Пифагора. Например сосчитаем расстояния от Гуся-Хрустального до Москвы и Ярославля:

55.619419         / 40.657307          - Гусь-Хрустальный
55.79749504565197 / 37.5407153847656   - Москвa
57.62662119485742 / 39.89367465100093  - Ярославль

Гусь-Хрустальный - Москва по теореме Пифагора:

((55.619419 - 55.79749504565197)^2 +
+ (40.657307 - 37.5407153847656)^2)^0.5 = 3.1216749308959835

Гусь-Хрустальный - Ярославль по теореме Пифагора:

((55.619419 - 57.62662119485742)^2 +
+ (40.657307 - 39.89367465100093)^2)^0.5 = 2.147555590777172

От Гуся-Хрустального до Ярославля ближе? Нет, если измерить расстояния по прямой в километрах то получится что до Москвы 196 км, а до Ярославля 228 км. Москва ближе. Причина расхождения в том что градус долготы "короче" градуса широты в наших широтах.

Аккуратный расчёт

Формулы можно найти в Википедии: Great-circle distance#Computational formulas. Расстояние вычисляется как центральный угол между двумя точками на глобусе:

const deg_to_rad = deg => deg / 180 * Math.PI;

const hav = a => Math.sin(a / 2) ** 2;
const ahav = a => 2 * Math.asin(Math.sqrt(a));

const central_angle = (loc1, loc2) => {
    const dlong = deg_to_rad(loc1[1] - loc2[1]);
    const lat1 = deg_to_rad(loc1[0]);
    const lat2 = deg_to_rad(loc2[0]);

    return ahav(
        hav(lat2 - lat1) +
        Math.cos(lat1) * Math.cos(lat2) * hav(dlong)
    );
};

const nearest = (locations, request) => {
    let min_dist = Number.POSITIVE_INFINITY;
    let nearest = undefined;
    for (const loc of locations) {
        const dist = central_angle(loc, request);
        if (dist < min_dist) {
            min_dist = dist;
            nearest = loc;
        }
    }
    return nearest;
};

const locations = [
    [55.79749504565197, 37.5407153847656],
    [51.66109513550912, 39.19964245473753],
    [57.62662119485742, 39.89367465100093],
    [58.04855727216249, 38.85813673976128],
    [57.00040249293972, 40.973840485275254],
    [51.73096145146215, 36.192820361190755],
    [53.243644660620774, 34.36328412094874]
];

for (const request of [[55.75222, 37.61556], [57.4, 41.2]]) {
    console.log(request, '->', nearest(locations, request));
}

$ node nearest.js 
[ 55.75222, 37.61556 ] -> [ 55.79749504565197, 37.5407153847656 ]
[ 57.4, 41.2 ] -> [ 57.00040249293972, 40.973840485275254 ]

БЛОГ НА HUSL

JavaScript. Как найти максимально приближённое значение массива в многомерном массиве?

Ответы (2 шт):