edge_query_test.go

Documentation: github.com/golang/geo/s2

     1  // Copyright 2019 Google Inc. All rights reserved.
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  package s2
    16  
    17  import (
    18  	"flag"
    19  
    20  	"fmt"
    21  	"math/rand"
    22  	"reflect"
    23  	"testing"
    24  
    25  	"github.com/golang/geo/s1"
    26  )
    27  
    28  var (
    29  	// The edge query benchmarks scale up the number of edges each time in the
    30  	// benchmarking loop. This flag allows for chaning up or down the number
    31  	// of scalings that occur in benchmarking.  The default value gets to
    32  	// ~50k edges in the test, and completes in a reasonable amount of time.
    33  	// Sometimes though there is a need to push the limits on the benchmarks
    34  	// without wanting to do a complete redeploy to change the counter, and
    35  	// this flag allows that to happen.
    36  	//
    37  	// To set in testing add "--benchmark_edge_query_range=5" to your test command.
    38  	benchmarkEdgeQueryRange = flag.Int("benchmark_edge_query_range", 7,
    39  		"Set the upper limit on times to scale up the edge query "+
    40  			"edge counts in benchmark runs.")
    41  )
    42  
    43  // Note that most of the actual testing is done in s2edge_query_{closest|furthest}_test.
    44  
    45  func TestEdgeQueryMaxDistance(t *testing.T) {
    46  	index := makeShapeIndex("0:0 | 1:0 | 2:0 | 3:0 # #")
    47  	query := NewFurthestEdgeQuery(index, nil)
    48  	target := NewMaxDistanceToPointTarget(parsePoint("4:0"))
    49  	results := query.findEdges(target, NewFurthestEdgeQueryOptions().MaxResults(1).common)
    50  
    51  	if len(results) != 1 {
    52  		t.Errorf("len(results) = %v, want 1: %+v", len(results), results)
    53  		return
    54  	}
    55  
    56  	if results[0].shapeID != 0 {
    57  		t.Errorf("shapeID should be 0 got %v", results[0].shapeID)
    58  
    59  	}
    60  
    61  	if results[0].edgeID != 0 {
    62  		t.Errorf("edgeID should be 0, got %v", results[0].edgeID)
    63  
    64  	}
    65  
    66  	if got, want := results[0].Distance().Angle().Degrees(), 4.0; !float64Near(got, want, 1e-13) {
    67  		t.Errorf("results[0].Distance = %v, want ~%v", got, want)
    68  	}
    69  }
    70  
    71  func TestEdgeQuerySortAndUnique(t *testing.T) {
    72  	tests := []struct {
    73  		have []EdgeQueryResult
    74  		want []EdgeQueryResult
    75  	}{
    76  		{
    77  			// one result gets doesn't change
    78  			have: []EdgeQueryResult{
    79  				{distance: minDistance(0.0790858), shapeID: 0, edgeID: 0},
    80  			},
    81  			want: []EdgeQueryResult{
    82  				{distance: minDistance(0.0790858), shapeID: 0, edgeID: 0},
    83  			},
    84  		},
    85  		{
    86  			// tied result in same shape should be ordered by edge id.
    87  			have: []EdgeQueryResult{
    88  				{distance: minDistance(0.0639643), shapeID: 0, edgeID: 4},
    89  				{distance: minDistance(0.0639643), shapeID: 0, edgeID: 2},
    90  			},
    91  			want: []EdgeQueryResult{
    92  				{distance: minDistance(0.0639643), shapeID: 0, edgeID: 2},
    93  				{distance: minDistance(0.0639643), shapeID: 0, edgeID: 4},
    94  			},
    95  		},
    96  		{
    97  			// more than one result in same shape.
    98  			have: []EdgeQueryResult{
    99  				{distance: minDistance(0.0639643), shapeID: 0, edgeID: 1},
   100  				{distance: minDistance(0.0508695), shapeID: 0, edgeID: 11},
   101  				{distance: minDistance(0.1181251), shapeID: 0, edgeID: 43},
   102  			},
   103  			want: []EdgeQueryResult{
   104  				{distance: minDistance(0.0508695), shapeID: 0, edgeID: 11},
   105  				{distance: minDistance(0.0639643), shapeID: 0, edgeID: 1},
   106  				{distance: minDistance(0.1181251), shapeID: 0, edgeID: 43},
   107  			},
   108  		},
   109  		{
   110  			// more than one shape has the equal distance edge,
   111  			// order should be by shape by edge.
   112  			have: []EdgeQueryResult{
   113  				{distance: minDistance(0.0639643), shapeID: 4, edgeID: 2},
   114  				{distance: minDistance(0.0639643), shapeID: 3, edgeID: 8},
   115  				{distance: minDistance(0.0508695), shapeID: 0, edgeID: 11},
   116  				{distance: minDistance(0.1181251), shapeID: 0, edgeID: 43},
   117  			},
   118  			want: []EdgeQueryResult{
   119  				{distance: minDistance(0.0508695), shapeID: 0, edgeID: 11},
   120  				{distance: minDistance(0.0639643), shapeID: 3, edgeID: 8},
   121  				{distance: minDistance(0.0639643), shapeID: 4, edgeID: 2},
   122  				{distance: minDistance(0.1181251), shapeID: 0, edgeID: 43},
   123  			},
   124  		},
   125  		{
   126  			// larger set of results.
   127  			have: []EdgeQueryResult{
   128  				{distance: minDistance(0.0790858), shapeID: 0, edgeID: 0},
   129  				{distance: minDistance(0.0639643), shapeID: 0, edgeID: 1},
   130  				{distance: minDistance(0.0639643), shapeID: 0, edgeID: 2},
   131  				{distance: minDistance(0.0677918), shapeID: 0, edgeID: 3},
   132  				{distance: minDistance(0.0542300), shapeID: 0, edgeID: 4},
   133  				{distance: minDistance(0.0455950), shapeID: 0, edgeID: 5},
   134  				{distance: minDistance(0.0423160), shapeID: 0, edgeID: 6},
   135  				{distance: minDistance(0.0320540), shapeID: 0, edgeID: 7},
   136  				{distance: minDistance(0.0320540), shapeID: 0, edgeID: 8},
   137  				{distance: minDistance(0.0404029), shapeID: 0, edgeID: 9},
   138  				{distance: minDistance(0.0405702), shapeID: 0, edgeID: 10},
   139  				{distance: minDistance(0.0508695), shapeID: 0, edgeID: 11},
   140  				{distance: minDistance(0.0627421), shapeID: 0, edgeID: 12},
   141  				{distance: minDistance(0.0539154), shapeID: 0, edgeID: 13},
   142  				{distance: minDistance(0.1181251), shapeID: 0, edgeID: 43},
   143  				{distance: minDistance(0.1061612), shapeID: 0, edgeID: 44},
   144  				{distance: minDistance(0.1061612), shapeID: 0, edgeID: 45},
   145  				{distance: minDistance(0.0957947), shapeID: 0, edgeID: 46},
   146  			},
   147  			want: []EdgeQueryResult{
   148  				{distance: minDistance(0.0320540), shapeID: 0, edgeID: 7},
   149  				{distance: minDistance(0.0320540), shapeID: 0, edgeID: 8},
   150  				{distance: minDistance(0.0404029), shapeID: 0, edgeID: 9},
   151  				{distance: minDistance(0.0405702), shapeID: 0, edgeID: 10},
   152  				{distance: minDistance(0.0423160), shapeID: 0, edgeID: 6},
   153  				{distance: minDistance(0.0455950), shapeID: 0, edgeID: 5},
   154  				{distance: minDistance(0.0508695), shapeID: 0, edgeID: 11},
   155  				{distance: minDistance(0.0539154), shapeID: 0, edgeID: 13},
   156  				{distance: minDistance(0.0542300), shapeID: 0, edgeID: 4},
   157  				{distance: minDistance(0.0627421), shapeID: 0, edgeID: 12},
   158  				{distance: minDistance(0.0639643), shapeID: 0, edgeID: 1},
   159  				{distance: minDistance(0.0639643), shapeID: 0, edgeID: 2},
   160  				{distance: minDistance(0.0677918), shapeID: 0, edgeID: 3},
   161  				{distance: minDistance(0.0790858), shapeID: 0, edgeID: 0},
   162  				{distance: minDistance(0.0957947), shapeID: 0, edgeID: 46},
   163  				{distance: minDistance(0.1061612), shapeID: 0, edgeID: 44},
   164  				{distance: minDistance(0.1061612), shapeID: 0, edgeID: 45},
   165  				{distance: minDistance(0.1181251), shapeID: 0, edgeID: 43},
   166  			},
   167  		},
   168  	}
   169  
   170  	for _, test := range tests {
   171  		have := append([]EdgeQueryResult{}, test.have...)
   172  		got := sortAndUniqueResults(have)
   173  		if !reflect.DeepEqual(got, test.want) {
   174  			t.Errorf("sortAndUniqueResults(%v) =\n %v, \nwant %v", test.have, got, test.want)
   175  		}
   176  	}
   177  }
   178  
   179  // For various tests and benchmarks on the edge query code, there are a number of
   180  // ShapeIndex generators that can be used.
   181  type shapeIndexGeneratorFunc func(c Cap, numEdges int, index *ShapeIndex)
   182  
   183  // loopShapeIndexGenerator generates a regular loop that approximately fills
   184  // the given Cap.
   185  //
   186  // Regular loops are nearly the worst case for distance calculations, since
   187  // many edges are nearly equidistant from any query point that is not
   188  // immediately adjacent to the loop.
   189  func loopShapeIndexGenerator(c Cap, numEdges int, index *ShapeIndex) {
   190  	index.Add(RegularLoop(c.Center(), c.Radius(), numEdges))
   191  }
   192  
   193  // fractalLoopShapeIndexGenerator generates a fractal loop that approximately
   194  // fills the given Cap.
   195  func fractalLoopShapeIndexGenerator(c Cap, numEdges int, index *ShapeIndex) {
   196  	fractal := newFractal()
   197  	fractal.setLevelForApproxMaxEdges(numEdges)
   198  	index.Add(fractal.makeLoop(randomFrameAtPoint(c.Center()), c.Radius()))
   199  }
   200  
   201  // pointCloudShapeIndexGenerator generates a cloud of points that approximately
   202  // fills the given Cap.
   203  func pointCloudShapeIndexGenerator(c Cap, numPoints int, index *ShapeIndex) {
   204  	var points PointVector
   205  	for i := 0; i < numPoints; i++ {
   206  		points = append(points, samplePointFromCap(c))
   207  	}
   208  	index.Add(&points)
   209  }
   210  
   211  type queryTargetType int
   212  
   213  const (
   214  	queryTypePoint queryTargetType = iota
   215  	queryTypeEdge
   216  	queryTypeCell
   217  	queryTypeIndex
   218  )
   219  
   220  const edgeQueryTestNumIndexes = 50
   221  const edgeQueryTestNumEdges = 100
   222  const edgeQueryTestNumQueries = 200
   223  
   224  // The approximate radius of Cap from which query edges are chosen.
   225  var testCapRadius = kmToAngle(10)
   226  
   227  /*
   228  // testEdgeQueryWithGenerator is used to perform high volume random testing on EdqeQuery
   229  // using a variety of index generation methods and varying sizes.
   230  //
   231  // The running time of this test is proportional to
   232  //    (numIndexes + numQueries) * numEdges.
   233  // Every query is checked using the brute force algorithm.
   234  func testEdgeQueryWithGenerator(t *testing.T,
   235  	newQueryFunc func(si *ShapeIndex, opts *EdgeQueryOptions) *EdgeQuery,
   236  	newOptsFunc func() *EdgeQueryOptions,
   237  	gen shapeIndexGeneratorFunc,
   238  	numIndexes, numEdges, numQueries int) {
   239  
   240  	// Build a set of ShapeIndexes containing the desired geometry.
   241  	var indexCaps []Cap
   242  	var indexes []*ShapeIndex
   243  	for i := 0; i < numIndexes; i++ {
   244  		rand.Seed(int64(i))
   245  		indexCaps = append(indexCaps, CapFromCenterAngle(randomPoint(), testCapRadius))
   246  		indexes = append(indexes, NewShapeIndex())
   247  		gen(indexCaps[i], numEdges, indexes[i])
   248  	}
   249  
   250  	for i := 0; i < numQueries; i++ {
   251  		rand.Seed(int64(i))
   252  		iIndex := randomUniformInt(numIndexes)
   253  		indexCap := indexCaps[iIndex]
   254  
   255  		// Choose query points from an area approximately 4x larger than the
   256  		// geometry being tested.
   257  		queryRadius := 2 * indexCap.Radius()
   258  		// Exercise the opposite-hemisphere code 1/5 of the time.
   259  		antipodal := 1.0
   260  		if oneIn(5) {
   261  			antipodal = -1
   262  		}
   263  		//queryCap := CapFromCenterAngle(indexCap.Center(), queryRadius)
   264  		queryCap := CapFromCenterAngle(Point{indexCap.Center().Mul(antipodal)}, queryRadius)
   265  
   266  		opts := newOptsFunc()
   267  
   268  		// Occasionally we don't set any limit on the number of result edges.
   269  		// (This may return all edges if we also don't set a distance limit.)
   270  		if oneIn(5) {
   271  			opts.MaxResults(1 + randomUniformInt(10))
   272  		}
   273  
   274  		// We set a distance limit 1/3 of the time.
   275  		if oneIn(3) {
   276  			opts.DistanceLimit(s1.ChordAngleFromAngle(s1.Angle(randomFloat64()) * queryRadius))
   277  		}
   278  		if oneIn(2) {
   279  			// Choose a maximum error whose logarithm is uniformly distributed over
   280  			// a reasonable range, except that it is sometimes zero.
   281  			opts.MaxError(s1.ChordAngleFromAngle(s1.Angle(math.Pow(1e-4, randomFloat64()) * queryRadius.Radians())))
   282  		}
   283  		opts.IncludeInteriors(oneIn(2))
   284  
   285  		query := newQueryFunc(indexes[iIndex], opts)
   286  
   287  		switch randomUniformInt(4) {
   288  		case 0:
   289  			// Find the edges furthest from a given point.
   290  			point := samplePointFromCap(queryCap)
   291  			target := NewMaxDistanceToPointTarget(point)
   292  			testFindEdges(target, query)
   293  		case 1:
   294  			// Find the edges furthest from a given edge.
   295  			a := samplePointFromCap(queryCap)
   296  			b := samplePointFromCap(
   297  				CapFromCenterAngle(a, s1.Angle(math.Pow(1e-4, randomFloat64()))*queryRadius))
   298  			target := NewMaxDistanceToEdgeTarget(Edge{a, b})
   299  			testFindEdges(target, query)
   300  
   301  		case 2:
   302  			// Find the edges furthest from a given cell.
   303  			minLevel := MaxDiagMetric.MinLevel(queryRadius.Radians())
   304  			level := minLevel + randomUniformInt(MaxLevel-minLevel+1)
   305  			a := samplePointFromCap(queryCap)
   306  			cell := CellFromCellID(cellIDFromPoint(a).Parent(level))
   307  			target := NewMaxDistanceToCellTarget(cell)
   308  			testFindEdges(target, query)
   309  
   310  		case 3:
   311  			// Use another one of the pre-built indexes as the target.
   312  			jIndex := randomUniformInt(numIndexes)
   313  			target := NewMaxDistanceToShapeIndexTarget(indexes[jIndex])
   314  			target.setIncludeInteriors(oneIn(2))
   315  			testFindEdges(target, query)
   316  		}
   317  	}
   318  }
   319  
   320  */
   321  
   322  // benchmarkEdgeQueryFindClosest calls FindEdges the given number of times on
   323  // a ShapeIndex with approximately numIndexEdges edges generated by the given
   324  // generator. The geometry is generated within a Cap of the radius given.
   325  //
   326  // Each query uses a target of the given targetType.
   327  //
   328  //   - If maxDistanceFraction > 0, then DistanceLimit is set to the given
   329  //     fraction of the index radius.
   330  //
   331  //   - If maxErrorFraction > 0, then MaxError is set to the given
   332  //     fraction of the index radius.
   333  //
   334  // TODO(roberts): If there is a need to benchmark Furthest as well, this will need
   335  // some changes to not use just the Closest variants of parts.
   336  // Furthest isn't doing anything different under the covers than Closest, so there
   337  // isn't really a huge need for benchmarking both.
   338  func benchmarkEdgeQueryFindClosest(b *testing.B, bmOpts *edgeQueryBenchmarkOptions) {
   339  	index := NewShapeIndex()
   340  	opts := NewClosestEdgeQueryOptions().MaxResults(1).IncludeInteriors(bmOpts.includeInteriors)
   341  
   342  	radius := kmToAngle(bmOpts.radiusKm.Radians())
   343  	if bmOpts.maxDistanceFraction > 0 {
   344  		opts.DistanceLimit(s1.ChordAngleFromAngle(s1.Angle(bmOpts.maxDistanceFraction) * radius))
   345  	}
   346  	if bmOpts.maxErrorFraction > 0 {
   347  		opts.MaxError(s1.ChordAngleFromAngle(s1.Angle(bmOpts.maxErrorFraction) * radius))
   348  	}
   349  
   350  	opts.UseBruteForce(*benchmarkBruteForce)
   351  	query := NewClosestEdgeQuery(index, opts)
   352  
   353  	var targets []distanceTarget
   354  
   355  	// To follow the sizing on the C++ tests to ease comparisons, the number of
   356  	// edges in the index range on 3 * 4^n (up to ~48k by default).
   357  	bmOpts.numIndexEdges = 3
   358  	for n := 1; n <= *benchmarkEdgeQueryRange; n++ {
   359  		bmOpts.numIndexEdges *= 4
   360  		b.Run(fmt.Sprintf("%d", bmOpts.numIndexEdges),
   361  			func(b *testing.B) {
   362  				// TODO(roberts): Return value 2 here is the slice of target
   363  				// ShapeIndexes. Incorporate it once ShapeIndexTargets
   364  				// are able to be used in tests.
   365  				targets, _ = generateEdgeQueryWithTargets(bmOpts, query, index)
   366  				for i := 0; i < b.N; i++ {
   367  					// TODO(roberts): In the reference C++ benchmark
   368  					// they use the tooling to split the benchmark
   369  					// run iterations up into kNumIndexSamples (8)
   370  					// times and pause to generate a new geometry
   371  					// and targets to do so.  If the current set
   372  					// of Go benchmark results are not sufficient, see
   373  					// about incorporating that same behavior using
   374  					// b.N to estimate when to pause and recreate.
   375  					query.FindEdges(targets[i%len(targets)])
   376  				}
   377  			})
   378  	}
   379  }
   380  
   381  // edgeQueryBenchmarkOptions holds the various parameters than can be adjusted by the
   382  // benchmarking runners.
   383  type edgeQueryBenchmarkOptions struct {
   384  	iters                    int
   385  	indexGenerator           shapeIndexGeneratorFunc
   386  	numIndexEdges            int
   387  	includeInteriors         bool
   388  	targetType               queryTargetType
   389  	numTargetEdges           int
   390  	chooseTargetFromIndex    bool
   391  	radiusKm                 s1.Angle
   392  	maxDistanceFraction      float64
   393  	maxErrorFraction         float64
   394  	targetRadiusFraction     float64
   395  	centerSeparationFraction float64
   396  	randomSeed               int64
   397  }
   398  
   399  // generateEdgeQueryWithTargets generates and adds geometry to a ShapeIndex for
   400  // use in an edge query.
   401  //
   402  // Approximately numIndexEdges will be generated by the requested generator and
   403  // inserted. The geometry is generated within a Cap of the radius specified
   404  // by radiusKm (the index radius). Parameters with fraction in their
   405  // names are expressed as a fraction of this radius.
   406  //
   407  // Also generates a set of target geometries for the query, based on the
   408  // targetType and the input parameters. If targetType is INDEX, then:
   409  //
   410  //	(i) the target will have approximately numTargetEdges edges.
   411  //	(ii) includeInteriors will be set on the target index.
   412  //
   413  //	- If chooseTargetFromIndex is true, then the target will be chosen
   414  //	  from the geometry in the index itself, otherwise it will be chosen
   415  //	  randomly according to the parameters below:
   416  //
   417  //	- If targetRadiusFraction > 0, the target radius will be approximately
   418  //	  the given fraction of the index radius; if targetRadiusFraction < 0,
   419  //	  it will be chosen randomly up to corresponding positive fraction.
   420  //
   421  //	- If centerSeparationFraction > 0, then the centers of index and target
   422  //	  bounding caps will be separated by the given fraction of the index
   423  //	  radius; if centerSeparationFraction < 0, they will be separated by up
   424  //	  to the corresponding positive fraction.
   425  //
   426  //	- The randomSeed is used to initialize an internal seed, which is
   427  //	  incremented at the start of each call to generateEdgeQueryWithTargets.
   428  //	  This is for debugging purposes.
   429  func generateEdgeQueryWithTargets(opts *edgeQueryBenchmarkOptions, query *EdgeQuery, queryIndex *ShapeIndex) (targets []distanceTarget, targetIndexes []*ShapeIndex) {
   430  
   431  	// To save time, we generate at most this many distinct targets per index.
   432  	const maxTargetsPerIndex = 100
   433  
   434  	// Set a specific seed to allow repeatability
   435  	rand.Seed(opts.randomSeed)
   436  	opts.randomSeed++
   437  	indexCap := CapFromCenterAngle(randomPoint(), opts.radiusKm)
   438  
   439  	query.Reset()
   440  	queryIndex.Reset()
   441  	opts.indexGenerator(indexCap, opts.numIndexEdges, queryIndex)
   442  
   443  	targets = make([]distanceTarget, 0)
   444  	targetIndexes = make([]*ShapeIndex, 0)
   445  
   446  	numTargets := maxTargetsPerIndex
   447  	if opts.targetType == queryTypeIndex {
   448  		// Limit the total number of target edges to reduce the benchmark running times.
   449  		numTargets = minInt(numTargets, 500000/opts.numTargetEdges)
   450  	}
   451  
   452  	for i := 0; i < numTargets; i++ {
   453  		targetDist := fractionToRadius(opts.centerSeparationFraction, opts.radiusKm.Radians())
   454  		targetCap := CapFromCenterAngle(
   455  			sampleBoundaryFromCap(CapFromCenterAngle(indexCap.Center(), targetDist)),
   456  			fractionToRadius(opts.targetRadiusFraction, opts.radiusKm.Radians()))
   457  
   458  		switch opts.targetType {
   459  		case queryTypePoint:
   460  			var pt Point
   461  			if opts.chooseTargetFromIndex {
   462  				pt = sampleEdgeFromIndex(queryIndex).V0
   463  			} else {
   464  				pt = targetCap.Center()
   465  			}
   466  			targets = append(targets, NewMinDistanceToPointTarget(pt))
   467  
   468  		case queryTypeEdge:
   469  			var edge Edge
   470  			if opts.chooseTargetFromIndex {
   471  				edge = sampleEdgeFromIndex(queryIndex)
   472  			} else {
   473  				edge.V0 = sampleBoundaryFromCap(targetCap)
   474  				edge.V1 = sampleBoundaryFromCap(targetCap)
   475  			}
   476  			targets = append(targets, NewMinDistanceToEdgeTarget(edge))
   477  		case queryTypeCell:
   478  			var cellID CellID
   479  			if opts.chooseTargetFromIndex {
   480  				cellID = sampleCellFromIndex(queryIndex)
   481  			} else {
   482  				cellID = cellIDFromPoint(targetCap.Center()).Parent(
   483  					MaxDiagMetric.ClosestLevel(targetCap.Radius().Radians()))
   484  			}
   485  			targets = append(targets, NewMinDistanceToCellTarget(CellFromCellID(cellID)))
   486  		case queryTypeIndex:
   487  			targetIndex := NewShapeIndex()
   488  			if opts.chooseTargetFromIndex {
   489  				var shape edgeVectorShape
   490  				for i := 0; i < opts.numTargetEdges; i++ {
   491  					edge := sampleEdgeFromIndex(queryIndex)
   492  					shape.Add(edge.V0, edge.V1)
   493  				}
   494  				targetIndex.Add(&shape)
   495  			} else {
   496  				opts.indexGenerator(targetCap, opts.numTargetEdges, targetIndex)
   497  			}
   498  			target := NewMinDistanceToShapeIndexTarget(targetIndex)
   499  			target.setIncludeInteriors(opts.includeInteriors)
   500  			targets = append(targets, target)
   501  			targetIndexes = append(targetIndexes, targetIndex)
   502  		default:
   503  			panic(fmt.Sprintf("unknown query target type %v", opts.targetType))
   504  		}
   505  	}
   506  
   507  	return targets, targetIndexes
   508  }
   509  
   510  func sampleBoundaryFromCap(c Cap) Point {
   511  	return InterpolateAtDistance(c.Radius(), c.Center(), randomPoint())
   512  }
   513  
   514  func sampleEdgeFromIndex(index *ShapeIndex) Edge {
   515  	e := randomUniformInt(index.NumEdges())
   516  
   517  	for _, shape := range index.shapes {
   518  		if e < shape.NumEdges() {
   519  			return shape.Edge(e)
   520  		}
   521  		e -= shape.NumEdges()
   522  	}
   523  	// This should only happen if the index has no edges at all.
   524  	panic("index with no edges")
   525  }
   526  
   527  func sampleCellFromIndex(index *ShapeIndex) CellID {
   528  	iter := index.Iterator()
   529  	for i := randomUniformInt(len(index.cells)); i >= 0; i-- {
   530  		iter.Next()
   531  		continue
   532  	}
   533  	return iter.CellID()
   534  }
   535  
   536  func fractionToRadius(fraction, radiusKm float64) s1.Angle {
   537  	if fraction < 0 {
   538  		fraction = -randomFloat64() * fraction
   539  	}
   540  	return s1.Angle(fraction) * kmToAngle(radiusKm)
   541  }
   542
View as plain text