Source file src/github.com/golang/geo/s2/shapeindex_test.go

Documentation: github.com/golang/geo/s2

     1  // Copyright 2016 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  	"testing"
    19  
    20  	"github.com/golang/geo/r3"
    21  	"github.com/golang/geo/s1"
    22  )
    23  
    24  func TestShapeIndexBasics(t *testing.T) {
    25  	index := NewShapeIndex()
    26  	s := &edgeVectorShape{}
    27  
    28  	if index.Len() != 0 {
    29  		t.Errorf("initial index should be empty after creation")
    30  	}
    31  	index.Add(s)
    32  
    33  	if index.Len() == 0 {
    34  		t.Errorf("index should not be empty after adding shape")
    35  	}
    36  
    37  	index.Reset()
    38  	if index.Len() != 0 {
    39  		t.Errorf("index should be empty after reset, got %v %+v", index.Len(), index)
    40  	}
    41  }
    42  
    43  func TestShapeEdgeComparisons(t *testing.T) {
    44  	tests := []struct {
    45  		a, b Edge
    46  		want int
    47  	}{
    48  		{
    49  			// a.V0 < b.V0
    50  			a:    Edge{PointFromCoords(-1, 0, 0), PointFromCoords(0, 0, 0)},
    51  			b:    Edge{PointFromCoords(0, 0, 0), PointFromCoords(0, 0, 0)},
    52  			want: -1,
    53  		},
    54  		{
    55  			// a.V0 = b.V0
    56  			a:    Edge{PointFromCoords(0, 2, 0), PointFromCoords(0, 0, 5)},
    57  			b:    Edge{PointFromCoords(0, 2, 0), PointFromCoords(0, 0, 5)},
    58  			want: 0,
    59  		},
    60  		{
    61  			// a.V0 > b.V0
    62  			a:    Edge{PointFromCoords(1, 0, 0), PointFromCoords(-6, 7, 8)},
    63  			b:    Edge{PointFromCoords(0, 0, 0), PointFromCoords(1, 3, 5)},
    64  			want: 1,
    65  		},
    66  		{
    67  			// a.V0 = b.V0 && a.V1 < b.V1
    68  			a:    Edge{PointFromCoords(5, -2, -0.4), PointFromCoords(-1, 0, 0)},
    69  			b:    Edge{PointFromCoords(5, -2, -0.4), PointFromCoords(0, -1, -1)},
    70  			want: -1,
    71  		},
    72  		{
    73  			// a.V0 = b.V0 && a.V1 = b.V1
    74  			a:    Edge{PointFromCoords(9, 8, 7), PointFromCoords(12, 3, -4)},
    75  			b:    Edge{PointFromCoords(9, 8, 7), PointFromCoords(12, 3, -4)},
    76  			want: 0,
    77  		},
    78  		{
    79  			// a.V0 = b.V0 && a.V1 > b.V1
    80  			a:    Edge{PointFromCoords(-11, 7.2, -4.6), PointFromCoords(0, 1, 0)},
    81  			b:    Edge{PointFromCoords(-11, 7.2, -4.6), PointFromCoords(0, 0, 0.9)},
    82  			want: 1,
    83  		},
    84  	}
    85  
    86  	for _, test := range tests {
    87  		if got := test.a.Cmp(test.b); got != test.want {
    88  			t.Errorf("%v.Cmp(%v) = %v, want %v", test.a, test.b, got, test.want)
    89  		}
    90  	}
    91  }
    92  
    93  func TestShapeIndexCellBasics(t *testing.T) {
    94  	s := &ShapeIndexCell{}
    95  
    96  	if len(s.shapes) != 0 {
    97  		t.Errorf("len(s.shapes) = %v, want %d", len(s.shapes), 0)
    98  	}
    99  
   100  	// create some clipped shapes to add.
   101  	c1 := &clippedShape{}
   102  	s.add(c1)
   103  
   104  	c2 := newClippedShape(7, 1)
   105  	s.add(c2)
   106  
   107  	c3 := &clippedShape{}
   108  	s.add(c3)
   109  
   110  	// look up the element at a given index
   111  	if got := s.shapes[1]; got != c2 {
   112  		t.Errorf("%v.shapes[%d] = %v, want %v", s, 1, got, c2)
   113  	}
   114  
   115  	// look for the clipped shape that is part of the given shape.
   116  	if got := s.findByShapeID(7); got != c2 {
   117  		t.Errorf("%v.findByShapeID(%v) = %v, want %v", s, 7, got, c2)
   118  	}
   119  }
   120  
   121  // validateEdge determines whether or not the edge defined by points A and B should be
   122  // present in that CellID and verify that this matches hasEdge.
   123  func validateEdge(t *testing.T, a, b Point, ci CellID, hasEdge bool) {
   124  	// Expand or shrink the padding slightly to account for errors in the
   125  	// function we use to test for intersection (IntersectsRect).
   126  	padding := cellPadding
   127  	sign := 1.0
   128  	if !hasEdge {
   129  		sign = -1
   130  	}
   131  	padding += sign * intersectsRectErrorUVDist
   132  	bound := ci.boundUV().ExpandedByMargin(padding)
   133  	aUV, bUV, ok := ClipToPaddedFace(a, b, ci.Face(), padding)
   134  
   135  	if got := ok && edgeIntersectsRect(aUV, bUV, bound); got != hasEdge {
   136  		t.Errorf("edgeIntersectsRect(%v, %v, %v) = %v && clip = %v, want %v", aUV, bUV, bound, edgeIntersectsRect(aUV, bUV, bound), ok, hasEdge)
   137  	}
   138  }
   139  
   140  // validateInterior tests if the given Shape contains the center of the given CellID,
   141  // and that this matches the expected value of indexContainsCenter.
   142  func validateInterior(t *testing.T, shape Shape, ci CellID, indexContainsCenter bool) {
   143  	if shape == nil {
   144  		if indexContainsCenter {
   145  			t.Errorf("%v was nil or does not have an interior, but should have", shape)
   146  		}
   147  		return
   148  	}
   149  	if got := containsBruteForce(shape, ci.Point()); got != indexContainsCenter {
   150  		t.Errorf("validating interior of shape containsCenter = %v, want %v", got, indexContainsCenter)
   151  	}
   152  }
   153  
   154  // quadraticValidate verifies that that every cell of the index contains the correct
   155  // edges, and that no cells are missing from the index.  The running time of this
   156  // function is quadratic in the number of edges.
   157  func quadraticValidate(t *testing.T, index *ShapeIndex) {
   158  	// Iterate through a sequence of nonoverlapping cell ids that cover the
   159  	// sphere and include as a subset all the cell ids used in the index.  For
   160  	// each cell id, verify that the expected set of edges is present.
   161  	// "minCellID" is the first CellID that has not been validated yet.
   162  	minCellID := CellIDFromFace(0).ChildBeginAtLevel(MaxLevel)
   163  	for it := index.Iterator(); ; it.Next() {
   164  		// Generate a list of CellIDs ("skipped cells") that cover the gap
   165  		// between the last cell we validated and the next cell in the index.
   166  		var skipped CellUnion
   167  		if !it.Done() {
   168  			cellID := it.CellID()
   169  			if cellID < minCellID {
   170  				t.Errorf("cell ID below min, got %v, want %v", cellID, minCellID)
   171  			}
   172  			skipped = CellUnionFromRange(minCellID, cellID.RangeMin())
   173  			minCellID = cellID.RangeMax().Next()
   174  		} else {
   175  			// Validate the empty cells beyond the last cell in the index.
   176  			skipped = CellUnionFromRange(minCellID,
   177  				CellIDFromFace(5).ChildEndAtLevel(MaxLevel))
   178  		}
   179  
   180  		// Iterate through all the shapes, simultaneously validating the current
   181  		// index cell and all the skipped cells.
   182  		shortEdges := 0 // number of edges counted toward subdivision
   183  		for id, shape := range index.shapes {
   184  			for j := 0; j < len(skipped); j++ {
   185  				validateInterior(t, shape, skipped[j], false)
   186  			}
   187  
   188  			// First check that containsCenter() is set correctly.
   189  			var clipped *clippedShape
   190  			if !it.Done() {
   191  				clipped = it.IndexCell().findByShapeID(id)
   192  				containsCenter := clipped != nil && clipped.containsCenter
   193  				validateInterior(t, shape, it.CellID(), containsCenter)
   194  			}
   195  			// If this shape has been removed, it should not be present at all.
   196  			if shape == nil {
   197  				if clipped != nil {
   198  					t.Errorf("clipped should be nil when shape is nil")
   199  				}
   200  				continue
   201  			}
   202  
   203  			// Otherwise check that the appropriate edges are present.
   204  			for e := 0; e < shape.NumEdges(); e++ {
   205  				edge := shape.Edge(e)
   206  				for j := 0; j < len(skipped); j++ {
   207  					validateEdge(t, edge.V0, edge.V1, skipped[j], false)
   208  				}
   209  				if !it.Done() {
   210  					hasEdge := clipped != nil && clipped.containsEdge(e)
   211  					validateEdge(t, edge.V0, edge.V1, it.CellID(), hasEdge)
   212  					if hasEdge && it.CellID().Level() < maxLevelForEdge(edge) {
   213  						shortEdges++
   214  					}
   215  				}
   216  			}
   217  		}
   218  
   219  		if shortEdges > index.maxEdgesPerCell {
   220  			t.Errorf("too many edges")
   221  		}
   222  
   223  		if it.Done() {
   224  			break
   225  		}
   226  	}
   227  }
   228  
   229  // copyIterator copies the internal state of the given iterator to a new iterator.
   230  func copyIterator(i *ShapeIndexIterator) *ShapeIndexIterator {
   231  	s := &ShapeIndexIterator{
   232  		index:    i.index,
   233  		position: i.position,
   234  		id:       i.id,
   235  		cell:     i.cell,
   236  	}
   237  	return s
   238  }
   239  
   240  func testIteratorMethods(t *testing.T, index *ShapeIndex) {
   241  	it := index.Iterator()
   242  	if it.Prev() {
   243  		t.Fatalf("new iterator should not be able to go backwards")
   244  	}
   245  
   246  	it.End()
   247  	if !it.Done() {
   248  		t.Errorf("iterator positioned at end should report as done")
   249  	}
   250  
   251  	var ids []CellID
   252  	// minCellID is the first CellID in a complete traversal.
   253  	minCellID := CellIDFromFace(0).ChildBeginAtLevel(MaxLevel)
   254  
   255  	for it.Begin(); !it.Done(); it.Next() {
   256  		// Get the next cell in the iterator.
   257  		ci := it.CellID()
   258  		skipped := CellUnionFromRange(minCellID, ci.RangeMin())
   259  
   260  		it2 := NewShapeIndexIterator(index, IteratorEnd)
   261  		for i := 0; i < len(skipped); i++ {
   262  			if it2.LocatePoint(skipped[i].Point()) {
   263  				t.Errorf("iterator should not have been able to find the cell %v which was not in the index", skipped[i].Point())
   264  			}
   265  
   266  			if got := it2.LocateCellID(skipped[i]); got != Disjoint {
   267  				t.Errorf("CellID location should be Disjoint for non-existent entry, got %v", got)
   268  			}
   269  			it2.Begin()
   270  			it2.seek(skipped[i])
   271  			if ci != it2.CellID() {
   272  				t.Errorf("seeking the current cell in the skipped list should match the current cellid. got %v, want %v", it2.CellID(), ci)
   273  			}
   274  		}
   275  
   276  		if len(ids) != 0 {
   277  			prevCell := ids[len(ids)-1]
   278  			// C++ overloads operator= to clone the iterator. We can't
   279  			// just assign directly since it2 will than change it when
   280  			// it should not.
   281  			it2 = copyIterator(it)
   282  			if !it2.Prev() {
   283  				t.Errorf("should have been able to go back because there are cells")
   284  			}
   285  			if prevCell != it2.CellID() {
   286  				t.Errorf("ShapeIndexIterator should be positioned at the beginning and not equal to last entry")
   287  			}
   288  
   289  			it2.Next()
   290  			if ci != it2.CellID() {
   291  				t.Errorf("advancing back one spot should give us the current cell")
   292  			}
   293  
   294  			it2.seek(prevCell)
   295  			if prevCell != it2.CellID() {
   296  				t.Errorf("seek from beginning for the first previous cell %v should not give us the current cell %v", prevCell, it.CellID())
   297  			}
   298  		}
   299  
   300  		it2.Begin()
   301  		if ci.Point() != it.Center() {
   302  			t.Errorf("point at center of current position should equal center of the crrent CellID. got %v, want %v", it.Center(), ci.Point())
   303  		}
   304  
   305  		if !it2.LocatePoint(it.Center()) {
   306  			t.Errorf("it.LocatePoint(it.Center()) should have been able to locate the point it is currently at")
   307  		}
   308  
   309  		if ci != it2.CellID() {
   310  			t.Errorf("CellID of the Point we just located should be equal. got %v, want %v", it2.CellID(), ci)
   311  		}
   312  
   313  		it2.Begin()
   314  		if got := it2.LocateCellID(ci); got != Indexed {
   315  			t.Errorf("it.LocateCellID(%v) = %v, want %v", ci, got, Indexed)
   316  		}
   317  
   318  		if ci != it2.CellID() {
   319  			t.Errorf("CellID of the CellID we just located should match. got %v, want %v", it2.CellID(), ci)
   320  		}
   321  
   322  		if !ci.isFace() {
   323  			it2.Begin()
   324  			if got := it2.LocateCellID(ci.immediateParent()); Subdivided != got {
   325  				t.Errorf("it2.LocateCellID(%v) = %v, want %v", ci.immediateParent(), got, Subdivided)
   326  			}
   327  
   328  			if it2.CellID() > ci {
   329  				t.Errorf("CellID of the immediate parent should be above the current cell, got %v, want %v", it2.CellID(), ci)
   330  			}
   331  
   332  			if it2.CellID() < ci.immediateParent().RangeMin() {
   333  				t.Errorf("CellID of the current position should fall below the RangeMin of the parent. got %v, want %v", it2.CellID(), ci.immediateParent().RangeMin())
   334  			}
   335  		}
   336  
   337  		if !ci.IsLeaf() {
   338  			for i := 0; i < 4; i++ {
   339  				it2.Begin()
   340  				if got, want := it2.LocateCellID(ci.Children()[i]), Indexed; got != want {
   341  					t.Errorf("it2.LocateCellID(%v.Children[%d]) = %v, want %v", ci, i, got, want)
   342  				}
   343  
   344  				if ci != it2.CellID() {
   345  					t.Errorf("it2.CellID() = %v, want %v", it2.CellID(), ci)
   346  				}
   347  			}
   348  		}
   349  		// Add this cellID to the set of cells to examine.
   350  		ids = append(ids, ci)
   351  		// Move the minimal CellID to the next CellID past our current position.
   352  		minCellID = ci.RangeMax().Next()
   353  	}
   354  }
   355  
   356  func TestShapeIndexNoEdges(t *testing.T) {
   357  	index := NewShapeIndex()
   358  	iter := index.Iterator()
   359  
   360  	if !iter.Done() {
   361  		t.Errorf("iterator for empty index should start at Done but did not")
   362  	}
   363  	testIteratorMethods(t, index)
   364  }
   365  
   366  func TestShapeIndexOneEdge(t *testing.T) {
   367  	index := NewShapeIndex()
   368  	e := edgeVectorShapeFromPoints(PointFromCoords(1, 0, 0), PointFromCoords(0, 1, 0))
   369  	if got := index.Add(e); got != 0 {
   370  		t.Errorf("the first element added to the index should have id 0, got %v", got)
   371  	}
   372  	quadraticValidate(t, index)
   373  	testIteratorMethods(t, index)
   374  }
   375  
   376  func TestShapeIndexManyIdenticalEdges(t *testing.T) {
   377  	const numEdges = 100
   378  	a := PointFromCoords(0.99, 0.99, 1)
   379  	b := PointFromCoords(-0.99, -0.99, 1)
   380  
   381  	index := NewShapeIndex()
   382  	for i := int32(0); i < numEdges; i++ {
   383  		if got := index.Add(edgeVectorShapeFromPoints(a, b)); got != i {
   384  			t.Errorf("element %d id = %v, want %v", i, got, i)
   385  		}
   386  	}
   387  	quadraticValidate(t, index)
   388  	testIteratorMethods(t, index)
   389  
   390  	// Since all edges span the diagonal of a face, no subdivision should
   391  	// have occurred (with the default index options).
   392  	for it := index.Iterator(); !it.Done(); it.Next() {
   393  		if it.CellID().Level() != 0 {
   394  			t.Errorf("it.CellID.Level() = %v, want nonzero", it.CellID().Level())
   395  		}
   396  	}
   397  }
   398  
   399  func TestShapeIndexDegenerateEdge(t *testing.T) {
   400  	// This test verifies that degenerate edges are supported.  The following
   401  	// point is a cube face vertex, and so it should be indexed in 3 cells.
   402  	a := PointFromCoords(1, 1, 1)
   403  	shape := edgeVectorShapeFromPoints(a, a)
   404  	index := NewShapeIndex()
   405  	index.Add(shape)
   406  	quadraticValidate(t, index)
   407  	// Check that exactly 3 index cells contain the degenerate edge.
   408  	count := 0
   409  	for it := index.Iterator(); !it.Done(); it.Next() {
   410  		if !it.CellID().IsLeaf() {
   411  			t.Errorf("the cell for this shape should be a leaf cell.")
   412  		}
   413  		if got := len(it.IndexCell().shapes); got != 1 {
   414  			t.Errorf("there should only be one shape stored in the index cell, got %d", got)
   415  		}
   416  		if got := len(it.IndexCell().shapes[0].edges); got != 1 {
   417  			t.Errorf("point should only have one edge, got %d", got)
   418  		}
   419  		count++
   420  	}
   421  	if count != 3 {
   422  		t.Errorf("expected 3 index cells, got %d", count)
   423  	}
   424  
   425  }
   426  
   427  func TestShapeIndexManyTinyEdges(t *testing.T) {
   428  	// This test adds many edges to a single leaf cell, to check that
   429  	// subdivision stops when no further subdivision is possible.
   430  
   431  	// Construct two points in the same leaf cell.
   432  	a := cellIDFromPoint(PointFromCoords(1, 0, 0)).Point()
   433  	b := Point{a.Add(r3.Vector{0, 1e-12, 0}).Normalize()}
   434  	shape := &edgeVectorShape{}
   435  	for i := 0; i < 100; i++ {
   436  		shape.Add(a, b)
   437  	}
   438  
   439  	index := NewShapeIndex()
   440  	index.Add(shape)
   441  	quadraticValidate(t, index)
   442  
   443  	// Check that there is exactly one index cell and that it is a leaf cell.
   444  	it := index.Iterator()
   445  	if it.Done() {
   446  		t.Errorf("ShapeIndexIterator should not be positioned at the end for %v", index)
   447  		return
   448  	}
   449  	if !(it.CellID().IsLeaf()) {
   450  		t.Errorf("there should be only one leaf cell in the index but it.CellID().IsLeaf() returned false")
   451  	}
   452  	it.Next()
   453  	if !(it.Done()) {
   454  		t.Errorf("ShapeIndexIterator should be positioned at the end now since there should have been only one element")
   455  	}
   456  }
   457  
   458  func TestShapeIndexShrinkToFitOptimization(t *testing.T) {
   459  	// This used to trigger a bug in the ShrinkToFit optimization. The loop
   460  	// below contains almost all of face 0 except for a small region in the
   461  	// 0/00000 subcell. That subcell is the only one that contains any edges.
   462  	// This caused the index to be built only in that subcell. However, all the
   463  	// other cells on that face should also have index entries, in order to
   464  	// indicate that they are contained by the loop.
   465  	loop := RegularLoop(PointFromCoords(1, 0.5, 0.5), s1.Degree*89, 100)
   466  	index := NewShapeIndex()
   467  	index.Add(loop)
   468  	quadraticValidate(t, index)
   469  }
   470  
   471  func TestShapeIndexMixedGeometry(t *testing.T) {
   472  	// This test used to trigger a bug where the presence of a shape with an
   473  	// interior could cause shapes that don't have an interior to suddenly
   474  	// acquire one. This would cause extra ShapeIndex cells to be created
   475  	// that are outside the bounds of the given geometry.
   476  	index := NewShapeIndex()
   477  	index.Add(makePolyline("0:0, 2:1, 0:2, 2:3, 0:4, 2:5, 0:6"))
   478  	index.Add(makePolyline("1:0, 3:1, 1:2, 3:3, 1:4, 3:5, 1:6"))
   479  	index.Add(makePolyline("2:0, 4:1, 2:2, 4:3, 2:4, 4:5, 2:6"))
   480  
   481  	loop := LoopFromCell(CellFromCellID(CellIDFromFace(0).ChildBeginAtLevel(MaxLevel)))
   482  	index.Add(loop)
   483  	it := index.Iterator()
   484  	// No geometry intersects face 1, so there should be no index cells there.
   485  	c := CellIDFromFace(1)
   486  	if got, want := it.LocateCellID(c), Disjoint; got != want {
   487  		t.Errorf("%v.LocateCellID(%v) = %v, want %v\n%v", it, c, got, want, index)
   488  	}
   489  }
   490  
   491  func TestShapeIndexLoopSpanningThreeFaces(t *testing.T) {
   492  	const numEdges = 100
   493  	// Construct two loops consisting of numEdges vertices each, centered
   494  	// around the cube vertex at the start of the Hilbert curve.
   495  	polygon := concentricLoopsPolygon(PointFromCoords(1, -1, -1), 2, numEdges)
   496  	index := NewShapeIndex()
   497  
   498  	for _, l := range polygon.loops {
   499  		index.Add(l)
   500  	}
   501  
   502  	quadraticValidate(t, index)
   503  	testIteratorMethods(t, index)
   504  }
   505  
   506  func TestShapeIndexNumEdgesUpTo(t *testing.T) {
   507  	index := makeShapeIndex("0:0 | 0:1 | 0:2 | 0:3 | 0:4 # 1:0, 1:1 | 1:2, 1:3 | 1:4, 1:5, 1:6 #")
   508  
   509  	if got, want := len(index.shapes), 4; got != want {
   510  		t.Errorf("len(index.shapes) = %v, want %v", got, want)
   511  	}
   512  
   513  	numEdgesTests := []struct {
   514  		shapeID int32
   515  		want    int
   516  	}{
   517  		{shapeID: 0, want: 5},
   518  		{shapeID: 1, want: 1},
   519  		{shapeID: 2, want: 1},
   520  		{shapeID: 3, want: 2},
   521  	}
   522  
   523  	for _, test := range numEdgesTests {
   524  		if got := index.Shape(test.shapeID).NumEdges(); got != test.want {
   525  			t.Errorf("index.Shape(%d).NumEdges() = %d, want %d", test.shapeID, got, test.want)
   526  		}
   527  	}
   528  
   529  	if got, want := index.NumEdges(), 9; got != want {
   530  		t.Errorf("index.NumEdges() = %d, want %d", got, want)
   531  	}
   532  
   533  	countTests := []struct {
   534  		limit int
   535  		want  int
   536  	}{
   537  		{limit: 1, want: 5},
   538  		{limit: 5, want: 5},
   539  		{limit: 6, want: 6},
   540  		{limit: 8, want: 9},
   541  	}
   542  	for _, test := range countTests {
   543  		if got := index.NumEdgesUpTo(test.limit); got != test.want {
   544  			t.Errorf("index.NumEdgesUpTo(%d) = %d, want %d", test.limit, got, test.want)
   545  		}
   546  	}
   547  }
   548  
   549  // TODO(roberts): Differences from C++:
   550  // TestShapeIndexSimpleUpdates(t *testing.T) {}
   551  // TestShapeIndexRandomUpdates(t *testing.T) {}
   552  // TestShapeIndexHasCrossing(t *testing.T) {}
   553  
   554  func BenchmarkShapeIndexIteratorLocatePoint(b *testing.B) {
   555  	index := NewShapeIndex()
   556  	for i := 0; i < 100; i++ {
   557  		var points []Point
   558  		for j := 0; j < 100; j++ {
   559  			points = append(points, randomPoint())
   560  		}
   561  		polyline := Polyline(points)
   562  		index.Add(&polyline)
   563  	}
   564  
   565  	it := index.Iterator()
   566  	b.ResetTimer()
   567  	for i := 0; i < b.N; i++ {
   568  		it.LocatePoint(randomPoint())
   569  	}
   570  }
   571  

View as plain text