Created
September 14, 2020 01:42
-
-
Save thatsmadden/a193940bb593fb9067cd043c646e44a9 to your computer and use it in GitHub Desktop.
An After Effects expression to calculate a minimum enclosing path shape (the convex hull) around a set of points.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment