func generateEdgeQueryWithTargets(opts *edgeQueryBenchmarkOptions, query *EdgeQuery, queryIndex *ShapeIndex) (targets []distanceTarget, targetIndexes []*ShapeIndex) {
	const maxTargetsPerIndex = 100
	rand.Seed(opts.randomSeed)
	opts.randomSeed++
	indexCap := CapFromCenterAngle(randomPoint(), opts.radiusKm)
	query.Reset()
	queryIndex.Reset()
	opts.fact(indexCap, opts.numIndexEdges, queryIndex)
	targets = make([]distanceTarget, 0)
	targetIndexes = make([]*ShapeIndex, 0)
	numTargets := maxTargetsPerIndex
	if opts.targetType == queryTypeIndex {
		numTargets = minInt(numTargets, 500000/opts.numTargetEdges)
	}
	for i := 0; i < numTargets; i++ {
		targetDist := fractionToRadius(opts.centerSeparationFraction, opts.radiusKm.Radians())
		targetCap := CapFromCenterAngle(
			sampleBoundaryFromCap(CapFromCenterAngle(indexCap.Center(), targetDist)),
			fractionToRadius(opts.targetRadiusFraction, opts.radiusKm.Radians()))
		switch opts.targetType {
		case queryTypePoint:
			var pt Point
			if opts.chooseTargetFromIndex {
				pt = sampleEdgeFromIndex(queryIndex).V0
			} else {
				pt = targetCap.Center()
			}
			targets = append(targets, NewMinDistanceToPointTarget(pt))
		case queryTypeEdge:
			var edge Edge
			if opts.chooseTargetFromIndex {
				edge = sampleEdgeFromIndex(queryIndex)
			} else {
				edge.V0 = sampleBoundaryFromCap(targetCap)
				edge.V1 = sampleBoundaryFromCap(targetCap)
			}
			targets = append(targets, NewMinDistanceToEdgeTarget(edge))
		case queryTypeCell:
			var cellID CellID
			if opts.chooseTargetFromIndex {
				cellID = sampleCellFromIndex(queryIndex)
			} else {
				cellID = cellIDFromPoint(targetCap.Center()).Parent(
					MaxDiagMetric.ClosestLevel(targetCap.Radius().Radians()))
			}
			targets = append(targets, NewMinDistanceToCellTarget(CellFromCellID(cellID)))
		case queryTypeIndex:
			targetIndex := NewShapeIndex()
			if opts.chooseTargetFromIndex {
				var shape edgeVectorShape
				for i := 0; i < opts.numTargetEdges; i++ {
					edge := sampleEdgeFromIndex(queryIndex)
					shape.Add(edge.V0, edge.V1)
				}
				targetIndex.Add(&shape)
			} else {
				opts.fact(targetCap, opts.numTargetEdges, targetIndex)
			}
			target := NewMinDistanceToShapeIndexTarget(targetIndex)
			target.setIncludeInteriors(opts.includeInteriors)
			targets = append(targets, target)
		default:
			panic(fmt.Sprintf("unknown query target type %v", opts.targetType))
		}
	}
	return targets, targetIndexes
}
generateEdgeQueryWithTargets generates and adds geometry to a ShapeIndex for
use in an edge query.

Approximately numIndexEdges will be generated by the requested generator and
inserted. The geometry is generated within a Cap of the radius specified
by radiusKm (the index radius). Parameters with fraction in their
names are expressed as a fraction of this radius.

Also generates a set of target geometries for the query, based on the
targetType and the input parameters. If targetType is INDEX, then:
(i) the target will have approximately numTargetEdges edges.
(ii) includeInteriors will be set on the target index.

- If chooseTargetFromIndex is true, then the target will be chosen
from the geometry in the index itself, otherwise it will be chosen
randomly according to the parameters below:

- If targetRadiusFraction > 0, the target radius will be approximately
the given fraction of the index radius; if targetRadiusFraction < 0,
it will be chosen randomly up to corresponding positive fraction.

- If centerSeparationFraction > 0, then the centers of index and target
bounding caps will be separated by the given fraction of the index
radius; if centerSeparationFraction < 0, they will be separated by up
to the corresponding positive fraction.

