Jump to content

FYI: 2D Convex Hull Wrangle


Recommended Posts

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:



// 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

    hull[hi] = pointOnHull;
    newHullPointCandidate = pts[0];
    for( i=1;i<n;i++ )
        if( newHullPointCandidate==pointOnHull || isLeftOf( pts, hull[hi], newHullPointCandidate ) )
            newHullPointCandidate = pts;
    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]);


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.    




  • Like 1
Link to comment
Share on other sites

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).


Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

  • Create New...