func referencePointForShape()

in s2/shapeutil.go [113:169]
37 lines of code
11 McCabe index (conditional complexity)

func referencePointForShape(shape Shape) ReferencePoint {
	if shape.NumEdges() == 0 {
		// A shape with no edges is defined to be full if and only if it
		// contains at least one chain.
		return OriginReferencePoint(shape.NumChains() > 0)
	}
	// Define a "matched" edge as one that can be paired with a corresponding
	// reversed edge. Define a vertex as "balanced" if all of its edges are
	// matched. In order to determine containment, we must find an unbalanced
	// vertex. Often every vertex is unbalanced, so we start by trying an
	// arbitrary vertex.
	edge := shape.Edge(0)

	if ref, ok := referencePointAtVertex(shape, edge.V0); ok {
		return ref
	}

	// That didn't work, so now we do some extra work to find an unbalanced
	// vertex (if any). Essentially we gather a list of edges and a list of
	// reversed edges, and then sort them. The first edge that appears in one
	// list but not the other is guaranteed to be unmatched.
	n := shape.NumEdges()
	var edges = make([]Edge, n)
	var revEdges = make([]Edge, n)
	for i := 0; i < n; i++ {
		edge := shape.Edge(i)
		edges[i] = edge
		revEdges[i] = Edge{V0: edge.V1, V1: edge.V0}
	}

	sortEdges(edges)
	sortEdges(revEdges)

	for i := 0; i < n; i++ {
		if edges[i].Cmp(revEdges[i]) == -1 { // edges[i] is unmatched
			if ref, ok := referencePointAtVertex(shape, edges[i].V0); ok {
				return ref
			}
		}
		if revEdges[i].Cmp(edges[i]) == -1 { // revEdges[i] is unmatched
			if ref, ok := referencePointAtVertex(shape, revEdges[i].V0); ok {
				return ref
			}
		}
	}

	// All vertices are balanced, so this polygon is either empty or full except
	// for degeneracies. By convention it is defined to be full if it contains
	// any chain with no edges.
	for i := 0; i < shape.NumChains(); i++ {
		if shape.Chain(i).Length == 0 {
			return OriginReferencePoint(true)
		}
	}

	return OriginReferencePoint(false)
}