- The randomSeed is used to initialize an internal seed, which is
incremented at the start of each call to generateEdgeQueryWithTargets.
This is for debugging purposes.
package s2
import (
	"fmt"
	"math/rand"
	"reflect"
	"testing"
	"github.com/golang/geo/s1"
)
func TestEdgeQueryMaxDistance(t *testing.T) {
	index := makeShapeIndex("0:0 | 1:0 | 2:0 | 3:0 # #")
	query := NewFurthestEdgeQuery(index, nil)
	target := NewMaxDistanceToPointTarget(parsePoint("4:0"))
	results := query.findEdges(target, NewFurthestEdgeQueryOptions().MaxResults(1).common)
	if len(results) != 1 {
		t.Errorf("len(results) = %v, want 1: %+v", len(results), results)
		return
	}
	if results[0].shapeID != 0 {
		t.Errorf("shapeID should be 0 got %v", results[0].shapeID)
	}
	if results[0].edgeID != 0 {
		t.Errorf("edgeID should be 0, got %v", results[0].edgeID)
	}
	if got, want := results[0].Distance().Angle().Degrees(), 4.0; !float64Near(got, want, 1e-13) {
		t.Errorf("results[0].Distance = %v, want ~%v", got, want)
	}
}
func TestEdgeQuerySortAndUnique(t *testing.T) {
	tests := []struct {
		have []EdgeQueryResult
		want []EdgeQueryResult
	}{
		{
			have: []EdgeQueryResult{
				{distance: minDistance(0.0790858), shapeID: 0, edgeID: 0},
			},
			want: []EdgeQueryResult{
				{distance: minDistance(0.0790858), shapeID: 0, edgeID: 0},
			},
		},
		{
			have: []EdgeQueryResult{
				{distance: minDistance(0.0639643), shapeID: 0, edgeID: 4},
				{distance: minDistance(0.0639643), shapeID: 0, edgeID: 2},
			},
			want: []EdgeQueryResult{
				{distance: minDistance(0.0639643), shapeID: 0, edgeID: 2},
				{distance: minDistance(0.0639643), shapeID: 0, edgeID: 4},
			},
		},
		{
			have: []EdgeQueryResult{
				{distance: minDistance(0.0639643), shapeID: 0, edgeID: 1},
				{distance: minDistance(0.0508695), shapeID: 0, edgeID: 11},
				{distance: minDistance(0.1181251), shapeID: 0, edgeID: 43},
			},
			want: []EdgeQueryResult{
				{distance: minDistance(0.0508695), shapeID: 0, edgeID: 11},
				{distance: minDistance(0.0639643), shapeID: 0, edgeID: 1},
				{distance: minDistance(0.1181251), shapeID: 0, edgeID: 43},
			},
		},
		{
			have: []EdgeQueryResult{
				{distance: minDistance(0.0639643), shapeID: 4, edgeID: 2},
				{distance: minDistance(0.0639643), shapeID: 3, edgeID: 8},
				{distance: minDistance(0.0508695), shapeID: 0, edgeID: 11},
				{distance: minDistance(0.1181251), shapeID: 0, edgeID: 43},
			},
			want: []EdgeQueryResult{
				{distance: minDistance(0.0508695), shapeID: 0, edgeID: 11},
				{distance: minDistance(0.0639643), shapeID: 3, edgeID: 8},
				{distance: minDistance(0.0639643), shapeID: 4, edgeID: 2},
				{distance: minDistance(0.1181251), shapeID: 0, edgeID: 43},
			},
		},
		{
			have: []EdgeQueryResult{
				{distance: minDistance(0.0790858), shapeID: 0, edgeID: 0},
				{distance: minDistance(0.0639643), shapeID: 0, edgeID: 1},
				{distance: minDistance(0.0639643), shapeID: 0, edgeID: 2},
				{distance: minDistance(0.0677918), shapeID: 0, edgeID: 3},
				{distance: minDistance(0.0542300), shapeID: 0, edgeID: 4},
				{distance: minDistance(0.0455950), shapeID: 0, edgeID: 5},
				{distance: minDistance(0.0423160), shapeID: 0, edgeID: 6},
				{distance: minDistance(0.0320540), shapeID: 0, edgeID: 7},
				{distance: minDistance(0.0320540), shapeID: 0, edgeID: 8},
				{distance: minDistance(0.0404029), shapeID: 0, edgeID: 9},
				{distance: minDistance(0.0405702), shapeID: 0, edgeID: 10},
				{distance: minDistance(0.0508695), shapeID: 0, edgeID: 11},
				{distance: minDistance(0.0627421), shapeID: 0, edgeID: 12},
				{distance: minDistance(0.0539154), shapeID: 0, edgeID: 13},
				{distance: minDistance(0.1181251), shapeID: 0, edgeID: 43},
				{distance: minDistance(0.1061612), shapeID: 0, edgeID: 44},
				{distance: minDistance(0.1061612), shapeID: 0, edgeID: 45},
				{distance: minDistance(0.0957947), shapeID: 0, edgeID: 46},
			},
			want: []EdgeQueryResult{
				{distance: minDistance(0.0320540), shapeID: 0, edgeID: 7},
				{distance: minDistance(0.0320540), shapeID: 0, edgeID: 8},
				{distance: minDistance(0.0404029), shapeID: 0, edgeID: 9},
				{distance: minDistance(0.0405702), shapeID: 0, edgeID: 10},
				{distance: minDistance(0.0423160), shapeID: 0, edgeID: 6},
				{distance: minDistance(0.0455950), shapeID: 0, edgeID: 5},
				{distance: minDistance(0.0508695), shapeID: 0, edgeID: 11},
				{distance: minDistance(0.0539154), shapeID: 0, edgeID: 13},
				{distance: minDistance(0.0542300), shapeID: 0, edgeID: 4},
				{distance: minDistance(0.0627421), shapeID: 0, edgeID: 12},
				{distance: minDistance(0.0639643), shapeID: 0, edgeID: 1},
				{distance: minDistance(0.0639643), shapeID: 0, edgeID: 2},
				{distance: minDistance(0.0677918), shapeID: 0, edgeID: 3},
				{distance: minDistance(0.0790858), shapeID: 0, edgeID: 0},
				{distance: minDistance(0.0957947), shapeID: 0, edgeID: 46},
				{distance: minDistance(0.1061612), shapeID: 0, edgeID: 44},
				{distance: minDistance(0.1061612), shapeID: 0, edgeID: 45},
				{distance: minDistance(0.1181251), shapeID: 0, edgeID: 43},
			},
		},
	}
	for _, test := range tests {
		have := append([]EdgeQueryResult{}, test.have...)
		got := sortAndUniqueResults(have)
		if !reflect.DeepEqual(got, test.want) {
			t.Errorf("sortAndUniqueResults(%v) =\n %v, \nwant %v", test.have, got, test.want)
		}
	}
}
type shapeIndexGeneratorFunc func(c Cap, numEdges int, index *ShapeIndex)
func loopShapeIndexGenerator(c Cap, numEdges int, index *ShapeIndex) {
	index.Add(RegularLoop(c.Center(), c.Radius(), numEdges))
}
func fractalLoopShapeIndexGenerator(c Cap, numEdges int, index *ShapeIndex) {
	fractal := newFractal()
	fractal.setLevelForApproxMaxEdges(numEdges)
	index.Add(fractal.makeLoop(randomFrameAtPoint(c.Center()), c.Radius()))
}
func pointCloudShapeIndexGenerator(c Cap, numPoints int, index *ShapeIndex) {
	var points PointVector
	for i := 0; i < numPoints; i++ {
		points = append(points, samplePointFromCap(c))
	}
	index.Add(&points)
}
type queryTargetType int
const (
	queryTypePoint queryTargetType = iota
	queryTypeEdge
	queryTypeCell
	queryTypeIndex
)
const edgeQueryTestNumIndexes = 50
const edgeQueryTestNumEdges = 100
const edgeQueryTestNumQueries = 200
var testCapRadius = kmToAngle(10)
func benchmarkEdgeQueryFindClosest(b *testing.B, bmOpts *edgeQueryBenchmarkOptions) {
	const numIndexSamples = 8
	b.StopTimer()
	index := NewShapeIndex()
	opts := NewClosestEdgeQueryOptions().MaxResults(1).IncludeInteriors(bmOpts.includeInteriors)
	radius := kmToAngle(bmOpts.radiusKm.Radians())
	if bmOpts.maxDistanceFraction > 0 {
		opts.DistanceLimit(s1.ChordAngleFromAngle(s1.Angle(bmOpts.maxDistanceFraction) * radius))
	}
	if bmOpts.maxErrorFraction > 0 {
		opts.MaxError(s1.ChordAngleFromAngle(s1.Angle(bmOpts.maxErrorFraction) * radius))
	}
	opts.UseBruteForce(*benchmarkBruteForce)
	query := NewClosestEdgeQuery(index, opts)
	delta := 0  
	var targets []distanceTarget
	bmOpts.numIndexEdges = 3
	for n := 1; n <= 7; n++ {
		bmOpts.numIndexEdges *= 4
		b.Run(fmt.Sprintf("%d", bmOpts.numIndexEdges),
			func(b *testing.B) {
				iTarget := 0
				for i := 0; i < b.N; i++ {
					delta -= numIndexSamples
					if delta < 0 {
						b.StopTimer()
						delta += i
						targets, _ = generateEdgeQueryWithTargets(bmOpts, query, index)
						b.StartTimer()
					}
					query.FindEdges(targets[iTarget])
					iTarget++
					if iTarget == len(targets) {
						iTarget = 0
					}
				}
			})
	}
}
type edgeQueryBenchmarkOptions struct {
	iters                    int
	fact                     shapeIndexGeneratorFunc
	numIndexEdges            int
	includeInteriors         bool
	targetType               queryTargetType
	numTargetEdges           int
	chooseTargetFromIndex    bool
	radiusKm                 s1.Angle
	maxDistanceFraction      float64
	maxErrorFraction         float64
	targetRadiusFraction     float64
	centerSeparationFraction float64
	randomSeed               int64
}