Поиск / сортировка многомерных массивов

Question

Я создал многомерный массив на основе координат x / y периметра круга. Объект можно перетащить по дуге (в javascript), а затем «уронить» в любое место на нем. Проблема в том, что мне нужно найти координаты x и y, наиболее близкие к месту, где объект «отброшен».

Мое текущее решение заключается в циклическом прохождении массива и нахождении ближайшего к x значения, а затем повторном цикле, чтобы найти координату y, но она выглядит не очень чистой, и с ней возникают проблемы.

У кого-нибудь есть предложения?

Спасибо!

Answer 1

Итак, посмотрим.Мы предполагаем предопределенный набор (x, y) координат.Вам дана другая точка, и вы должны найти ближайший элемент массива к данной точке.Я собираюсь предположить, что «ближайший» означает наименьшее пифагорейское или евклидово расстояние от данной точки до каждой из других точек.

Самый простой алгоритм, вероятно, самый лучший (если вы хотите посмотреть на других в Википедия , есть на это).Поскольку вы не дали нам никакого кода для структуры, я собираюсь предположить массив объектов, каждый из которых имеет свойство x и y, то же самое для данной точки.

var findNearestPoint = function (p, points) {
  var minDist = Number.POSITIVE_INFINITY,
      minPoint = -1,
      i,
      l,
      curDist,
      sqr = function(x) { return x * x; };

  for (i = 0, l = points.length; i < l; i++) {
    curDist = sqr(p.x - points[i].x) + sqr(p.y - points[i].y);
    if (curDist < minDist) {
      minDist = curDist;
      minPoint = i;
    }
  } 
  return points[i];
};

(Не проверено, но вы поняли.)

Answer 2

Если ваши массивы создаются в последовательном порядке (от наименьшего к наибольшему или от наибольшего к наименьшему), вы можете использовать введение алгоритма двоичного поиска.

1. Получить средний элемент массива x.
2. Если x равен вашему значению, остановитесь и ищите y, в противном случае.
   1. Если x меньше, ищите в нижней половине массива (начиная с шага 1).
   2. Если x больше, ищите в верхней половине массива (начиная с шага 1).

Тогда используйте ту же формулу для y. Возможно, вам придется немного изменить алгоритм, чтобы он работал с ближайшим подходящим элементом. Не увидев ваш массив, я не могу предложить код для решения проблемы.