QuickHull computes the convex hull of a set of 2D points using a divide-and-conquer strategy similar to QuickSort. Average complexity is Θ(n log n); worst case O(n²). The algorithm splits the point set along the line connecting the leftmost and rightmost points, then recursively finds the farthest point on each side and discards all points inside the resulting triangle.

Starting Point

Find the two anchor points — minimum and maximum X — and connect them to form the initial dividing line. Points on the right and left of this line are processed independently:

python

import clr
clr.AddReference('ProtoGeometry')
from Autodesk.DesignScript.Geometry import *

def min_max_x(pts):
    """Return the point with the minimum X and the point with the maximum X."""
    minXPoint = maxXPoint = pts[0]
    for pt in pts:
        if pt.X < minXPoint.X: minXPoint = pt
        if pt.X > maxXPoint.X: maxXPoint = pt
    return minXPoint, maxXPoint

Helpers

The cross-product sign classifies each point as left or right of a directed line. The farthest point from a line is the next hull vertex candidate:

python

def PointSide(point, line):
    """
    Returns +1 if point is to the right of the directed line (start → end),
    -1 if to the left, 0 if on the line.
    Cross-product sign of vectors (SP→EP) and (SP→point).
    """
    sp = line.StartPoint
    ep = line.EndPoint
    d = (point.X - sp.X) * (ep.Y - sp.Y) - (point.Y - sp.Y) * (ep.X - sp.X)
    return 1 if d > 0 else (-1 if d < 0 else 0)

def PointsRightSide(points, line):
    return [pt for pt in points if PointSide(pt, line) > 0]

def PointsLeftSide(points, line):
    return [pt for pt in points if PointSide(pt, line) < 0]

def PointFarthest(points, line):
    """Return the point with the greatest distance to the line, or None."""
    if not points:
        return None
    return max(points, key=lambda pt: pt.DistanceTo(line))

def MainTriangle(point, line):
    if point is None:
        return None
    return Polygon.ByPoints([line.StartPoint, point, line.EndPoint])

def GetRestOfPoints(polygon, points):
    """Return points that lie outside the triangle (not contained, not on boundary)."""
    if polygon is None:
        return None
    return [p for p in points
            if not Polygon.ContainmentTest(polygon, p) and not polygon.DoesIntersect(p)]

Complete Solution

At each recursive step: find the farthest point, form the triangle with the current line, remove all points inside the triangle, then recurse on the two sub-lines. The recursion bottoms out when no points remain on the outside of a line — that line is a hull edge:

python

def GetNextPointRight(line, points):
    """
    Divide-and-conquer step for the right side.
    Find the farthest point, build the triangle, discard interior points,
    then recurse on the two sub-lines created by inserting the farthest point.
    """
    ptsRight     = PointsRightSide(points, line)
    farPoint     = PointFarthest(ptsRight, line)
    triangle     = MainTriangle(farPoint, line)
    restOfPoints = GetRestOfPoints(triangle, ptsRight)

    if not ptsRight:
        return line  # base case — no more points on this side

    r1 = GetNextPointRight(Line.ByStartPointEndPoint(line.StartPoint, farPoint), restOfPoints)
    r2 = GetNextPointRight(Line.ByStartPointEndPoint(farPoint, line.EndPoint),   restOfPoints)
    return [r1, r2]

def GetNextPointLeft(line, points):
    """Mirror of GetNextPointRight for the left side."""
    ptsLeft      = PointsLeftSide(points, line)
    farPoint     = PointFarthest(ptsLeft, line)
    triangle     = MainTriangle(farPoint, line)
    restOfPoints = GetRestOfPoints(triangle, ptsLeft)

    if not ptsLeft:
        return line

    r1 = GetNextPointLeft(Line.ByStartPointEndPoint(line.StartPoint, farPoint), restOfPoints)
    r2 = GetNextPointLeft(Line.ByStartPointEndPoint(farPoint, line.EndPoint),   restOfPoints)
    return [r1, r2]

def quick(pts):
    minXPoint, maxXPoint = min_max_x(pts)
    lineMinMaxX = Line.ByStartPointEndPoint(minXPoint, maxXPoint)
    ptsRight    = PointsRightSide(pts, lineMinMaxX)
    ptsLeft     = PointsLeftSide(pts, lineMinMaxX)
    resultRight = GetNextPointRight(lineMinMaxX, ptsRight)
    resultLeft  = GetNextPointLeft(lineMinMaxX, ptsLeft)
    return resultLeft, resultRight

OUT = quick(IN[0])

QuickHull - Divide and conquer

Starting Point

Helpers

Complete Solution