Grand test fixup (#138)

* start fixing up tests

* fix up tests + automate with drone

* fiddle with linting

* messing about with drone.yml

* some more fiddling

* hmmm

* add cache

* add vendor directory

* verbose

* ci updates

* update some little things

* update sig

1 files changed, 409 insertions, 0 deletions

diff --git a/vendor/github.com/golang/geo/s2/crossing_edge_query.go b/vendor/github.com/golang/geo/s2/crossing_edge_query.go
new file mode 100644
index 000000000..51852dab4
--- /dev/null
+++ b/vendor/github.com/golang/geo/s2/crossing_edge_query.go
@@ -0,0 +1,409 @@
+// Copyright 2017 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package s2
+
+import (
+	"sort"
+
+	"github.com/golang/geo/r2"
+)
+
+// CrossingEdgeQuery is used to find the Edge IDs of Shapes that are crossed by
+// a given edge(s).
+//
+// Note that if you need to query many edges, it is more efficient to declare
+// a single CrossingEdgeQuery instance and reuse it.
+//
+// If you want to find *all* the pairs of crossing edges, it is more efficient to
+// use the not yet implemented VisitCrossings in shapeutil.
+type CrossingEdgeQuery struct {
+	index *ShapeIndex
+
+	// temporary values used while processing a query.
+	a, b r2.Point
+	iter *ShapeIndexIterator
+
+	// candidate cells generated when finding crossings.
+	cells []*ShapeIndexCell
+}
+
+// NewCrossingEdgeQuery creates a CrossingEdgeQuery for the given index.
+func NewCrossingEdgeQuery(index *ShapeIndex) *CrossingEdgeQuery {
+	c := &CrossingEdgeQuery{
+		index: index,
+		iter:  index.Iterator(),
+	}
+	return c
+}
+
+// Crossings returns the set of edge of the shape S that intersect the given edge AB.
+// If the CrossingType is Interior, then only intersections at a point interior to both
+// edges are reported, while if it is CrossingTypeAll then edges that share a vertex
+// are also reported.
+func (c *CrossingEdgeQuery) Crossings(a, b Point, shape Shape, crossType CrossingType) []int {
+	edges := c.candidates(a, b, shape)
+	if len(edges) == 0 {
+		return nil
+	}
+
+	crosser := NewEdgeCrosser(a, b)
+	out := 0
+	n := len(edges)
+
+	for in := 0; in < n; in++ {
+		b := shape.Edge(edges[in])
+		sign := crosser.CrossingSign(b.V0, b.V1)
+		if crossType == CrossingTypeAll && (sign == MaybeCross || sign == Cross) || crossType != CrossingTypeAll && sign == Cross {
+			edges[out] = edges[in]
+			out++
+		}
+	}
+
+	if out < n {
+		edges = edges[0:out]
+	}
+	return edges
+}
+
+// EdgeMap stores a sorted set of edge ids for each shape.
+type EdgeMap map[Shape][]int
+
+// CrossingsEdgeMap returns the set of all edges in the index that intersect the given
+// edge AB. If crossType is CrossingTypeInterior, then only intersections at a
+// point interior to both edges are reported, while if it is CrossingTypeAll
+// then edges that share a vertex are also reported.
+//
+// The edges are returned as a mapping from shape to the edges of that shape
+// that intersect AB. Every returned shape has at least one crossing edge.
+func (c *CrossingEdgeQuery) CrossingsEdgeMap(a, b Point, crossType CrossingType) EdgeMap {
+	edgeMap := c.candidatesEdgeMap(a, b)
+	if len(edgeMap) == 0 {
+		return nil
+	}
+
+	crosser := NewEdgeCrosser(a, b)
+	for shape, edges := range edgeMap {
+		out := 0
+		n := len(edges)
+		for in := 0; in < n; in++ {
+			edge := shape.Edge(edges[in])
+			sign := crosser.CrossingSign(edge.V0, edge.V1)
+			if (crossType == CrossingTypeAll && (sign == MaybeCross || sign == Cross)) || (crossType != CrossingTypeAll && sign == Cross) {
+				edgeMap[shape][out] = edges[in]
+				out++
+			}
+		}
+
+		if out == 0 {
+			delete(edgeMap, shape)
+		} else {
+			if out < n {
+				edgeMap[shape] = edgeMap[shape][0:out]
+			}
+		}
+	}
+	return edgeMap
+}
+
+// candidates returns a superset of the edges of the given shape that intersect
+// the edge AB.
+func (c *CrossingEdgeQuery) candidates(a, b Point, shape Shape) []int {
+	var edges []int
+
+	// For small loops it is faster to use brute force. The threshold below was
+	// determined using benchmarks.
+	const maxBruteForceEdges = 27
+	maxEdges := shape.NumEdges()
+	if maxEdges <= maxBruteForceEdges {
+		edges = make([]int, maxEdges)
+		for i := 0; i < maxEdges; i++ {
+			edges[i] = i
+		}
+		return edges
+	}
+
+	// Compute the set of index cells intersected by the query edge.
+	c.getCellsForEdge(a, b)
+	if len(c.cells) == 0 {
+		return nil
+	}
+
+	// Gather all the edges that intersect those cells and sort them.
+	// TODO(roberts): Shapes don't track their ID, so we need to range over
+	// the index to find the ID manually.
+	var shapeID int32
+	for k, v := range c.index.shapes {
+		if v == shape {
+			shapeID = k
+		}
+	}
+
+	for _, cell := range c.cells {
+		if cell == nil {
+			continue
+		}
+		clipped := cell.findByShapeID(shapeID)
+		if clipped == nil {
+			continue
+		}
+		edges = append(edges, clipped.edges...)
+	}
+
+	if len(c.cells) > 1 {
+		edges = uniqueInts(edges)
+	}
+
+	return edges
+}
+
+// uniqueInts returns the sorted uniqued values from the given input.
+func uniqueInts(in []int) []int {
+	var edges []int
+	m := make(map[int]bool)
+	for _, i := range in {
+		if m[i] {
+			continue
+		}
+		m[i] = true
+		edges = append(edges, i)
+	}
+	sort.Ints(edges)
+	return edges
+}
+
+// candidatesEdgeMap returns a map from shapes to the superse of edges for that
+// shape that intersect the edge AB.
+//
+// CAVEAT: This method may return shapes that have an empty set of candidate edges.
+// However the return value is non-empty only if at least one shape has a candidate edge.
+func (c *CrossingEdgeQuery) candidatesEdgeMap(a, b Point) EdgeMap {
+	edgeMap := make(EdgeMap)
+
+	// If there are only a few edges then it's faster to use brute force. We
+	// only bother with this optimization when there is a single shape.
+	if len(c.index.shapes) == 1 {
+		// Typically this method is called many times, so it is worth checking
+		// whether the edge map is empty or already consists of a single entry for
+		// this shape, and skip clearing edge map in that case.
+		shape := c.index.Shape(0)
+
+		// Note that we leave the edge map non-empty even if there are no candidates
+		// (i.e., there is a single entry with an empty set of edges).
+		edgeMap[shape] = c.candidates(a, b, shape)
+		return edgeMap
+	}
+
+	// Compute the set of index cells intersected by the query edge.
+	c.getCellsForEdge(a, b)
+	if len(c.cells) == 0 {
+		return edgeMap
+	}
+
+	// Gather all the edges that intersect those cells and sort them.
+	for _, cell := range c.cells {
+		for _, clipped := range cell.shapes {
+			s := c.index.Shape(clipped.shapeID)
+			for j := 0; j < clipped.numEdges(); j++ {
+				edgeMap[s] = append(edgeMap[s], clipped.edges[j])
+			}
+		}
+	}
+
+	if len(c.cells) > 1 {
+		for s, edges := range edgeMap {
+			edgeMap[s] = uniqueInts(edges)
+		}
+	}
+
+	return edgeMap
+}
+
+// getCells returns the set of ShapeIndexCells that might contain edges intersecting
+// the edge AB in the given cell root. This method is used primarily by loop and shapeutil.
+func (c *CrossingEdgeQuery) getCells(a, b Point, root *PaddedCell) []*ShapeIndexCell {
+	aUV, bUV, ok := ClipToFace(a, b, root.id.Face())
+	if ok {
+		c.a = aUV
+		c.b = bUV
+		edgeBound := r2.RectFromPoints(c.a, c.b)
+		if root.Bound().Intersects(edgeBound) {
+			c.computeCellsIntersected(root, edgeBound)
+		}
+	}
+
+	if len(c.cells) == 0 {
+		return nil
+	}
+
+	return c.cells
+}
+
+// getCellsForEdge populates the cells field to the set of index cells intersected by an edge AB.
+func (c *CrossingEdgeQuery) getCellsForEdge(a, b Point) {
+	c.cells = nil
+
+	segments := FaceSegments(a, b)
+	for _, segment := range segments {
+		c.a = segment.a
+		c.b = segment.b
+
+		// Optimization: rather than always starting the recursive subdivision at
+		// the top level face cell, instead we start at the smallest S2CellId that
+		// contains the edge (the edge root cell). This typically lets us skip
+		// quite a few levels of recursion since most edges are short.
+		edgeBound := r2.RectFromPoints(c.a, c.b)
+		pcell := PaddedCellFromCellID(CellIDFromFace(segment.face), 0)
+		edgeRoot := pcell.ShrinkToFit(edgeBound)
+
+		// Now we need to determine how the edge root cell is related to the cells
+		// in the spatial index (cellMap). There are three cases:
+		//
+		//  1. edgeRoot is an index cell or is contained within an index cell.
+		//     In this case we only need to look at the contents of that cell.
+		//  2. edgeRoot is subdivided into one or more index cells. In this case
+		//     we recursively subdivide to find the cells intersected by AB.
+		//  3. edgeRoot does not intersect any index cells. In this case there
+		//     is nothing to do.
+		relation := c.iter.LocateCellID(edgeRoot)
+		if relation == Indexed {
+			// edgeRoot is an index cell or is contained by an index cell (case 1).
+			c.cells = append(c.cells, c.iter.IndexCell())
+		} else if relation == Subdivided {
+			// edgeRoot is subdivided into one or more index cells (case 2). We
+			// find the cells intersected by AB using recursive subdivision.
+			if !edgeRoot.isFace() {
+				pcell = PaddedCellFromCellID(edgeRoot, 0)
+			}
+			c.computeCellsIntersected(pcell, edgeBound)
+		}
+	}
+}
+
+// computeCellsIntersected computes the index cells intersected by the current
+// edge that are descendants of pcell and adds them to this queries set of cells.
+func (c *CrossingEdgeQuery) computeCellsIntersected(pcell *PaddedCell, edgeBound r2.Rect) {
+
+	c.iter.seek(pcell.id.RangeMin())
+	if c.iter.Done() || c.iter.CellID() > pcell.id.RangeMax() {
+		// The index does not contain pcell or any of its descendants.
+		return
+	}
+	if c.iter.CellID() == pcell.id {
+		// The index contains this cell exactly.
+		c.cells = append(c.cells, c.iter.IndexCell())
+		return
+	}
+
+	// Otherwise, split the edge among the four children of pcell.
+	center := pcell.Middle().Lo()
+
+	if edgeBound.X.Hi < center.X {
+		// Edge is entirely contained in the two left children.
+		c.clipVAxis(edgeBound, center.Y, 0, pcell)
+		return
+	} else if edgeBound.X.Lo >= center.X {
+		// Edge is entirely contained in the two right children.
+		c.clipVAxis(edgeBound, center.Y, 1, pcell)
+		return
+	}
+
+	childBounds := c.splitUBound(edgeBound, center.X)
+	if edgeBound.Y.Hi < center.Y {
+		// Edge is entirely contained in the two lower children.
+		c.computeCellsIntersected(PaddedCellFromParentIJ(pcell, 0, 0), childBounds[0])
+		c.computeCellsIntersected(PaddedCellFromParentIJ(pcell, 1, 0), childBounds[1])
+	} else if edgeBound.Y.Lo >= center.Y {
+		// Edge is entirely contained in the two upper children.
+		c.computeCellsIntersected(PaddedCellFromParentIJ(pcell, 0, 1), childBounds[0])
+		c.computeCellsIntersected(PaddedCellFromParentIJ(pcell, 1, 1), childBounds[1])
+	} else {
+		// The edge bound spans all four children. The edge itself intersects
+		// at most three children (since no padding is being used).
+		c.clipVAxis(childBounds[0], center.Y, 0, pcell)
+		c.clipVAxis(childBounds[1], center.Y, 1, pcell)
+	}
+}
+
+// clipVAxis computes the intersected cells recursively for a given padded cell.
+// Given either the left (i=0) or right (i=1) side of a padded cell pcell,
+// determine whether the current edge intersects the lower child, upper child,
+// or both children, and call c.computeCellsIntersected recursively on those children.
+// The center is the v-coordinate at the center of pcell.
+func (c *CrossingEdgeQuery) clipVAxis(edgeBound r2.Rect, center float64, i int, pcell *PaddedCell) {
+	if edgeBound.Y.Hi < center {
+		// Edge is entirely contained in the lower child.
+		c.computeCellsIntersected(PaddedCellFromParentIJ(pcell, i, 0), edgeBound)
+	} else if edgeBound.Y.Lo >= center {
+		// Edge is entirely contained in the upper child.
+		c.computeCellsIntersected(PaddedCellFromParentIJ(pcell, i, 1), edgeBound)
+	} else {
+		// The edge intersects both children.
+		childBounds := c.splitVBound(edgeBound, center)
+		c.computeCellsIntersected(PaddedCellFromParentIJ(pcell, i, 0), childBounds[0])
+		c.computeCellsIntersected(PaddedCellFromParentIJ(pcell, i, 1), childBounds[1])
+	}
+}
+
+// splitUBound returns the bound for two children as a result of spliting the
+// current edge at the given value U.
+func (c *CrossingEdgeQuery) splitUBound(edgeBound r2.Rect, u float64) [2]r2.Rect {
+	v := edgeBound.Y.ClampPoint(interpolateFloat64(u, c.a.X, c.b.X, c.a.Y, c.b.Y))
+	// diag indicates which diagonal of the bounding box is spanned by AB:
+	// it is 0 if AB has positive slope, and 1 if AB has negative slope.
+	var diag int
+	if (c.a.X > c.b.X) != (c.a.Y > c.b.Y) {
+		diag = 1
+	}
+	return splitBound(edgeBound, 0, diag, u, v)
+}
+
+// splitVBound returns the bound for two children as a result of spliting the
+// current edge into two child edges at the given value V.
+func (c *CrossingEdgeQuery) splitVBound(edgeBound r2.Rect, v float64) [2]r2.Rect {
+	u := edgeBound.X.ClampPoint(interpolateFloat64(v, c.a.Y, c.b.Y, c.a.X, c.b.X))
+	var diag int
+	if (c.a.X > c.b.X) != (c.a.Y > c.b.Y) {
+		diag = 1
+	}
+	return splitBound(edgeBound, diag, 0, u, v)
+}
+
+// splitBound returns the bounds for the two childrenn as a result of spliting
+// the current edge into two child edges at the given point (u,v). uEnd and vEnd
+// indicate which bound endpoints of the first child will be updated.
+func splitBound(edgeBound r2.Rect, uEnd, vEnd int, u, v float64) [2]r2.Rect {
+	var childBounds = [2]r2.Rect{
+		edgeBound,
+		edgeBound,
+	}
+
+	if uEnd == 1 {
+		childBounds[0].X.Lo = u
+		childBounds[1].X.Hi = u
+	} else {
+		childBounds[0].X.Hi = u
+		childBounds[1].X.Lo = u
+	}
+
+	if vEnd == 1 {
+		childBounds[0].Y.Lo = v
+		childBounds[1].Y.Hi = v
+	} else {
+		childBounds[0].Y.Hi = v
+		childBounds[1].Y.Lo = v
+	}
+
+	return childBounds
+}