Как реализовать алгоритм Джарвиса для выпуклых оболочек?

Question

[Quintis]

Здравствуйте . Есть задачка по поиску точек выпуклости - https://www.codewars.com/kata/5657d8bdafec0a27c800... . Для решения задачи хочу использовать алгоритм Джарвиса - https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D...

Код : https://codesandbox.io/s/awesome-fast-irxqu?file=/...

const hullMethod = (points) => {
  const [oPoint, ...restPoints] = points;
  const hull = [oPoint];
  const angelsObj = {
    angle: 0,
    x: 0,
    y: 0
  };
  // p2 point search by polar angel
  restPoints.forEach((point) => {
    const [x, y] = point;
    const angle = (Math.atan(y / x) * 180) / Math.PI;
    if (angelsObj.angle > angle) {
      [angelsObj.angle, angelsObj.x, angelsObj.y] = [angle, x, y];
    } else if (angelsObj.angle === 0) {
      [angelsObj.angle, angelsObj.x, angelsObj.y] = [angle, x, y];
    }
  });

  // searching other points by cos of angle
  points.forEach(([curX, curY]) => {
    let nextVector = [curX - angelsObj.x, curY - angelsObj.y];
    const cosAngle =
      (angelsObj.x * nextVector[0] + angelsObj.y * nextVector[1]) /
      Math.sqrt(
        Math.pow(angelsObj.x, 2) * Math.pow(nextVector[0], 2) +
          Math.pow(angelsObj.y, 2) * Math.pow(nextVector[1], 2)
      );

    console.log(curX, curY, cosAngle);
  });
};

hullMethod([
  [0, 0],
  [5, 3],
  [0, 5],
  [2, 3]
]);
//expected = [[0, 0], [0, 5], [5, 3]]

Функция нормально определяет вторую точку по полярному углу , но я не знаю как проверять слудующие точки через косинус скалярного произведениея. Как написать более оптимальную реализацию алгоритма ?

Comments

[twobomb]

Когда-то писал что-то подобное, но какой алгоритм использовал не помню

Answer 1

[Wataru]

Нужно векторное произведение. Оно дает синус угла и позволяет понять, что один вектор лежит правее другого.

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

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

Вот набросок кода на C++, думайте, что это псевдокод.

vector<int> ConvexHull(vector<double> x, vector<double> y) {
  int first = ...; // Тут поиск самой нижней-левой точки.
  const int n = x.size();
  int cur = first;
  vector<int> ans{first};
  // Текущий вектор стороны может идти вправо от самой нижней точки.
  double side_x = 1;
  double side_y = 0;
  while (true) { 
    int bsti = -1;
    // Вектор на лучшую точку.
    double bst_x = 0;
    double bst_y = 0;
    // Расстояние до нее.
    double bst_dist = 0;
    for (i = 0; i < n; ++i) {
      if (i == cur) continue;
      // Вектор на текущую точку.
      double cur_x = x[i] - x[cur];
      double cur_y = y[i] - y[cur];
      // Отсекаем точки назад вдоль оболочки на той же стороне.
      // Можно заменить пометкой в bool in_hull[],
      // которая ставится при добавлении точки в ответ (ans).
      if (side_x*cur_y-side_y*cur_x == 0 && side_x*cur_x+side_y*cur_y < 0) continue;
      double vec = bst_x*cur_y-bst_y*cur_x;
      double dist = cur_x*cur_x+cur_y*cur_y;
      // Берем точку, если она правее текущего кандидата. Или на той же прямой, но ближе.
      if (bsti == -1 || vec < 0 || (vec == 0 && dist < bst_dist)) {
        bsti = i;
        bst_dist = dist;
        bst_x = cur_x;
        bst_y = cur_y;
      } 
    }
    // Сделали полный оборот.
    if (bsti == first) break;
    side_x = bst_x;
    side_y = bst_y;
    and.push_back(bsti);
    cur = bsti;
  }
  return ans;
}