Studying Box2D-Lite in Javascript, Part 10.1: Creating Convex Hull - Gift Wrapping

There are many different convex hull algorithms. I looked at several, including Jarvis March,

Graham Scan and QuickHull. Simplest is Jarvis March (also known as the gift wrapping algorithm).

The algorithm may be summarized as follows:

• Initialization:

  • Start with a known point on the convex hull (e.g., the right point).

  • Set i = 0 to keep track of the number of steps.

• Main Steps:

  • Find the next point pi+1 such that all other points lie to the left of the line formed by pi and pi+1.

  • Increment i and repeat until you reach the starting point again (i.e., ph = p0).

• Result:

  • The sequence of points obtained during this process forms the convex hull.
    

In simpler terms, imagine wrapping a string around the set of points, ensuring that no points are on the left side of the string.

Its time complexity is O(nh), where n is the number of points and h is the number of points on the convex hull.

/**
 * Create a convex hull from the given array of local points.
 * The count must be in the range [3, b2_maxPolygonVertices].
 * warning the points may be re-ordered, even if they form a
 * convex polygon
 * warning collinear points are handled but not removed.
 * Collinear points may lead to poor stacking behavior.
 * @export
 * @return {box2d.b2PolygonShape}
 * @param {Array.<box2d.b2Vec2>} vertices
 * @param {number=} count
 * @param {number=} start
 */
box2d.b2PolygonShape.prototype.Set = function(vertices, count, start) {
  count = (typeof(count) === 'number') ? (count) : (vertices.length);
  start = (typeof(start) === 'number') ? (start) : (0);

  if (box2d.ENABLE_ASSERTS) {
    box2d.b2Assert(3 <= count && count <= box2d.b2_maxPolygonVertices);
  }
  if (count < 3) {
    return this.SetAsBox(1, 1);
  }

  var n = box2d.b2Min(count, box2d.b2_maxPolygonVertices);

  // Perform welding and copy vertices into local buffer.
  var ps = box2d.b2PolygonShape.prototype.Set.s_ps;
  var tempCount = 0;
  for (var i = 0; i < n; ++i) {
    var /*b2Vec2*/ v = vertices[start + i];

    var /*bool*/ unique = true;
    for (var /*int32*/ j = 0; j < tempCount; ++j) {
      if (box2d.b2DistanceSquared(v, ps[j]) < ((0.5 * box2d.b2_linearSlop) * (0.5 * box2d.b2_linearSlop))) {
        unique = false;
        break;
      }
    }

    if (unique) {
      ps[tempCount++].Copy(v); // ps[tempCount++] = v;
    }
  }

  n = tempCount;
  if (n < 3) {
    // Polygon is degenerate.
    if (box2d.ENABLE_ASSERTS) {
      box2d.b2Assert(false);
    }
    return this.SetAsBox(1.0, 1.0);
  }

  // Create the convex hull using the Gift wrapping algorithm
  // http://en.wikipedia.org/wiki/Gift_wrapping_algorithm

  // Find the right most point on the hull
  var i0 = 0;
  var x0 = ps[0].x;
  for (var i = 1; i < n; ++i) {
    var x = ps[i].x;
    if (x > x0 || (x === x0 && ps[i].y < ps[i0].y)) {
      i0 = i;
      x0 = x;
    }
  }

  var hull = box2d.b2PolygonShape.prototype.Set.s_hull;
  var m = 0;
  var ih = i0;

  for (;;) {
    hull[m] = ih;

    var ie = 0;
    for (var j = 1; j < n; ++j) {
      if (ie === ih) {
        ie = j;
        continue;
      }

      var r = box2d.b2Sub_V2_V2(ps[ie], ps[hull[m]], box2d.b2PolygonShape.prototype.Set.s_r);
      var v = box2d.b2Sub_V2_V2(ps[j], ps[hull[m]], box2d.b2PolygonShape.prototype.Set.s_v);
      var c = box2d.b2Cross_V2_V2(r, v);
      if (c < 0) {
        ie = j;
      }

      // Collinearity check
      if (c === 0 && v.LengthSquared() > r.LengthSquared()) {
        ie = j;
      }
    }

    ++m;
    ih = ie;

    if (ie === i0) {
      break;
    }
  }

  if (m < 3) {
    // Polygon is degenerate
    if (box2d.ENABLE_ASSERTS) {
      box2d.b2Assert(false);
    }
    return this.SetAsBox(1.0, 1.0);
  }

  this.m_count = m;

  // Copy vertices.
  for (var i = 0; i < m; ++i) {
    this.m_vertices[i].Copy(ps[hull[i]]);
  }

  // Compute normals. Ensure the edges have non-zero length.
  for (var i = 0, ict = m; i < ict; ++i) {
    var vertexi1 = this.m_vertices[i];
    var vertexi2 = this.m_vertices[(i + 1) % ict];
    var edge = box2d.b2Sub_V2_V2(vertexi2, vertexi1, box2d.b2Vec2.s_t0); // edge uses s_t0
    if (box2d.ENABLE_ASSERTS) {
      box2d.b2Assert(edge.LengthSquared() > box2d.b2_epsilon_sq);
    }
    box2d.b2Cross_V2_S(edge, 1.0, this.m_normals[i]).SelfNormalize();
  }

  // Compute the polygon centroid.
  box2d.b2PolygonShape.ComputeCentroid(this.m_vertices, m, this.m_centroid);

  return this;
}