# 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:

Quote

// 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]);
}

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.

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

## 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 previous content has been restored.   Clear editor

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

×
×