Ha, @Mark.Ackerley, uni + work does leave for very little time, but I was intrigued.
I know this has been answered, but here is another method that uses the Graham Scan method for “Gift Wrapping”. The best method is Chans algorithm from what I’ve read though as it is a combination of the Jarvis March and Graham Scan methods.
Here is the Python Code ported over from Thomas Switzers GitHub (I take zero credit for this)…
import clr
clr.AddReference('ProtoGeometry')
from Autodesk.DesignScript.Geometry import *
def ToVals(pt):
return [pt.X,pt.Y,pt.Z]
def ToPts(ptVals):
return Point.ByCoordinates(ptVals[0],ptVals[1],ptVals[2])
def CreateOutline(pts):
crvs = []
i = 0
while i < len(pts):
if i == len(pts)-1:
crvs.append(Line.ByStartPointEndPoint(pts[i],pts[0]))
else:
crvs.append(Line.ByStartPointEndPoint(pts[i],pts[i+1]))
i = i+1
return PolyCurve.ByJoinedCurves(crvs)
'''
Taken from Thomas Switzers awesome GitHub repo and modified to suit Dynamo Context
https://gist.github.com/arthur-e/5cf52962341310f438e96c1f3c3398b8
I take zero credit for this work other than porting it across.
'''
def convex_hull_graham(points):
'''
Returns points on convex hull in CCW order according to Graham's scan algorithm.
By Tom Switzer <thomas.switzer@gmail.com>.
'''
TURN_LEFT, TURN_RIGHT, TURN_NONE = (1, -1, 0)
def cmp(a, b):
return (a > b) - (a < b)
def turn(p, q, r):
return cmp((q[0] - p[0])*(r[1] - p[1]) - (r[0] - p[0])*(q[1] - p[1]), 0)
def _keep_left(hull, r):
while len(hull) > 1 and turn(hull[-2], hull[-1], r) != TURN_LEFT:
hull.pop()
if not len(hull) or hull[-1] != r:
hull.append(r)
return hull
points = [ToVals(p) for p in points]
points = sorted(points)
l = reduce(_keep_left, points, [])
u = reduce(_keep_left, reversed(points), [])
points = l.extend(u[i] for i in range(1, len(u) - 1)) or l
points = [ToPts(p) for p in points]
return CreateOutline(points)
OUT = convex_hull_graham(IN[0])
Cheers,
Dan