Rewrote this algorithm to be O(nlogn), and it’s oh-so-functional. The tail recursion and case statements were perfectly natural. I’m a convert– I think my next webapp backend will be in Scala.

    def fastConvexHull(points: List[Point2D]) = {
        def ensureConvex(hull: List[Point2D]): List[Point2D] = {
            if (hull.length > 2) {
                val lastThreePoints: List[Point2D] = Utility2D.lastThree(hull);
                if (Utility2D.isRightTurn(lastThreePoints(0), lastThreePoints(1), lastThreePoints(2)))
                    return ensureConvex(Utility2D.dropNextToLast(hull))
            }
            return hull;
        }

        def nextIter(remainingPoints: List[Point2D], hull: List[Point2D]): List[Point2D] = {
            remainingPoints match {
                case point :: rest => nextIter(rest, ensureConvex(hull ::: point :: Nil))
                case Nil => hull
            }
        }

        def hullHalf(points: List[Point2D]): List[Point2D] = {
            nextIter(points.tail.tail, points(0) :: points(1) :: Nil);
        }

        drawLine(hullHalf(points))
        drawLine(hullHalf(points.reverse))
    }