How to implement Jarvis algorithm for convex hulls?

Question

JavaScript

Hello . There is a task to find bulge points - https://www.codewars.com/kata/5657d8bdafec0a27c800... . To solve the problem, I want to use the Jarvis algorithm - https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D...

Code: 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 = 

The function normally determines the second point by the polar angle, but I do not know how to check the next points through the cosine of the dot product. How to write a more optimal implementation of the algorithm?

Answer 1

We need a vector product. It gives the sine of the angle and makes it clear that one vector lies to the right of the other.
If you ignore points already on the convex hull, then all the remaining points will lie in one half-plane relative to the given one. And then you need to choose a point, the vector to which is to the right. And if the vectors are collinear, then the nearest (or the farthest, if you want to skip the points on the boundary of the convex hull.
There is one problem here - if you do not throw out points already from the shell, then there may be a situation when you consider a move from a point in the middle of a side in a convex shell. Then the forward and backward points along the boundary cannot be separated in this way. All vector products will be zero, and the nearest point can be either behind or in front. But you can add a check with the previous side of the shell. A vector to the next point, if it gives 0 when multiplied with this one, then it must give a positive dot product.
Here's a draft of the C++ code, think it's pseudocode.

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;
}