func()

in s2/convex_hull_query.go [139:204]

• 38 lines of code
• 8 McCabe index (conditional complexity)

func (q *ConvexHullQuery) ConvexHull() *Loop {
	c := q.CapBound()
	if c.Height() >= 1 {
		// The bounding cap is not convex. The current bounding cap
		// implementation is not optimal, but nevertheless it is likely that the
		// input geometry itself is not contained by any convex polygon. In any
		// case, we need a convex bounding cap to proceed with the algorithm below
		// (in order to construct a point "origin" that is definitely outside the
		// convex hull).
		return FullLoop()
	}

	// Remove duplicates. We need to do this before checking whether there are
	// fewer than 3 points.
	x := make(map[Point]bool)
	r, w := 0, 0 // read/write indexes
	for ; r < len(q.points); r++ {
		if x[q.points[r]] {
			continue
		}
		q.points[w] = q.points[r]
		x[q.points[r]] = true
		w++
	}
	q.points = q.points[:w]

	// This code implements Andrew's monotone chain algorithm, which is a simple
	// variant of the Graham scan. Rather than sorting by x-coordinate, instead
	// we sort the points in CCW order around an origin O such that all points
	// are guaranteed to be on one side of some geodesic through O. This
	// ensures that as we scan through the points, each new point can only
	// belong at the end of the chain (i.e., the chain is monotone in terms of
	// the angle around O from the starting point).
	origin := Point{c.Center().Ortho()}
	sort.Slice(q.points, func(i, j int) bool {
		return RobustSign(origin, q.points[i], q.points[j]) == CounterClockwise
	})

	// Special cases for fewer than 3 points.
	switch len(q.points) {
	case 0:
		return EmptyLoop()
	case 1:
		return singlePointLoop(q.points[0])
	case 2:
		return singleEdgeLoop(q.points[0], q.points[1])
	}

	// Generate the lower and upper halves of the convex hull. Each half
	// consists of the maximal subset of vertices such that the edge chain
	// makes only left (CCW) turns.
	lower := q.monotoneChain()

	// reverse the points
	for left, right := 0, len(q.points)-1; left < right; left, right = left+1, right-1 {
		q.points[left], q.points[right] = q.points[right], q.points[left]
	}
	upper := q.monotoneChain()

	// Remove the duplicate vertices and combine the chains.
	lower = lower[:len(lower)-1]
	upper = upper[:len(upper)-1]
	lower = append(lower, upper...)

	return LoopFromPoints(lower)
}