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

Documentation: github.com/golang/geo/s2

     1  // Copyright 2015 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  	"fmt"
    19  	"math"
    20  	"testing"
    21  
    22  	"github.com/golang/geo/r1"
    23  	"github.com/golang/geo/r3"
    24  	"github.com/golang/geo/s1"
    25  )
    26  
    27  var (
    28  	// The northern hemisphere, defined using two pairs of antipodal points.
    29  	northHemi = LoopFromPoints(parsePoints("0:-180, 0:-90, 0:0, 0:90"))
    30  
    31  	// The northern hemisphere, defined using three points 120 degrees apart.
    32  	northHemi3 = LoopFromPoints(parsePoints("0:-180, 0:-60, 0:60"))
    33  
    34  	// The southern hemisphere, defined using two pairs of antipodal points.
    35  	southHemi = LoopFromPoints(parsePoints("0:90, 0:0, 0:-90, 0:-180"))
    36  
    37  	// The western hemisphere, defined using two pairs of antipodal points.
    38  	westHemi = LoopFromPoints(parsePoints("0:-180, -90:0, 0:0, 90:0"))
    39  
    40  	// The eastern hemisphere, defined using two pairs of antipodal points.
    41  	eastHemi = LoopFromPoints(parsePoints("90:0, 0:0, -90:0, 0:-180"))
    42  
    43  	// The "near" hemisphere, defined using two pairs of antipodal points.
    44  	nearHemi = LoopFromPoints(parsePoints("0:-90, -90:0, 0:90, 90:0"))
    45  
    46  	// The "far" hemisphere, defined using two pairs of antipodal points.
    47  	farHemi = LoopFromPoints(parsePoints("90:0, 0:90, -90:0, 0:-90"))
    48  
    49  	// A spiral stripe that slightly over-wraps the equator.
    50  	candyCane = LoopFromPoints(parsePoints("-20:150, -20:-70, 0:70, 10:-150, 10:70, -10:-70"))
    51  
    52  	// A small clockwise loop in the northern & eastern hemisperes.
    53  	smallNECW = LoopFromPoints(parsePoints("35:20, 45:20, 40:25"))
    54  
    55  	// Loop around the north pole at 80 degrees.
    56  	arctic80 = LoopFromPoints(parsePoints("80:-150, 80:-30, 80:90"))
    57  
    58  	// Loop around the south pole at 80 degrees.
    59  	antarctic80 = LoopFromPoints(parsePoints("-80:120, -80:0, -80:-120"))
    60  
    61  	// A completely degenerate triangle along the equator that RobustCCW()
    62  	// considers to be CCW.
    63  	lineTriangle = LoopFromPoints(parsePoints("0:1, 0:2, 0:3"))
    64  
    65  	// A nearly-degenerate CCW chevron near the equator with very long sides
    66  	// (about 80 degrees).  Its area is less than 1e-640, which is too small
    67  	// to represent in double precision.
    68  	skinnyChevron = LoopFromPoints(parsePoints("0:0, -1e-320:80, 0:1e-320, 1e-320:80"))
    69  
    70  	// A diamond-shaped loop around the point 0:180.
    71  	loopA = LoopFromPoints(parsePoints("0:178, -1:180, 0:-179, 1:-180"))
    72  
    73  	// Like loopA, but the vertices are at leaf cell centers.
    74  	snappedLoopA = LoopFromPoints([]Point{
    75  		cellIDFromPoint(parsePoint("0:178")).Point(),
    76  		cellIDFromPoint(parsePoint("-1:180")).Point(),
    77  		cellIDFromPoint(parsePoint("0:-179")).Point(),
    78  		cellIDFromPoint(parsePoint("1:-180")).Point(),
    79  	})
    80  
    81  	// A different diamond-shaped loop around the point 0:180.
    82  	loopB = LoopFromPoints(parsePoints("0:179, -1:180, 0:-178, 1:-180"))
    83  
    84  	// The intersection of A and B.
    85  	aIntersectB = LoopFromPoints(parsePoints("0:179, -1:180, 0:-179, 1:-180"))
    86  
    87  	// The union of A and B.
    88  	aUnionB = LoopFromPoints(parsePoints("0:178, -1:180, 0:-178, 1:-180"))
    89  
    90  	// A minus B (concave).
    91  	aMinusB = LoopFromPoints(parsePoints("0:178, -1:180, 0:179, 1:-180"))
    92  
    93  	// B minus A (concave).
    94  	bMinusA = LoopFromPoints(parsePoints("0:-179, -1:180, 0:-178, 1:-180"))
    95  
    96  	// A shape gotten from A by adding a triangle to one edge, and
    97  	// subtracting a triangle from the opposite edge.
    98  	loopC = LoopFromPoints(parsePoints("0:178, 0:180, -1:180, 0:-179, 1:-179, 1:-180"))
    99  
   100  	// A shape gotten from A by adding a triangle to one edge, and
   101  	// adding another triangle to the opposite edge.
   102  	loopD = LoopFromPoints(parsePoints("0:178, -1:178, -1:180, 0:-179, 1:-179, 1:-180"))
   103  
   104  	//   3------------2
   105  	//   |            |               ^
   106  	//   |  7-8  b-c  |               |
   107  	//   |  | |  | |  |      Latitude |
   108  	//   0--6-9--a-d--1               |
   109  	//   |  | |       |               |
   110  	//   |  f-e       |               +----------->
   111  	//   |            |                 Longitude
   112  	//   4------------5
   113  	//
   114  	// Important: It is not okay to skip over collinear vertices when
   115  	// defining these loops (e.g. to define loop E as "0,1,2,3") because S2
   116  	// uses symbolic perturbations to ensure that no three vertices are
   117  	// *ever* considered collinear (e.g., vertices 0, 6, 9 are not
   118  	// collinear).  In other words, it is unpredictable (modulo knowing the
   119  	// details of the symbolic perturbations) whether 0123 contains 06123
   120  	// for example.
   121  
   122  	// Loop E:  0,6,9,a,d,1,2,3
   123  	// Loop F:  0,4,5,1,d,a,9,6
   124  	// Loop G:  0,6,7,8,9,a,b,c,d,1,2,3
   125  	// Loop H:  0,6,f,e,9,a,b,c,d,1,2,3
   126  	// Loop I:  7,6,f,e,9,8
   127  	loopE = LoopFromPoints(parsePoints("0:30, 0:34, 0:36, 0:39, 0:41, 0:44, 30:44, 30:30"))
   128  	loopF = LoopFromPoints(parsePoints("0:30, -30:30, -30:44, 0:44, 0:41, 0:39, 0:36, 0:34"))
   129  	loopG = LoopFromPoints(parsePoints("0:30, 0:34, 10:34, 10:36, 0:36, 0:39, 10:39, 10:41, 0:41, 0:44, 30:44, 30:30"))
   130  	loopH = LoopFromPoints(parsePoints("0:30, 0:34, -10:34, -10:36, 0:36, 0:39, 10:39, 10:41, 0:41, 0:44, 30:44, 30:30"))
   131  	loopI = LoopFromPoints(parsePoints("10:34, 0:34, -10:34, -10:36, 0:36, 10:36"))
   132  
   133  	// The set of all test loops.
   134  	allLoops = []*Loop{
   135  		EmptyLoop(),
   136  		FullLoop(),
   137  		northHemi,
   138  		northHemi3,
   139  		southHemi,
   140  		westHemi,
   141  		eastHemi,
   142  		nearHemi,
   143  		farHemi,
   144  		candyCane,
   145  		smallNECW,
   146  		arctic80,
   147  		antarctic80,
   148  		lineTriangle,
   149  		skinnyChevron,
   150  		loopA,
   151  		//snappedLoopA, // Fails TestAreaConsistentWithTurningAngle
   152  		loopB,
   153  		aIntersectB,
   154  		aUnionB,
   155  		aMinusB,
   156  		bMinusA,
   157  		loopC,
   158  		loopD,
   159  		loopE,
   160  		loopF,
   161  		loopG,
   162  		loopH,
   163  		loopI,
   164  	}
   165  )
   166  
   167  func TestLoopEmptyLoop(t *testing.T) {
   168  	shape := EmptyLoop()
   169  
   170  	if got, want := shape.NumEdges(), 0; got != want {
   171  		t.Errorf("shape.NumEdges() = %v, want %v", got, want)
   172  	}
   173  	if got, want := shape.NumChains(), 0; got != want {
   174  		t.Errorf("shape.NumChains() = %v, want %v", got, want)
   175  	}
   176  	if got, want := shape.Dimension(), 2; got != want {
   177  		t.Errorf("shape.Dimension() = %v, want %v", got, want)
   178  	}
   179  	if !shape.IsEmpty() {
   180  		t.Errorf("shape.IsEmpty() = false, want true")
   181  	}
   182  	if shape.IsFull() {
   183  		t.Errorf("shape.IsFull() = true, want false")
   184  	}
   185  	if !shape.isEmptyOrFull() {
   186  		t.Errorf("shape.isEmptyOrFull = false, want true")
   187  	}
   188  	if shape.ReferencePoint().Contained {
   189  		t.Errorf("shape.ReferencePoint().Contained = true, want false")
   190  	}
   191  }
   192  
   193  func TestLoopFullLoop(t *testing.T) {
   194  	shape := FullLoop()
   195  
   196  	if got, want := shape.NumEdges(), 0; got != want {
   197  		t.Errorf("shape.NumEdges() = %v, want %v", got, want)
   198  	}
   199  	if got, want := shape.NumChains(), 1; got != want {
   200  		t.Errorf("shape.NumChains() = %v, want %v", got, want)
   201  	}
   202  	if got, want := shape.Dimension(), 2; got != want {
   203  		t.Errorf("shape.Dimension() = %v, want %v", got, want)
   204  	}
   205  	if shape.IsEmpty() {
   206  		t.Errorf("shape.IsEmpty() = true, want false")
   207  	}
   208  	if !shape.IsFull() {
   209  		t.Errorf("shape.IsFull() = false, want true")
   210  	}
   211  	if !shape.isEmptyOrFull() {
   212  		t.Errorf("shape.isEmptyOrFull = false, want true")
   213  	}
   214  	if !shape.ReferencePoint().Contained {
   215  		t.Errorf("shape.ReferencePoint().Contained = false, want true")
   216  	}
   217  }
   218  
   219  func TestLoopBasic(t *testing.T) {
   220  	shape := Shape(makeLoop("0:0, 0:1, 1:0"))
   221  
   222  	if got, want := shape.NumEdges(), 3; got != want {
   223  		t.Errorf("shape.NumEdges() = %d, want %d", got, want)
   224  	}
   225  	if got, want := shape.NumChains(), 1; got != 1 {
   226  		t.Errorf("shape.NumChains() = %d, want %d", got, want)
   227  	}
   228  	if got, want := shape.Chain(0).Start, 0; got != 0 {
   229  		t.Errorf("shape.Chain(0).Start = %d, want %d", got, want)
   230  	}
   231  	if got, want := shape.Chain(0).Length, 3; got != want {
   232  		t.Errorf("shape.Chain(0).Length = %d, want %d", got, want)
   233  	}
   234  
   235  	e := shape.Edge(2)
   236  	if want := PointFromLatLng(LatLngFromDegrees(1, 0)); !e.V0.ApproxEqual(want) {
   237  		t.Errorf("shape.Edge(2) end A = %v, want %v", e.V0, want)
   238  	}
   239  	if want := PointFromLatLng(LatLngFromDegrees(0, 0)); !e.V1.ApproxEqual(want) {
   240  		t.Errorf("shape.Edge(2) end B = %v, want %v", e.V1, want)
   241  	}
   242  	if got, want := shape.Dimension(), 2; got != want {
   243  		t.Errorf("shape.Dimension() = %v, want %v", got, want)
   244  	}
   245  	if shape.IsEmpty() {
   246  		t.Errorf("shape.IsEmpty() = true, want false")
   247  	}
   248  	if shape.IsFull() {
   249  		t.Errorf("shape.IsFull() = true, want false")
   250  	}
   251  	if shape.ReferencePoint().Contained {
   252  		t.Errorf("shape.ReferencePoint().Contained = true, want false")
   253  	}
   254  }
   255  
   256  func TestLoopHoleAndSign(t *testing.T) {
   257  	l := LoopFromPoints(parsePoints("0:-180, 0:-90, 0:0, 0:90"))
   258  
   259  	if l.IsHole() {
   260  		t.Errorf("loop with default depth should not be a hole")
   261  	}
   262  	if l.Sign() == -1 {
   263  		t.Errorf("loop with default depth should have a sign of +1")
   264  	}
   265  
   266  	l.depth = 3
   267  	if !l.IsHole() {
   268  		t.Errorf("loop with odd depth should be a hole")
   269  	}
   270  	if l.Sign() != -1 {
   271  		t.Errorf("loop with odd depth should have a sign of -1")
   272  	}
   273  
   274  	l.depth = 2
   275  	if l.IsHole() {
   276  		t.Errorf("loop with even depth should not be a hole")
   277  	}
   278  	if l.Sign() == -1 {
   279  		t.Errorf("loop with even depth should have a sign of +1")
   280  	}
   281  
   282  }
   283  
   284  func TestLoopRectBound(t *testing.T) {
   285  	rectError := NewRectBounder().maxErrorForTests()
   286  
   287  	if !EmptyLoop().RectBound().IsEmpty() {
   288  		t.Errorf("empty loop's RectBound should be empty")
   289  	}
   290  	if !FullLoop().RectBound().IsFull() {
   291  		t.Errorf("full loop's RectBound should be full")
   292  	}
   293  	if !candyCane.RectBound().Lng.IsFull() {
   294  		t.Errorf("candy cane loop's RectBound should have a full longitude range")
   295  	}
   296  	if got := candyCane.RectBound().Lat.Lo; got >= -0.349066 {
   297  		t.Errorf("candy cane loop's RectBound should have a lower latitude (%v) under -0.349066 radians", got)
   298  	}
   299  	if got := candyCane.RectBound().Lat.Hi; got <= 0.174533 {
   300  		t.Errorf("candy cane loop's RectBound should have an upper latitude (%v) over 0.174533 radians", got)
   301  	}
   302  	if !smallNECW.RectBound().IsFull() {
   303  		t.Errorf("small northeast clockwise loop's RectBound should be full")
   304  	}
   305  	if got, want := arctic80.RectBound(), rectFromDegrees(80, -180, 90, 180); !rectsApproxEqual(got, want, rectError.Lat.Radians(), rectError.Lng.Radians()) {
   306  		t.Errorf("arctic 80 loop's RectBound (%v) should be %v", got, want)
   307  	}
   308  	if got, want := antarctic80.RectBound(), rectFromDegrees(-90, -180, -80, 180); !rectsApproxEqual(got, want, rectError.Lat.Radians(), rectError.Lng.Radians()) {
   309  		t.Errorf("antarctic 80 loop's RectBound (%v) should be %v", got, want)
   310  	}
   311  
   312  	if !southHemi.RectBound().Lng.IsFull() {
   313  		t.Errorf("south hemi loop's RectBound should have a full longitude range")
   314  	}
   315  	if got, want := southHemi.RectBound().Lat, (r1.Interval{-math.Pi / 2, 0}); !r1IntervalsApproxEqual(got, want, rectError.Lat.Radians()) {
   316  		t.Errorf("south hemi loop's RectBound latitude interval (%v) should be %v", got, want)
   317  	}
   318  
   319  	// Create a loop that contains the complement of the arctic80 loop.
   320  	arctic80Inv := cloneLoop(arctic80)
   321  	arctic80Inv.Invert()
   322  	// The highest latitude of each edge is attained at its midpoint.
   323  	mid := Point{arctic80Inv.vertices[0].Vector.Add(arctic80Inv.vertices[1].Vector).Mul(.5)}
   324  	if got, want := arctic80Inv.RectBound().Lat.Hi, float64(LatLngFromPoint(mid).Lat); !float64Near(got, want, 10*dblEpsilon) {
   325  		t.Errorf("arctic 80 inverse loop's RectBound should have a latutude hi of %v, got %v", got, want)
   326  	}
   327  }
   328  
   329  func TestLoopCapBound(t *testing.T) {
   330  	if !EmptyLoop().CapBound().IsEmpty() {
   331  		t.Errorf("empty loop's CapBound should be empty")
   332  	}
   333  	if !FullLoop().CapBound().IsFull() {
   334  		t.Errorf("full loop's CapBound should be full")
   335  	}
   336  	if !smallNECW.CapBound().IsFull() {
   337  		t.Errorf("small northeast clockwise loop's CapBound should be full")
   338  	}
   339  	if got, want := arctic80.CapBound(), rectFromDegrees(80, -180, 90, 180).CapBound(); !got.ApproxEqual(want) {
   340  		t.Errorf("arctic 80 loop's CapBound (%v) should be %v", got, want)
   341  	}
   342  	if got, want := antarctic80.CapBound(), rectFromDegrees(-90, -180, -80, 180).CapBound(); !got.ApproxEqual(want) {
   343  		t.Errorf("antarctic 80 loop's CapBound (%v) should be %v", got, want)
   344  	}
   345  }
   346  
   347  func TestLoopOriginInside(t *testing.T) {
   348  	if !northHemi.originInside {
   349  		t.Errorf("north hemisphere polygon should include origin")
   350  	}
   351  	if !northHemi3.originInside {
   352  		t.Errorf("north hemisphere 3 polygon should include origin")
   353  	}
   354  	if southHemi.originInside {
   355  		t.Errorf("south hemisphere polygon should not include origin")
   356  	}
   357  	if westHemi.originInside {
   358  		t.Errorf("west hemisphere polygon should not include origin")
   359  	}
   360  	if !eastHemi.originInside {
   361  		t.Errorf("east hemisphere polygon should include origin")
   362  	}
   363  	if nearHemi.originInside {
   364  		t.Errorf("near hemisphere polygon should not include origin")
   365  	}
   366  	if !farHemi.originInside {
   367  		t.Errorf("far hemisphere polygon should include origin")
   368  	}
   369  	if candyCane.originInside {
   370  		t.Errorf("candy cane polygon should not include origin")
   371  	}
   372  	if !smallNECW.originInside {
   373  		t.Errorf("smallNECW polygon should include origin")
   374  	}
   375  	if !arctic80.originInside {
   376  		t.Errorf("arctic 80 polygon should include origin")
   377  	}
   378  	if antarctic80.originInside {
   379  		t.Errorf("antarctic 80 polygon should not include origin")
   380  	}
   381  	if loopA.originInside {
   382  		t.Errorf("loop A polygon should not include origin")
   383  	}
   384  }
   385  
   386  func rotate(l *Loop) *Loop {
   387  	vertices := make([]Point, 0, len(l.vertices))
   388  	for i := 1; i < len(l.vertices); i++ {
   389  		vertices = append(vertices, l.vertices[i])
   390  	}
   391  	vertices = append(vertices, l.vertices[0])
   392  	return LoopFromPoints(vertices)
   393  }
   394  
   395  func TestLoopContainsPoint(t *testing.T) {
   396  	north := Point{r3.Vector{0, 0, 1}}
   397  	south := Point{r3.Vector{0, 0, -1}}
   398  	east := PointFromCoords(0, 1, 0)
   399  	west := PointFromCoords(0, -1, 0)
   400  
   401  	if EmptyLoop().ContainsPoint(north) {
   402  		t.Errorf("empty loop should not not have any points")
   403  	}
   404  	if !FullLoop().ContainsPoint(south) {
   405  		t.Errorf("full loop should have full point vertex")
   406  	}
   407  
   408  	for _, tc := range []struct {
   409  		name string
   410  		l    *Loop
   411  		in   Point
   412  		out  Point
   413  	}{
   414  		{
   415  			"north hemisphere",
   416  			northHemi,
   417  			north,
   418  			south,
   419  		},
   420  		{
   421  			"south hemisphere",
   422  			southHemi,
   423  			south,
   424  			north,
   425  		},
   426  		{
   427  			"west hemisphere",
   428  			westHemi,
   429  			west,
   430  			east,
   431  		},
   432  		{
   433  			"east hemisphere",
   434  			eastHemi,
   435  			east,
   436  			west,
   437  		},
   438  		{
   439  			"candy cane",
   440  			candyCane,
   441  			PointFromLatLng(LatLngFromDegrees(5, 71)),
   442  			PointFromLatLng(LatLngFromDegrees(-8, 71)),
   443  		},
   444  	} {
   445  		l := tc.l
   446  		for i := 0; i < 4; i++ {
   447  			if !l.ContainsPoint(tc.in) {
   448  				t.Errorf("%s loop should contain %v at rotation %d", tc.name, tc.in, i)
   449  			}
   450  			if l.ContainsPoint(tc.out) {
   451  				t.Errorf("%s loop shouldn't contain %v at rotation %d", tc.name, tc.out, i)
   452  			}
   453  			l = rotate(l)
   454  		}
   455  	}
   456  
   457  	// This code checks each cell vertex is contained by exactly one of
   458  	// the adjacent cells.
   459  	for level := 0; level < 3; level++ {
   460  		// set of unique points across all loops at this level.
   461  		points := make(map[Point]bool)
   462  		var loops []*Loop
   463  		for id := CellIDFromFace(0).ChildBeginAtLevel(level); id != CellIDFromFace(5).ChildEndAtLevel(level); id = id.Next() {
   464  			var vertices []Point
   465  			cell := CellFromCellID(id)
   466  			points[cell.Center()] = true
   467  			for k := 0; k < 4; k++ {
   468  				vertices = append(vertices, cell.Vertex(k))
   469  				points[cell.Vertex(k)] = true
   470  			}
   471  			loops = append(loops, LoopFromPoints(vertices))
   472  		}
   473  
   474  		for point := range points {
   475  			count := 0
   476  			for _, loop := range loops {
   477  				if loop.ContainsPoint(point) {
   478  					count++
   479  				}
   480  			}
   481  			if count != 1 {
   482  				t.Errorf("point %v should only be contained by one loop at level %d, got %d", point, level, count)
   483  			}
   484  		}
   485  	}
   486  }
   487  
   488  func TestLoopVertex(t *testing.T) {
   489  	tests := []struct {
   490  		loop   *Loop
   491  		vertex int
   492  		want   Point
   493  	}{
   494  		{EmptyLoop(), 0, Point{r3.Vector{0, 0, 1}}},
   495  		{EmptyLoop(), 1, Point{r3.Vector{0, 0, 1}}},
   496  		{FullLoop(), 0, Point{r3.Vector{0, 0, -1}}},
   497  		{FullLoop(), 1, Point{r3.Vector{0, 0, -1}}},
   498  		{arctic80, 0, parsePoint("80:-150")},
   499  		{arctic80, 1, parsePoint("80:-30")},
   500  		{arctic80, 2, parsePoint("80:90")},
   501  		{arctic80, 3, parsePoint("80:-150")},
   502  	}
   503  
   504  	for _, test := range tests {
   505  		if got := test.loop.Vertex(test.vertex); !pointsApproxEqual(got, test.want, epsilon) {
   506  			t.Errorf("%v.Vertex(%d) = %v, want %v", test.loop, test.vertex, got, test.want)
   507  		}
   508  	}
   509  
   510  	// Check that wrapping is correct.
   511  	if !pointsApproxEqual(arctic80.Vertex(2), arctic80.Vertex(5), epsilon) {
   512  		t.Errorf("Vertex should wrap values. %v.Vertex(2) = %v != %v.Vertex(5) = %v",
   513  			arctic80, arctic80.Vertex(2), arctic80, arctic80.Vertex(5))
   514  	}
   515  
   516  	loopAroundThrice := 2 + 3*len(arctic80.vertices)
   517  	if !pointsApproxEqual(arctic80.Vertex(2), arctic80.Vertex(loopAroundThrice), epsilon) {
   518  		t.Errorf("Vertex should wrap values. %v.Vertex(2) = %v != %v.Vertex(%d) = %v",
   519  			arctic80, arctic80.Vertex(2), arctic80, loopAroundThrice, arctic80.Vertex(loopAroundThrice))
   520  	}
   521  }
   522  
   523  func TestLoopNumEdges(t *testing.T) {
   524  	tests := []struct {
   525  		loop *Loop
   526  		want int
   527  	}{
   528  		{EmptyLoop(), 0},
   529  		{FullLoop(), 0},
   530  		{farHemi, 4},
   531  		{candyCane, 6},
   532  		{smallNECW, 3},
   533  		{arctic80, 3},
   534  		{antarctic80, 3},
   535  		{lineTriangle, 3},
   536  		{skinnyChevron, 4},
   537  	}
   538  
   539  	for _, test := range tests {
   540  		if got := test.loop.NumEdges(); got != test.want {
   541  			t.Errorf("%v.NumEdges() = %v, want %v", test.loop, got, test.want)
   542  		}
   543  	}
   544  }
   545  
   546  func TestLoopEdge(t *testing.T) {
   547  	tests := []struct {
   548  		loop  *Loop
   549  		edge  int
   550  		wantA Point
   551  		wantB Point
   552  	}{
   553  		{
   554  			loop:  farHemi,
   555  			edge:  2,
   556  			wantA: Point{r3.Vector{0, 0, -1}},
   557  			wantB: Point{r3.Vector{0, -1, 0}},
   558  		},
   559  		{
   560  			loop: candyCane,
   561  			edge: 0,
   562  
   563  			wantA: parsePoint("-20:150"),
   564  			wantB: parsePoint("-20:-70"),
   565  		},
   566  		{
   567  			loop:  candyCane,
   568  			edge:  1,
   569  			wantA: parsePoint("-20:-70"),
   570  			wantB: parsePoint("0:70"),
   571  		},
   572  		{
   573  			loop:  candyCane,
   574  			edge:  2,
   575  			wantA: parsePoint("0:70"),
   576  			wantB: parsePoint("10:-150"),
   577  		},
   578  		{
   579  			loop:  candyCane,
   580  			edge:  3,
   581  			wantA: parsePoint("10:-150"),
   582  			wantB: parsePoint("10:70"),
   583  		},
   584  		{
   585  			loop:  candyCane,
   586  			edge:  4,
   587  			wantA: parsePoint("10:70"),
   588  			wantB: parsePoint("-10:-70"),
   589  		},
   590  		{
   591  			loop:  candyCane,
   592  			edge:  5,
   593  			wantA: parsePoint("-10:-70"),
   594  			wantB: parsePoint("-20:150"),
   595  		},
   596  		{
   597  			loop:  skinnyChevron,
   598  			edge:  2,
   599  			wantA: parsePoint("0:1e-320"),
   600  			wantB: parsePoint("1e-320:80"),
   601  		},
   602  		{
   603  			loop:  skinnyChevron,
   604  			edge:  3,
   605  			wantA: parsePoint("1e-320:80"),
   606  			wantB: parsePoint("0:0"),
   607  		},
   608  	}
   609  
   610  	for _, test := range tests {
   611  		if e := test.loop.Edge(test.edge); !(pointsApproxEqual(e.V0, test.wantA, epsilon) && pointsApproxEqual(e.V1, test.wantB, epsilon)) {
   612  			t.Errorf("%v.Edge(%d) = %v, want (%v, %v)", test.loop, test.edge, e, test.wantA, test.wantB)
   613  		}
   614  	}
   615  }
   616  
   617  func TestLoopFromCell(t *testing.T) {
   618  	cell := CellFromCellID(CellIDFromLatLng(LatLng{40.565459 * s1.Degree, -74.645276 * s1.Degree}))
   619  	loopFromCell := LoopFromCell(cell)
   620  
   621  	// Demonstrates the reason for this test; the cell bounds are more
   622  	// conservative than the resulting loop bounds.
   623  	if loopFromCell.RectBound().Contains(cell.RectBound()) {
   624  		t.Errorf("loopFromCell's RectBound contains the original cells RectBound, but should not")
   625  	}
   626  }
   627  
   628  func TestLoopRegularLoop(t *testing.T) {
   629  	loop := RegularLoop(PointFromLatLng(LatLngFromDegrees(80, 135)), 20*s1.Degree, 4)
   630  	if len(loop.vertices) != 4 {
   631  		t.Errorf("RegularLoop with 4 vertices should have 4 vertices, got %d", len(loop.vertices))
   632  	}
   633  	// The actual Points values are already tested in the s2point_test method TestRegularPoints.
   634  }
   635  
   636  // cloneLoop creates a new copy of the given loop including all of its vertices
   637  // so that when tests modify vertices in it, it won't ruin the original loop.
   638  func cloneLoop(l *Loop) *Loop {
   639  	c := &Loop{
   640  		vertices:       make([]Point, len(l.vertices)),
   641  		originInside:   l.originInside,
   642  		bound:          l.bound,
   643  		subregionBound: l.subregionBound,
   644  		index:          NewShapeIndex(),
   645  	}
   646  	copy(c.vertices, l.vertices)
   647  	c.index.Add(c)
   648  
   649  	return c
   650  }
   651  
   652  func TestLoopEqual(t *testing.T) {
   653  	tests := []struct {
   654  		a, b *Loop
   655  		want bool
   656  	}{
   657  		{
   658  			a:    EmptyLoop(),
   659  			b:    EmptyLoop(),
   660  			want: true,
   661  		},
   662  		{
   663  			a:    FullLoop(),
   664  			b:    FullLoop(),
   665  			want: true,
   666  		},
   667  		{
   668  			a:    EmptyLoop(),
   669  			b:    FullLoop(),
   670  			want: false,
   671  		},
   672  		{
   673  			a:    candyCane,
   674  			b:    candyCane,
   675  			want: true,
   676  		},
   677  		{
   678  			a:    candyCane,
   679  			b:    rotate(candyCane),
   680  			want: false,
   681  		},
   682  		{
   683  			a:    candyCane,
   684  			b:    rotate(rotate(candyCane)),
   685  			want: false,
   686  		},
   687  		{
   688  			a:    candyCane,
   689  			b:    rotate(rotate(rotate(candyCane))),
   690  			want: false,
   691  		},
   692  		{
   693  			a:    candyCane,
   694  			b:    rotate(rotate(rotate(rotate(candyCane)))),
   695  			want: false,
   696  		},
   697  		{
   698  			a:    candyCane,
   699  			b:    rotate(rotate(rotate(rotate(rotate(candyCane))))),
   700  			want: false,
   701  		},
   702  		{
   703  			// candyCane has 6 points, so 6 rotates should line up again.
   704  			a:    candyCane,
   705  			b:    rotate(rotate(rotate(rotate(rotate(rotate(candyCane)))))),
   706  			want: true,
   707  		},
   708  	}
   709  
   710  	for _, test := range tests {
   711  		if got := test.a.Equal(test.b); got != test.want {
   712  			t.Errorf("%v.Equal(%v) = %t, want %t", test.a, test.b, got, test.want)
   713  		}
   714  	}
   715  }
   716  
   717  func TestLoopContainsMatchesCrossingSign(t *testing.T) {
   718  	// This test demonstrates a former incompatibility between CrossingSign
   719  	// and ContainsPoint. It constructs a Cell-based loop L and
   720  	// an edge E from Origin to a0 that crosses exactly one edge of L.  Yet
   721  	// previously, Contains() returned false for both endpoints of E.
   722  	//
   723  	// The reason for the bug was that the loop bound was sometimes too tight.
   724  	// The Contains() code for a0 bailed out early because a0 was found not to
   725  	// be inside the bound of L.
   726  
   727  	// Start with a cell that ends up producing the problem.
   728  	cellID := cellIDFromPoint(Point{r3.Vector{1, 1, 1}}).Parent(21)
   729  	children, ok := CellFromCellID(cellID).Children()
   730  	if !ok {
   731  		t.Fatalf("error subdividing cell")
   732  	}
   733  
   734  	points := make([]Point, 4)
   735  	for i := 0; i < 4; i++ {
   736  		// Note extra normalization. Center() is already normalized.
   737  		// The test results will no longer be inconsistent if the extra
   738  		// Normalize() is removed.
   739  		points[i] = Point{children[i].Center().Normalize()}
   740  	}
   741  
   742  	// Get a vertex from a grandchild cell.
   743  	// +---------------+---------------+
   744  	// |               |               |
   745  	// |    points[3]  |   points[2]   |
   746  	// |       v       |       v       |
   747  	// |       +-------+------ +       |
   748  	// |       |       |       |       |
   749  	// |       |       |       |       |
   750  	// |       |       |       |       |
   751  	// +-------+-------+-------+-------+
   752  	// |       |       |       |       |
   753  	// |       |    <----------------------- grandchild_cell
   754  	// |       |       |       |       |
   755  	// |       +-------+------ +       |
   756  	// |       ^       |       ^       | <-- cell
   757  	// | points[0]/a0  |     points[1] |
   758  	// |               |               |
   759  	// +---------------+---------------+
   760  	loop := LoopFromPoints(points)
   761  	grandchildren, ok := children[0].Children()
   762  	if !ok {
   763  		t.Fatalf("error subdividing cell")
   764  	}
   765  
   766  	grandchildCell := grandchildren[2]
   767  
   768  	a0 := grandchildCell.Vertex(0)
   769  
   770  	// This test depends on rounding errors that should make a0 slightly different from points[0]
   771  	if points[0] == a0 {
   772  		t.Errorf("%v not different enough from %v to successfully test", points[0], a0)
   773  	}
   774  
   775  	// The edge from a0 to the origin crosses one boundary.
   776  	if got, want := NewChainEdgeCrosser(a0, OriginPoint(), loop.Vertex(0)).ChainCrossingSign(loop.Vertex(1)), DoNotCross; got != want {
   777  		t.Errorf("crossingSign(%v, %v, %v, %v) = %v, want %v", a0, OriginPoint(), loop.Vertex(0), loop.Vertex(1), got, want)
   778  	}
   779  
   780  	if got, want := NewChainEdgeCrosser(a0, OriginPoint(), loop.Vertex(1)).ChainCrossingSign(loop.Vertex(2)), Cross; got != want {
   781  		t.Errorf("crossingSign(%v, %v, %v, %v) = %v, want %v", a0, OriginPoint(), loop.Vertex(1), loop.Vertex(2), got, want)
   782  	}
   783  
   784  	if got, want := NewChainEdgeCrosser(a0, OriginPoint(), loop.Vertex(2)).ChainCrossingSign(loop.Vertex(3)), DoNotCross; got != want {
   785  		t.Errorf("crossingSign(%v, %v, %v, %v) = %v, want %v", a0, OriginPoint(), loop.Vertex(2), loop.Vertex(3), got, want)
   786  	}
   787  
   788  	if got, want := NewChainEdgeCrosser(a0, OriginPoint(), loop.Vertex(3)).ChainCrossingSign(loop.Vertex(4)), DoNotCross; got != want {
   789  		t.Errorf("crossingSign(%v, %v, %v, %v) = %v, want %v", a0, OriginPoint(), loop.Vertex(3), loop.Vertex(4), got, want)
   790  	}
   791  
   792  	// Contains should return false for the origin, and true for a0.
   793  	if loop.ContainsPoint(OriginPoint()) {
   794  		t.Errorf("%v.ContainsPoint(%v) = true, want false", loop, OriginPoint())
   795  	}
   796  	if !loop.ContainsPoint(a0) {
   797  		t.Errorf("%v.ContainsPoint(%v) = false, want true", loop, a0)
   798  	}
   799  
   800  	// Since a0 is inside the loop, it should be inside the bound.
   801  	bound := loop.RectBound()
   802  	if !bound.ContainsPoint(a0) {
   803  		t.Errorf("%v.RectBound().ContainsPoint(%v) = false, want true", loop, a0)
   804  	}
   805  }
   806  
   807  func TestLoopRelations(t *testing.T) {
   808  	tests := []struct {
   809  		a, b       *Loop
   810  		contains   bool // A contains B
   811  		contained  bool // B contains A
   812  		disjoint   bool // A and B are disjoint (intersection is empty)
   813  		covers     bool // (A union B) covers the entire sphere
   814  		sharedEdge bool // the loops share at least one edge (possibly reversed)
   815  	}{
   816  		// Check full and empty relationships with normal loops and each other.
   817  		{
   818  			a:          FullLoop(),
   819  			b:          FullLoop(),
   820  			contains:   true,
   821  			contained:  true,
   822  			covers:     true,
   823  			sharedEdge: true,
   824  		},
   825  		{
   826  			a:          FullLoop(),
   827  			b:          northHemi,
   828  			contains:   true,
   829  			covers:     true,
   830  			sharedEdge: false,
   831  		},
   832  		{
   833  			a:          FullLoop(),
   834  			b:          EmptyLoop(),
   835  			contains:   true,
   836  			disjoint:   true,
   837  			covers:     true,
   838  			sharedEdge: false,
   839  		},
   840  		{
   841  			a:          northHemi,
   842  			b:          FullLoop(),
   843  			contained:  true,
   844  			covers:     true,
   845  			sharedEdge: false,
   846  		},
   847  		{
   848  			a:          northHemi,
   849  			b:          EmptyLoop(),
   850  			contains:   true,
   851  			disjoint:   true,
   852  			sharedEdge: false,
   853  		},
   854  		{
   855  			a:          EmptyLoop(),
   856  			b:          FullLoop(),
   857  			contained:  true,
   858  			disjoint:   true,
   859  			covers:     true,
   860  			sharedEdge: false,
   861  		},
   862  		{
   863  			a:          EmptyLoop(),
   864  			b:          northHemi,
   865  			contained:  true,
   866  			disjoint:   true,
   867  			sharedEdge: false,
   868  		},
   869  		{
   870  			a:          EmptyLoop(),
   871  			b:          EmptyLoop(),
   872  			contains:   true,
   873  			contained:  true,
   874  			disjoint:   true,
   875  			sharedEdge: false,
   876  		},
   877  		{
   878  			a:          northHemi,
   879  			b:          northHemi,
   880  			contains:   true,
   881  			contained:  true,
   882  			sharedEdge: true,
   883  		},
   884  		{
   885  			a:          northHemi,
   886  			b:          southHemi,
   887  			disjoint:   true,
   888  			covers:     true,
   889  			sharedEdge: true,
   890  		},
   891  		{
   892  			a: northHemi,
   893  			b: eastHemi,
   894  		},
   895  		{
   896  			a:          northHemi,
   897  			b:          arctic80,
   898  			contains:   true,
   899  			sharedEdge: false,
   900  		},
   901  		{
   902  			a:          northHemi,
   903  			b:          antarctic80,
   904  			disjoint:   true,
   905  			sharedEdge: false,
   906  		},
   907  		{
   908  			a: northHemi,
   909  			b: candyCane,
   910  		},
   911  		// We can't compare northHemi3 vs. northHemi or southHemi because the
   912  		// result depends on the "simulation of simplicity" implementation details.
   913  		{
   914  			a:          northHemi3,
   915  			b:          northHemi3,
   916  			contains:   true,
   917  			contained:  true,
   918  			sharedEdge: true,
   919  		},
   920  		{
   921  			a: northHemi3,
   922  			b: eastHemi,
   923  		},
   924  		{
   925  			a:          northHemi3,
   926  			b:          arctic80,
   927  			contains:   true,
   928  			sharedEdge: false,
   929  		},
   930  		{
   931  			a:          northHemi3,
   932  			b:          antarctic80,
   933  			disjoint:   true,
   934  			sharedEdge: false,
   935  		},
   936  		{
   937  			a: northHemi3,
   938  			b: candyCane,
   939  		},
   940  		{
   941  			a:          southHemi,
   942  			b:          northHemi,
   943  			disjoint:   true,
   944  			covers:     true,
   945  			sharedEdge: true,
   946  		},
   947  		{
   948  			a:          southHemi,
   949  			b:          southHemi,
   950  			contains:   true,
   951  			contained:  true,
   952  			sharedEdge: true,
   953  		},
   954  		{
   955  			a: southHemi,
   956  			b: farHemi,
   957  		},
   958  		{
   959  			a:          southHemi,
   960  			b:          arctic80,
   961  			disjoint:   true,
   962  			sharedEdge: false,
   963  		},
   964  		// xxxx?
   965  		{
   966  			a:          southHemi,
   967  			b:          antarctic80,
   968  			contains:   true,
   969  			sharedEdge: false,
   970  		},
   971  		{
   972  			a: southHemi,
   973  			b: candyCane,
   974  		},
   975  		{
   976  			a: candyCane,
   977  			b: northHemi,
   978  		},
   979  		{
   980  			a: candyCane,
   981  			b: southHemi,
   982  		},
   983  		{
   984  			a:          candyCane,
   985  			b:          arctic80,
   986  			disjoint:   true,
   987  			sharedEdge: false,
   988  		},
   989  		{
   990  			a:          candyCane,
   991  			b:          antarctic80,
   992  			disjoint:   true,
   993  			sharedEdge: false,
   994  		},
   995  		{
   996  			a:          candyCane,
   997  			b:          candyCane,
   998  			contains:   true,
   999  			contained:  true,
  1000  			sharedEdge: true,
  1001  		},
  1002  		{
  1003  			a: nearHemi,
  1004  			b: westHemi,
  1005  		},
  1006  		{
  1007  			a:          smallNECW,
  1008  			b:          southHemi,
  1009  			contains:   true,
  1010  			sharedEdge: false,
  1011  		},
  1012  		{
  1013  			a:          smallNECW,
  1014  			b:          westHemi,
  1015  			contains:   true,
  1016  			sharedEdge: false,
  1017  		},
  1018  		{
  1019  			a:          smallNECW,
  1020  			b:          northHemi,
  1021  			covers:     true,
  1022  			sharedEdge: false,
  1023  		},
  1024  		{
  1025  			a:          smallNECW,
  1026  			b:          eastHemi,
  1027  			covers:     true,
  1028  			sharedEdge: false,
  1029  		},
  1030  		{
  1031  			a:          loopA,
  1032  			b:          loopA,
  1033  			contains:   true,
  1034  			contained:  true,
  1035  			sharedEdge: true,
  1036  		},
  1037  		{
  1038  			a: loopA,
  1039  			b: loopB,
  1040  		},
  1041  		{
  1042  			a:          loopA,
  1043  			b:          aIntersectB,
  1044  			contains:   true,
  1045  			sharedEdge: true,
  1046  		},
  1047  		{
  1048  			a:          loopA,
  1049  			b:          aUnionB,
  1050  			contained:  true,
  1051  			sharedEdge: true,
  1052  		},
  1053  		{
  1054  			a:          loopA,
  1055  			b:          aMinusB,
  1056  			contains:   true,
  1057  			sharedEdge: true,
  1058  		},
  1059  		{
  1060  			a:          loopA,
  1061  			b:          bMinusA,
  1062  			disjoint:   true,
  1063  			sharedEdge: true,
  1064  		},
  1065  		{
  1066  			a: loopB,
  1067  			b: loopA,
  1068  		},
  1069  		{
  1070  			a:          loopB,
  1071  			b:          loopB,
  1072  			contains:   true,
  1073  			contained:  true,
  1074  			sharedEdge: true,
  1075  		},
  1076  		{
  1077  			a:          loopB,
  1078  			b:          aIntersectB,
  1079  			contains:   true,
  1080  			sharedEdge: true,
  1081  		},
  1082  		{
  1083  			a:          loopB,
  1084  			b:          aUnionB,
  1085  			contained:  true,
  1086  			sharedEdge: true,
  1087  		},
  1088  		{
  1089  			a:          loopB,
  1090  			b:          aMinusB,
  1091  			disjoint:   true,
  1092  			sharedEdge: true,
  1093  		},
  1094  		{
  1095  			a:          loopB,
  1096  			b:          bMinusA,
  1097  			contains:   true,
  1098  			sharedEdge: true,
  1099  		},
  1100  		{
  1101  			a:          aIntersectB,
  1102  			b:          loopA,
  1103  			contained:  true,
  1104  			sharedEdge: true,
  1105  		},
  1106  		{
  1107  			a:          aIntersectB,
  1108  			b:          loopB,
  1109  			contained:  true,
  1110  			sharedEdge: true,
  1111  		},
  1112  		{
  1113  			a:          aIntersectB,
  1114  			b:          aIntersectB,
  1115  			contains:   true,
  1116  			contained:  true,
  1117  			sharedEdge: true,
  1118  		},
  1119  		{
  1120  			a:          aIntersectB,
  1121  			b:          aUnionB,
  1122  			contained:  true,
  1123  			sharedEdge: false,
  1124  		},
  1125  		{
  1126  			a:          aIntersectB,
  1127  			b:          aMinusB,
  1128  			disjoint:   true,
  1129  			sharedEdge: true,
  1130  		},
  1131  		{
  1132  			a:          aIntersectB,
  1133  			b:          bMinusA,
  1134  			disjoint:   true,
  1135  			sharedEdge: true,
  1136  		},
  1137  		{
  1138  			a:          aUnionB,
  1139  			b:          loopA,
  1140  			contains:   true,
  1141  			sharedEdge: true,
  1142  		},
  1143  		{
  1144  			a:          aUnionB,
  1145  			b:          loopB,
  1146  			contains:   true,
  1147  			sharedEdge: true,
  1148  		},
  1149  		{
  1150  			a:          aUnionB,
  1151  			b:          aIntersectB,
  1152  			contains:   true,
  1153  			sharedEdge: false,
  1154  		},
  1155  		{
  1156  			a:          aUnionB,
  1157  			b:          aUnionB,
  1158  			contains:   true,
  1159  			contained:  true,
  1160  			sharedEdge: true,
  1161  		},
  1162  		{
  1163  			a:          aUnionB,
  1164  			b:          aMinusB,
  1165  			contains:   true,
  1166  			sharedEdge: true,
  1167  		},
  1168  		{
  1169  			a:          aUnionB,
  1170  			b:          bMinusA,
  1171  			contains:   true,
  1172  			sharedEdge: true,
  1173  		},
  1174  		{
  1175  			a:          aMinusB,
  1176  			b:          loopA,
  1177  			contained:  true,
  1178  			sharedEdge: true,
  1179  		},
  1180  		{
  1181  			a:          aMinusB,
  1182  			b:          loopB,
  1183  			disjoint:   true,
  1184  			sharedEdge: true,
  1185  		},
  1186  		{
  1187  			a:          aMinusB,
  1188  			b:          aIntersectB,
  1189  			disjoint:   true,
  1190  			sharedEdge: true,
  1191  		},
  1192  		{
  1193  			a:          aMinusB,
  1194  			b:          aUnionB,
  1195  			contained:  true,
  1196  			sharedEdge: true,
  1197  		},
  1198  		{
  1199  			a:          aMinusB,
  1200  			b:          aMinusB,
  1201  			contains:   true,
  1202  			contained:  true,
  1203  			sharedEdge: true,
  1204  		},
  1205  		{
  1206  			a:          aMinusB,
  1207  			b:          bMinusA,
  1208  			disjoint:   true,
  1209  			sharedEdge: false,
  1210  		},
  1211  		{
  1212  			a:          bMinusA,
  1213  			b:          loopA,
  1214  			disjoint:   true,
  1215  			sharedEdge: true,
  1216  		},
  1217  		{
  1218  			a:          bMinusA,
  1219  			b:          loopB,
  1220  			contained:  true,
  1221  			sharedEdge: true,
  1222  		},
  1223  		{
  1224  			a:          bMinusA,
  1225  			b:          aIntersectB,
  1226  			disjoint:   true,
  1227  			sharedEdge: true,
  1228  		},
  1229  		{
  1230  			a:          bMinusA,
  1231  			b:          aUnionB,
  1232  			contained:  true,
  1233  			sharedEdge: true,
  1234  		},
  1235  		{
  1236  			a:          bMinusA,
  1237  			b:          aMinusB,
  1238  			disjoint:   true,
  1239  			sharedEdge: false,
  1240  		},
  1241  		{
  1242  			a:          bMinusA,
  1243  			b:          bMinusA,
  1244  			contains:   true,
  1245  			contained:  true,
  1246  			sharedEdge: true,
  1247  		},
  1248  		// Make sure the relations are correct if the loop crossing happens on
  1249  		// two ends of a shared boundary segment.
  1250  		// LoopRelationsWhenSameExceptPiecesStickingOutAndIn
  1251  		{
  1252  			a:          loopA,
  1253  			b:          loopC,
  1254  			sharedEdge: true,
  1255  		},
  1256  		{
  1257  			a:          loopC,
  1258  			b:          loopA,
  1259  			sharedEdge: true,
  1260  		},
  1261  		{
  1262  			a:          loopA,
  1263  			b:          loopD,
  1264  			contained:  true,
  1265  			sharedEdge: true,
  1266  		},
  1267  		{
  1268  			a:          loopD,
  1269  			b:          loopA,
  1270  			contains:   true,
  1271  			sharedEdge: true,
  1272  		},
  1273  		{
  1274  			a:          loopE,
  1275  			b:          loopF,
  1276  			disjoint:   true,
  1277  			sharedEdge: true,
  1278  		},
  1279  		{
  1280  			a:          loopE,
  1281  			b:          loopG,
  1282  			contains:   true,
  1283  			sharedEdge: true,
  1284  		},
  1285  		{
  1286  			a:          loopE,
  1287  			b:          loopH,
  1288  			sharedEdge: true,
  1289  		},
  1290  		{
  1291  			a:          loopE,
  1292  			b:          loopI,
  1293  			sharedEdge: false,
  1294  		},
  1295  		{
  1296  			a:          loopF,
  1297  			b:          loopG,
  1298  			disjoint:   true,
  1299  			sharedEdge: true,
  1300  		},
  1301  		{
  1302  			a:          loopF,
  1303  			b:          loopH,
  1304  			sharedEdge: true,
  1305  		},
  1306  		{
  1307  			a:          loopF,
  1308  			b:          loopI,
  1309  			sharedEdge: false,
  1310  		},
  1311  		{
  1312  			a:          loopG,
  1313  			b:          loopH,
  1314  			contained:  true,
  1315  			sharedEdge: true,
  1316  		},
  1317  		{
  1318  			a:          loopH,
  1319  			b:          loopG,
  1320  			contains:   true,
  1321  			sharedEdge: true,
  1322  		},
  1323  		{
  1324  			a:          loopG,
  1325  			b:          loopI,
  1326  			disjoint:   true,
  1327  			sharedEdge: true,
  1328  		},
  1329  		{
  1330  			a:          loopH,
  1331  			b:          loopI,
  1332  			contains:   true,
  1333  			sharedEdge: true,
  1334  		},
  1335  	}
  1336  
  1337  	for _, test := range tests {
  1338  		if test.contains {
  1339  			testLoopNestedPair(t, test.a, test.b)
  1340  		}
  1341  		if test.contained {
  1342  			testLoopNestedPair(t, test.b, test.a)
  1343  		}
  1344  		if test.covers {
  1345  			b1 := cloneLoop(test.b)
  1346  			b1.Invert()
  1347  			testLoopNestedPair(t, test.a, b1)
  1348  		}
  1349  		if test.disjoint {
  1350  			a1 := cloneLoop(test.a)
  1351  			a1.Invert()
  1352  			testLoopNestedPair(t, a1, test.b)
  1353  		} else if !(test.contains || test.contained || test.covers) {
  1354  			// Given loops A and B such that both A and its complement
  1355  			// intersect both B and its complement, test various
  1356  			// identities involving these four loops.
  1357  			a1 := cloneLoop(test.a)
  1358  			a1.Invert()
  1359  			b1 := cloneLoop(test.b)
  1360  			b1.Invert()
  1361  			testLoopOneOverlappingPair(t, test.a, test.b)
  1362  			testLoopOneOverlappingPair(t, a1, b1)
  1363  			testLoopOneOverlappingPair(t, a1, test.b)
  1364  			testLoopOneOverlappingPair(t, test.a, b1)
  1365  		}
  1366  		if !test.sharedEdge && (test.contains || test.contained || test.disjoint) {
  1367  			if got, want := test.a.Contains(test.b), test.a.ContainsNested(test.b); got != want {
  1368  				t.Errorf("%v.Contains(%v) = %v, but should equal %v.ContainsNested(%v) = %v", test.a, test.b, got, test.a, test.b, want)
  1369  			}
  1370  		}
  1371  
  1372  		// A contains the boundary of B if either A contains B, or the two loops
  1373  		// contain each other's boundaries and there are no shared edges (since at
  1374  		// least one such edge must be reversed, and therefore is not considered to
  1375  		// be contained according to the rules of compareBoundary).
  1376  		comparison := 0
  1377  		if test.contains || (test.covers && !test.sharedEdge) {
  1378  			comparison = 1
  1379  		}
  1380  
  1381  		// Similarly, A excludes the boundary of B if either A and B are disjoint,
  1382  		// or B contains A and there are no shared edges (since A is considered to
  1383  		// contain such edges according to the rules of compareBoundary).
  1384  		if test.disjoint || (test.contained && !test.sharedEdge) {
  1385  			comparison = -1
  1386  		}
  1387  
  1388  		// compareBoundary requires that neither loop is empty.
  1389  		if !test.a.IsEmpty() && !test.b.IsEmpty() {
  1390  			if got := test.a.compareBoundary(test.b); got != comparison {
  1391  				t.Errorf("%v.compareBoundary(%v) = %v, want %v", test.a, test.b, got, comparison)
  1392  			}
  1393  		}
  1394  	}
  1395  }
  1396  
  1397  // Given a pair of loops where A contains B, test various identities
  1398  // involving A, B, and their complements.
  1399  func testLoopNestedPair(t *testing.T, a, b *Loop) {
  1400  	a1 := cloneLoop(a)
  1401  	a1.Invert()
  1402  	b1 := cloneLoop(b)
  1403  	b1.Invert()
  1404  	testLoopOneNestedPair(t, a, b)
  1405  	testLoopOneNestedPair(t, b1, a1)
  1406  	testLoopOneDisjointPair(t, a1, b)
  1407  	testLoopOneCoveringPair(t, a, b1)
  1408  }
  1409  
  1410  // Given a pair of loops where A contains B, check various identities.
  1411  func testLoopOneNestedPair(t *testing.T, a, b *Loop) {
  1412  	if !a.Contains(b) {
  1413  		t.Errorf("%v.Contains(%v) = false, want true", a, b)
  1414  	}
  1415  	if got, want := b.Contains(a), a.BoundaryEqual(b); got != want {
  1416  		t.Errorf("%v.Contains(%v) = %v, want %v", b, a, got, want)
  1417  	}
  1418  	if got, want := a.Intersects(b), !b.IsEmpty(); got != want {
  1419  		t.Errorf("%v.Intersects(%v) = %v, want %v", a, b, got, want)
  1420  	}
  1421  	if got, want := b.Intersects(a), !b.IsEmpty(); got != want {
  1422  		t.Errorf("%v.Intersects(%v) = %v, want %v", b, a, got, want)
  1423  	}
  1424  }
  1425  
  1426  // Given a pair of disjoint loops A and B, check various identities.
  1427  func testLoopOneDisjointPair(t *testing.T, a, b *Loop) {
  1428  	if a.Intersects(b) {
  1429  		t.Errorf("%v.Intersects(%v) = true, want false", a, b)
  1430  	}
  1431  	if b.Intersects(a) {
  1432  		t.Errorf("%v.Intersects(%v) = true, want false", b, a)
  1433  	}
  1434  	if got, want := a.Contains(b), b.IsEmpty(); got != want {
  1435  		t.Errorf("%v.Contains(%v) = %v, want %v", a, b, got, want)
  1436  	}
  1437  	if got, want := b.Contains(a), a.IsEmpty(); got != want {
  1438  		t.Errorf("%v.Contains(%v) = %v, want %v", b, a, got, want)
  1439  	}
  1440  }
  1441  
  1442  // Given loops A and B whose union covers the sphere, check various identities.
  1443  func testLoopOneCoveringPair(t *testing.T, a, b *Loop) {
  1444  	if got, want := a.Contains(b), a.IsFull(); got != want {
  1445  		t.Errorf("%v.Contains(%v) = %v, want %v", a, b, got, want)
  1446  	}
  1447  	if got, want := b.Contains(a), b.IsFull(); got != want {
  1448  		t.Errorf("%v.Contains(%v) = %v, want %v", b, a, got, want)
  1449  	}
  1450  	a1 := cloneLoop(a)
  1451  	a1.Invert()
  1452  	complementary := a1.BoundaryEqual(b)
  1453  	if got, want := a.Intersects(b), !complementary; got != want {
  1454  		t.Errorf("%v.Intersects(%v) = %v, want %v", a, b, got, want)
  1455  	}
  1456  	if got, want := b.Intersects(a), !complementary; got != want {
  1457  		t.Errorf("%v.Intersects(%v) = %v, want %v", b, a, got, want)
  1458  	}
  1459  }
  1460  
  1461  // Given loops A and B such that both A and its complement intersect both B
  1462  // and its complement, check various identities.
  1463  func testLoopOneOverlappingPair(t *testing.T, a, b *Loop) {
  1464  	if a.Contains(b) {
  1465  		t.Errorf("%v.Contains(%v) = true want false", a, b)
  1466  	}
  1467  	if b.Contains(a) {
  1468  		t.Errorf("%v.Contains(%v) = true want false", b, a)
  1469  	}
  1470  	if !a.Intersects(b) {
  1471  		t.Errorf("%v.Intersects(%v) = false, want true", a, b)
  1472  	}
  1473  	if !b.Intersects(a) {
  1474  		t.Errorf("%v.Intersects(%v) = false, want true", b, a)
  1475  	}
  1476  }
  1477  
  1478  func TestLoopTurningAngle(t *testing.T) {
  1479  	tests := []struct {
  1480  		loop *Loop
  1481  		want float64
  1482  	}{
  1483  		{EmptyLoop(), 2 * math.Pi},
  1484  		{FullLoop(), -2 * math.Pi},
  1485  		{northHemi3, 0},
  1486  		{westHemi, 0},
  1487  		{candyCane, 4.69364376125922},
  1488  		{lineTriangle, 2 * math.Pi},
  1489  		{skinnyChevron, 2 * math.Pi},
  1490  	}
  1491  
  1492  	for _, test := range tests {
  1493  		if got := test.loop.TurningAngle(); !float64Near(got, test.want, epsilon) {
  1494  			t.Errorf("%v.TurningAngle() = %v, want %v", test.loop, got, test.want)
  1495  		}
  1496  
  1497  		// Check that the turning angle is *identical* when the vertex order is
  1498  		// rotated, and that the sign is inverted when the vertices are reversed.
  1499  		expected := test.loop.TurningAngle()
  1500  		loopCopy := cloneLoop(test.loop)
  1501  		for i := 0; i < len(test.loop.vertices); i++ {
  1502  			loopCopy.Invert()
  1503  			if got := loopCopy.TurningAngle(); got != -expected {
  1504  				t.Errorf("loop.Invert().TurningAngle() = %v, want %v", got, -expected)
  1505  			}
  1506  			// Invert it back to normal.
  1507  			loopCopy.Invert()
  1508  
  1509  			loopCopy = rotate(loopCopy)
  1510  			if got := loopCopy.TurningAngle(); got != expected {
  1511  				t.Errorf("loop.TurningAngle() = %v, want %v", got, expected)
  1512  			}
  1513  		}
  1514  	}
  1515  
  1516  	// Build a narrow spiral loop starting at the north pole. This is designed
  1517  	// to test that the error in TurningAngle is linear in the number of
  1518  	// vertices even when the partial sum of the turning angles gets very large.
  1519  	// The spiral consists of two arms defining opposite sides of the loop.
  1520  	const armPoints = 10000 // Number of vertices in each "arm"
  1521  	const armRadius = 0.01  // Radius of spiral.
  1522  	var vertices = make([]Point, 2*armPoints)
  1523  
  1524  	// Set the center point of the spiral.
  1525  	vertices[armPoints] = PointFromCoords(0, 0, 1)
  1526  
  1527  	for i := 0; i < armPoints; i++ {
  1528  		angle := (2 * math.Pi / 3) * float64(i)
  1529  		x := math.Cos(angle)
  1530  		y := math.Sin(angle)
  1531  		r1 := float64(i) * armRadius / armPoints
  1532  		r2 := (float64(i) + 1.5) * armRadius / armPoints
  1533  		vertices[armPoints-i-1] = PointFromCoords(r1*x, r1*y, 1)
  1534  		vertices[armPoints+i] = PointFromCoords(r2*x, r2*y, 1)
  1535  	}
  1536  	// This is a pathological loop that contains many long parallel edges.
  1537  	spiral := LoopFromPoints(vertices)
  1538  
  1539  	// Check that TurningAngle is consistent with Area to within the
  1540  	// error bound of the former. We actually use a tiny fraction of the
  1541  	// worst-case error bound, since the worst case only happens when all the
  1542  	// roundoff errors happen in the same direction and this test is not
  1543  	// designed to achieve that. The error in Area can be ignored for the
  1544  	// purposes of this test since it is generally much smaller.
  1545  	if got, want := spiral.TurningAngle(), (2*math.Pi - spiral.Area()); !float64Near(got, want, 0.01*spiral.turningAngleMaxError()) {
  1546  		t.Errorf("spiral.TurningAngle() = %v, want %v", got, want)
  1547  	}
  1548  }
  1549  
  1550  func TestLoopAreaAndCentroid(t *testing.T) {
  1551  	var p Point
  1552  
  1553  	if got, want := EmptyLoop().Area(), 0.0; got != want {
  1554  		t.Errorf("EmptyLoop.Area() = %v, want %v", got, want)
  1555  	}
  1556  	if got, want := FullLoop().Area(), 4*math.Pi; got != want {
  1557  		t.Errorf("FullLoop.Area() = %v, want %v", got, want)
  1558  	}
  1559  	if got := EmptyLoop().Centroid(); !p.ApproxEqual(got) {
  1560  		t.Errorf("EmptyLoop.Centroid() = %v, want %v", got, p)
  1561  	}
  1562  	if got := FullLoop().Centroid(); !p.ApproxEqual(got) {
  1563  		t.Errorf("FullLoop.Centroid() = %v, want %v", got, p)
  1564  	}
  1565  
  1566  	if got, want := northHemi.Area(), 2*math.Pi; !float64Eq(got, want) {
  1567  		t.Errorf("northHemi.Area() = %v, want %v", got, want)
  1568  	}
  1569  
  1570  	eastHemiArea := eastHemi.Area()
  1571  	if eastHemiArea < 2*math.Pi-1e-12 || eastHemiArea > 2*math.Pi+1e-12 {
  1572  		t.Errorf("eastHemi.Area() = %v, want between [%v, %v]", eastHemiArea, 2*math.Pi-1e-12, 2*math.Pi+1e-12)
  1573  	}
  1574  
  1575  	// Construct spherical caps of random height, and approximate their boundary
  1576  	// with closely spaces vertices. Then check that the area and centroid are
  1577  	// correct.
  1578  	for i := 0; i < 50; i++ {
  1579  		// Choose a coordinate frame for the spherical cap.
  1580  		f := randomFrame()
  1581  		x := f.col(0)
  1582  		y := f.col(1)
  1583  		z := f.col(2)
  1584  
  1585  		// Given two points at latitude phi and whose longitudes differ by dtheta,
  1586  		// the geodesic between the two points has a maximum latitude of
  1587  		// atan(tan(phi) / cos(dtheta/2)). This can be derived by positioning
  1588  		// the two points at (-dtheta/2, phi) and (dtheta/2, phi).
  1589  		//
  1590  		// We want to position the vertices close enough together so that their
  1591  		// maximum distance from the boundary of the spherical cap is maxDist.
  1592  		// Thus we want abs(atan(tan(phi) / cos(dtheta/2)) - phi) <= maxDist.
  1593  		const maxDist = 1e-6
  1594  		height := 2 * randomFloat64()
  1595  		phi := math.Asin(1.0 - height)
  1596  		maxDtheta := 2 * math.Acos(math.Tan(math.Abs(phi))/math.Tan(math.Abs(phi)+maxDist))
  1597  		maxDtheta = math.Min(math.Pi, maxDtheta)
  1598  
  1599  		var vertices []Point
  1600  		for theta := 0.0; theta < 2*math.Pi; theta += randomFloat64() * maxDtheta {
  1601  			vertices = append(vertices,
  1602  				Point{x.Mul(math.Cos(theta) * math.Cos(phi)).Add(
  1603  					y.Mul(math.Sin(theta) * math.Cos(phi))).Add(
  1604  					z.Mul(math.Sin(phi)))},
  1605  			)
  1606  		}
  1607  
  1608  		loop := LoopFromPoints(vertices)
  1609  		area := loop.Area()
  1610  		centroid := loop.Centroid()
  1611  		expectedArea := 2 * math.Pi * height
  1612  		if delta, want := math.Abs(area-expectedArea), 2*math.Pi*maxDist; delta > want {
  1613  			t.Errorf("%v.Area() = %v, want to be within %v of %v, got %v", loop, area, want, expectedArea, delta)
  1614  		}
  1615  		expectedCentroid := z.Mul(expectedArea * (1 - 0.5*height))
  1616  		if delta, want := centroid.Sub(expectedCentroid).Norm(), 2*maxDist; delta > want {
  1617  			t.Errorf("%v.Centroid() = %v, want to be within %v of %v, got %v", loop, centroid, want, expectedCentroid, delta)
  1618  		}
  1619  	}
  1620  }
  1621  
  1622  // TODO(roberts): Test that Area() has an accuracy significantly better
  1623  // than 1e-15 on loops whose area is small.
  1624  
  1625  func TestLoopAreaConsistentWithTurningAngle(t *testing.T) {
  1626  	// Check that the area computed using GetArea() is consistent with the
  1627  	// turning angle of the loop computed using GetTurnAngle().  According to
  1628  	// the Gauss-Bonnet theorem, the area of the loop should be equal to 2*Pi
  1629  	// minus its turning angle.
  1630  	for x, loop := range allLoops {
  1631  		area := loop.Area()
  1632  		gaussArea := 2*math.Pi - loop.TurningAngle()
  1633  
  1634  		// TODO(roberts): The error bound below is much larger than it should be.
  1635  		if math.Abs(area-gaussArea) > 1e-9 {
  1636  			t.Errorf("%d. %v.Area() = %v want %v", x, loop, area, gaussArea)
  1637  		}
  1638  	}
  1639  }
  1640  
  1641  func TestLoopGetAreaConsistentWithSign(t *testing.T) {
  1642  	// TODO(roberts): Uncomment when Loop has Validate
  1643  	/*
  1644  		// Test that Area() returns an area near 0 for degenerate loops that
  1645  		// contain almost no points, and an area near 4*pi for degenerate loops that
  1646  		// contain almost all points.
  1647  		const maxVertices = 6
  1648  
  1649  		for i := 0; i < 50; i++ {
  1650  			numVertices := 3 + randomUniformInt(maxVertices-3+1)
  1651  			// Repeatedly choose N vertices that are exactly on the equator until we
  1652  			// find some that form a valid loop.
  1653  			var loop = Loop{}
  1654  			for !loop.Validate() {
  1655  				var vertices []Point
  1656  				for i := 0; i < numVertices; i++ {
  1657  					// We limit longitude to the range [0, 90] to ensure that the loop is
  1658  					// degenerate (as opposed to following the entire equator).
  1659  					vertices = append(vertices,
  1660  						PointFromLatLng(LatLng{0, s1.Angle(randomFloat64()) * math.Pi / 2}))
  1661  				}
  1662  				loop.vertices = vertices
  1663  				break
  1664  			}
  1665  
  1666  			ccw := loop.IsNormalized()
  1667  			want := 0.0
  1668  			if !ccw {
  1669  				want = 4 * math.Pi
  1670  			}
  1671  
  1672  			// TODO(roberts): The error bound below is much larger than it should be.
  1673  			if got := loop.Area(); !float64Near(got, want, 1e-8) {
  1674  				t.Errorf("%v.Area() = %v, want %v", loop, got, want)
  1675  			}
  1676  			p := PointFromCoords(0, 0, 1)
  1677  			if got := loop.ContainsPoint(p); got != !ccw {
  1678  				t.Errorf("%v.ContainsPoint(%v) = %v, want %v", got, p, !ccw)
  1679  			}
  1680  		}
  1681  	*/
  1682  }
  1683  
  1684  func TestLoopNormalizedCompatibleWithContains(t *testing.T) {
  1685  	p := parsePoint("40:40")
  1686  
  1687  	tests := []*Loop{
  1688  		lineTriangle,
  1689  		skinnyChevron,
  1690  	}
  1691  
  1692  	// Checks that if a loop is normalized, it doesn't contain a
  1693  	// point outside of it, and vice versa.
  1694  	for _, loop := range tests {
  1695  		flip := cloneLoop(loop)
  1696  
  1697  		flip.Invert()
  1698  		if norm, contains := loop.IsNormalized(), loop.ContainsPoint(p); norm == contains {
  1699  			t.Errorf("loop.IsNormalized() = %t == loop.ContainsPoint(%v) = %v, want !=", norm, p, contains)
  1700  		}
  1701  		if norm, contains := flip.IsNormalized(), flip.ContainsPoint(p); norm == contains {
  1702  			t.Errorf("flip.IsNormalized() = %t == flip.ContainsPoint(%v) = %v, want !=", norm, p, contains)
  1703  		}
  1704  		if a, b := loop.IsNormalized(), flip.IsNormalized(); a == b {
  1705  			t.Errorf("a loop and it's invert can not both be normalized")
  1706  		}
  1707  		flip.Normalize()
  1708  		if flip.ContainsPoint(p) {
  1709  			t.Errorf("%v.ContainsPoint(%v) = true, want false", flip, p)
  1710  		}
  1711  	}
  1712  }
  1713  
  1714  func TestLoopValidateDetectsInvalidLoops(t *testing.T) {
  1715  	tests := []struct {
  1716  		msg    string
  1717  		points []Point
  1718  	}{
  1719  		// Not enough vertices. Note that all single-vertex loops are valid; they
  1720  		// are interpreted as being either "empty" or "full".
  1721  		{
  1722  			msg:    "loop has no vertices",
  1723  			points: parsePoints(""),
  1724  		},
  1725  		{
  1726  			msg:    "loop has too few vertices",
  1727  			points: parsePoints("20:20, 21:21"),
  1728  		},
  1729  		// degenerate edge checks happen in validation before duplicate vertices.
  1730  		{
  1731  			msg:    "loop has degenerate first edge",
  1732  			points: parsePoints("20:20, 20:20, 20:21"),
  1733  		},
  1734  		{
  1735  			msg:    "loop has degenerate third edge",
  1736  			points: parsePoints("20:20, 20:21, 20:20"),
  1737  		},
  1738  		// TODO(roberts): Uncomment these cases when FindAnyCrossings is in.
  1739  		/*
  1740  			{
  1741  				msg:    "loop has duplicate points",
  1742  				points: parsePoints("20:20, 21:21, 21:20, 20:20, 20:21"),
  1743  			},
  1744  			{
  1745  				msg:    "loop has crossing edges",
  1746  				points: parsePoints("20:20, 21:21, 21:20.5, 21:20, 20:21"),
  1747  			},
  1748  		*/
  1749  		{
  1750  			// Ensure points are not normalized.
  1751  			msg: "loop with non-normalized vertices",
  1752  			points: []Point{
  1753  				{r3.Vector{2, 0, 0}},
  1754  				{r3.Vector{0, 1, 0}},
  1755  				{r3.Vector{0, 0, 1}},
  1756  			},
  1757  		},
  1758  		{
  1759  			// Adjacent antipodal vertices
  1760  			msg: "loop with antipodal points",
  1761  			points: []Point{
  1762  				{r3.Vector{1, 0, 0}},
  1763  				{r3.Vector{-1, 0, 0}},
  1764  				{r3.Vector{0, 0, 1}},
  1765  			},
  1766  		},
  1767  	}
  1768  
  1769  	for _, test := range tests {
  1770  		loop := LoopFromPoints(test.points)
  1771  		if err := loop.Validate(); err == nil {
  1772  			t.Errorf("%s. %v.Validate() = %v, want nil", test.msg, loop, err)
  1773  		}
  1774  		// The C++ tests also tests that the returned error message string contains
  1775  		// a specific set of text. That part of the test is skipped here.
  1776  	}
  1777  }
  1778  
  1779  const (
  1780  	// TODO(roberts): Convert these into changeable flags or parameters.
  1781  	// A loop with a 10km radius and 4096 vertices has an edge length of 15 meters.
  1782  	defaultRadiusKm   = 10.0
  1783  	numLoopSamples    = 16
  1784  	numQueriesPerLoop = 100
  1785  )
  1786  
  1787  func BenchmarkLoopContainsPoint(b *testing.B) {
  1788  	// Benchmark ContainsPoint() on regular loops. The query points for a loop are
  1789  	// chosen so that they all lie in the loop's bounding rectangle (to avoid the
  1790  	// quick-rejection code path).
  1791  
  1792  	// C++ ranges from 4 -> 256k by powers of 2 for number of vertices for benchmarking.
  1793  	vertices := 4
  1794  	for n := 1; n <= 17; n++ {
  1795  		b.Run(fmt.Sprintf("%d", vertices),
  1796  			func(b *testing.B) {
  1797  				b.StopTimer()
  1798  				loops := make([]*Loop, numLoopSamples)
  1799  				for i := 0; i < numLoopSamples; i++ {
  1800  					loops[i] = RegularLoop(randomPoint(), kmToAngle(10.0), vertices)
  1801  				}
  1802  
  1803  				queries := make([][]Point, numLoopSamples)
  1804  
  1805  				for i, loop := range loops {
  1806  					queries[i] = make([]Point, numQueriesPerLoop)
  1807  					for j := 0; j < numQueriesPerLoop; j++ {
  1808  						queries[i][j] = samplePointFromRect(loop.RectBound())
  1809  					}
  1810  				}
  1811  
  1812  				b.StartTimer()
  1813  				for i := 0; i < b.N; i++ {
  1814  					loops[i%numLoopSamples].ContainsPoint(queries[i%numLoopSamples][i%numQueriesPerLoop])
  1815  				}
  1816  			})
  1817  		vertices *= 2
  1818  	}
  1819  }
  1820  

View as plain text