FYI: 2D Convex Hull Wrangle

[odToad]

Hope its ok to post an answer rather than a question here too. I was looking for a way to compute the convex hull for a bunch of 2D points and found no obvious node/HDA so I wrote one.

Example problem in the attached picture: from all the shown points, eliminate all the yellow ones and create a polygon around with the blue ones. This is an example of a convex hull (wikipedia)

Just create a Attribute Wrangle, set it to "Run Over" "Detail (only once)" and paste the following code into it:

Quote

 

// https://en.wikipedia.org/wiki/Gift_wrapping_algorithm
// jarvis wrapping algorithm for finding the convex hull

// output will always be clockwise in top view

// note this wrangle is getting its data from input 1, not 0. 
// This makes sure the input points dont get spit out as well
// just the convex hull polygon

int n = npoints(1);
vector pts[];
int i;

// find leftmost point in source poly/points
vector minP = { 1e30,0,0 };
for( i=0;i<n;i++ )
{
    pts = point(1,"P",i);
    if( pts.x < minP.x )
        minP = pts;
}

vector pointOnHull, newHullPointCandidate;
vector hull[]; // convex hull to be created

int isLeftOf( vector a; vector p0; vector p1 )
{
    vector va  = normalize(a-p0);
    vector vp1 = normalize(p1-p0);
    vector normal = set( -vp1.z,0,vp1.x );
    return dot(va,normal)>0;
}

// this is from the wikipedia page
pointOnHull = minP;
int hi=0; // hull last point index as we build hull
newHullPointCandidate = {0,0,0}; // just to keep uninited warning off

do
{
    hull[hi] = pointOnHull;
    newHullPointCandidate = pts[0];
    for( i=1;i<n;i++ )
        if( newHullPointCandidate==pointOnHull || isLeftOf( pts, hull[hi], newHullPointCandidate ) )
            newHullPointCandidate = pts;
    hi++;
    pointOnHull = newHullPointCandidate;
} 
while( newHullPointCandidate!=hull[0]  );

// finally, create the convex hull polygon as output
int pr = addprim(1,"poly");
for( hi=0;hi<len(hull);hi++ )
{
    int pt = addpoint(0,hull[hi]);
    addvertex(1,pr,pt);
}

 

Now connect input 1 (thats the second one, not the first one) to a collection of points or a prim

The output of this Convex Hull Wrangle will be a single polygon, clockwise when viewed from above (+y) The reason input 1 rather than input 0 is used is that no source geometry/points appears on the output this way, just the convex hull polygon.

This code assumes that your points all live in the XZ plane, ie y=0 for all points. It only creates a 2D convex hull, not 3D polyhedra.    

 

 

[Noobini]

sorry for posting non-H stuff here...but did mine (not exact but similar) in 3D, I can't show you the code coz it's done with MCG but I can guarantee you there was not one bit of 'code'...it was all based on what I called 'sweeping radar' approach (where on the radar screen, you see a line sweeping radially, when it hits something it goes PIIIIIING !). Shows you being a non-coder should not discourage you from doing something.

This was done because BBox doesn't conform to the contours of your geo...so I wrote my own BSh (ape).