逆时针凸包算法

Question

我实现了Andrew's monotone chain convex hull algorithm。

我得到了这些分数(a, a), (b, b), (c, c), (d, d)

我得到(b, b), (d, d), (a, a), (c, c)

我需要(b, b), (c, c), (a, a), (d, d)

所以我的结果从正确的点开始，但随后时钟方向错误。

这是我实现的例子：

function cross(a, b, o) {
   return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
}

/**
 * @param points An array of [X, Y] coordinates
 */
function convexHull(points) {
   points.sort(function(a, b) {
      return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0];
   });

   var lower = [];
   for (var i = 0; i < points.length; i++) {
      while (lower.length >= 2 && cross(lower[lower.length - 2], lower[lower.length - 1], points[i]) <= 0) {
         lower.pop();
      }
      lower.push(points[i]);
   }

   var upper = [];
   for (var i = points.length - 1; i >= 0; i--) {
      while (upper.length >= 2 && cross(upper[upper.length - 2], upper[upper.length - 1], points[i]) <= 0) {
         upper.pop();
      }
      upper.push(points[i]);
   }

   upper.pop();
   lower.pop();
   return lower.concat(upper);
}

Answer 1

只需将数组元素的顺序从第一个索引还原到末尾。例如，如果结果在数组 arr[0 .. n]:

中

arr[0] | revert(arr[1 .. n])

逆时针凸包算法

Counterclockwise Convex Hull Algorithm

algorithm

polygon