An After Effects expression to calculate a minimum enclosing path shape (the convex hull) around a set of points.

convex-hull-expression

// This is a messy way to calculate a minimum enclosing shape given a set of 2D points. Just replace the "points[0]=.... ;" section with your own selection of points.

// The expression uses a Graham scan to find the points on the outer edge of the shape-- utilizing a cross product to find the point with the greatest "left-turn" for the next vertex on the hull.

// It's meant to go on a path shape-- either a mask path or a Shape Layer path.

function indexOfMin(arr) { // find index of point that has the lowest x-position.
    if (arr.length === 0) {
        return -1;
    }

    var min = arr[0][0];
    var minIndex = 0;

    for (var i = 1; i < arr.length; i++) {
        if (arr[i][0] < min) {
            minIndex = i;
            min = arr[i][0];
        }
    }

    return minIndex;
}

// create the necessary things

points = [];
t=[];
hull = [];
pInd = [];
hullInd = 0;


points[0] = fromCompToSurface(thisComp.layer("ant_0200").toComp([0,0,0]));
points[1] = fromCompToSurface(thisComp.layer("ant_0201").toComp([0,0,0]));
points[2] = fromCompToSurface(thisComp.layer("ant_0202").toComp([0,0,0]));
points[3] = fromCompToSurface(thisComp.layer("ant_0203").toComp([0,0,0]));
points[4] = fromCompToSurface(thisComp.layer("ant_0204").toComp([0,0,0]));
points[5] = fromCompToSurface(thisComp.layer("ant_0205").toComp([0,0,0]));
points[6] = fromCompToSurface(thisComp.layer("ant_0206").toComp([0,0,0]));
points[7] = fromCompToSurface(thisComp.layer("ant_0207").toComp([0,0,0]));
points[8] = fromCompToSurface(thisComp.layer("ant_0208").toComp([0,0,0]));
points[9] = fromCompToSurface(thisComp.layer("ant_0209").toComp([0,0,0]));
points[10] = fromCompToSurface(thisComp.layer("ant_0210").toComp([0,0,0]));
points[11] = fromCompToSurface(thisComp.layer("ant_0211").toComp([0,0,0]));
points[12] = fromCompToSurface(thisComp.layer("ant_0212").toComp([0,0,0]));
points[13] = fromCompToSurface(thisComp.layer("ant_0213").toComp([0,0,0]));
points[14] = fromCompToSurface(thisComp.layer("ant_0214").toComp([0,0,0]));
points[15] = fromCompToSurface(thisComp.layer("ant_0215").toComp([0,0,0]));
points[16] = fromCompToSurface(thisComp.layer("ant_0216").toComp([0,0,0]));
points[17] = fromCompToSurface(thisComp.layer("ant_0217").toComp([0,0,0]));
points[18] = fromCompToSurface(thisComp.layer("ant_0218").toComp([0,0,0]));


// simple modulo to make sure our indices stay in-range of the length of the points array

function cInd(_i){ 
  return _i%points.length;
}

// find left-most point

i1 = indexOfMin(points);


// add leftMost to hullArray
addToHull(i1);

// tentative winner
cwInd = cInd(i1+1); 

// loop through every point to find the actual winner
for (var j = 1; j < points.length; j++){

	checkInd = cInd(pInd[hullInd-1]+j); // the contender

	v1 = sub(hull[hullInd-1], points[cwInd]); // vector from the last point on the hull to the tentative winner
	v2 = sub(hull[hullInd-1], points[checkInd]); // vector from the last point on the hull to the contender
	if (cross(v1,v2)[2] < 0){ // if v2 is counter-clockwise to v1, v2 is the new winner
	  cwInd = checkInd;
	}

	// when we reach the end of the loop, add the winner to the hull

	if (j == points.length-1){
		reached = addToHull(cwInd);
		cwInd = cInd(cwInd+1);

		// reset loop until the winning hull point is the left-most point again
		if (!reached){
		j=1; 
		}
	}
}



function addToHull(_pInd) {
    temp = hullInd;
    endReached = false;

    if (pInd[0] == null || pInd[0] !== _pInd) {
        hull[hullInd] = points[_pInd]; // add winning point to hull
        pInd[hullInd] = _pInd; // store index of this point's index 
        t[hullInd] = [0, 0]; // add point tangents
        hullInd++;
    } else {
        endReached = true;
    }
    return endReached;
}

createPath(hull, t, t, true);