CODEWITHSUNDEEP
algorithmpolygon
K..
K..

Reputation: 4233

Counterclockwise Convex Hull Algorithm

I implemented Andrew's monotone chain convex hull algorithm.

I got these points (a, a), (b, b), (c, c), (d, d)

I get (b, b), (d, d), (a, a), (c, c)

I need (b, b), (c, c), (a, a), (d, d)

So my result starts at the right point, but then goes in the wrong clock direction.

This is the example I implemented:

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

Upvotes: 0

Views: 385

Answers (1)

OmG
OmG

Reputation: 18858

Just revert the order of the array elements from the first index to the end. For example, if the result is in array arr[0 .. n]:

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

Upvotes: 1

Related Questions