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

Documentation: github.com/golang/geo/s2

     1  // Copyright 2014 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  	"math"
    19  	"reflect"
    20  	"testing"
    21  
    22  	"github.com/golang/geo/r2"
    23  	"github.com/golang/geo/s1"
    24  )
    25  
    26  func TestCellIDFromFace(t *testing.T) {
    27  	for face := 0; face < 6; face++ {
    28  		fpl := CellIDFromFacePosLevel(face, 0, 0)
    29  		f := CellIDFromFace(face)
    30  		if fpl != f {
    31  			t.Errorf("CellIDFromFacePosLevel(%d, 0, 0) != CellIDFromFace(%d), got %v wanted %v", face, face, f, fpl)
    32  		}
    33  	}
    34  }
    35  
    36  func TestCellIDSentinelRangeMinMax(t *testing.T) {
    37  	s := SentinelCellID
    38  	if got := s.RangeMin(); s != got {
    39  		t.Errorf("sentinel.RangeMin() = %v, want %v", got, s)
    40  	}
    41  	if got := s.RangeMax(); s != got {
    42  		t.Errorf("sentinel.RangeMax() = %v, want %v", got, s)
    43  	}
    44  }
    45  
    46  func TestCellIDParentChildRelationships(t *testing.T) {
    47  	ci := CellIDFromFacePosLevel(3, 0x12345678, MaxLevel-4)
    48  
    49  	if !ci.IsValid() {
    50  		t.Errorf("CellID %v should be valid", ci)
    51  	}
    52  	if f := ci.Face(); f != 3 {
    53  		t.Errorf("ci.Face() is %v, want 3", f)
    54  	}
    55  	if p := ci.Pos(); p != 0x12345700 {
    56  		t.Errorf("ci.Pos() is 0x%X, want 0x12345700", p)
    57  	}
    58  	if l := ci.Level(); l != 26 { // 26 is MaxLevel - 4
    59  		t.Errorf("ci.Level() is %v, want 26", l)
    60  	}
    61  	if ci.IsLeaf() {
    62  		t.Errorf("CellID %v should not be a leaf", ci)
    63  	}
    64  
    65  	if kid2 := ci.ChildBeginAtLevel(ci.Level() + 2).Pos(); kid2 != 0x12345610 {
    66  		t.Errorf("child two levels down is 0x%X, want 0x12345610", kid2)
    67  	}
    68  	if kid0 := ci.ChildBegin().Pos(); kid0 != 0x12345640 {
    69  		t.Errorf("first child is 0x%X, want 0x12345640", kid0)
    70  	}
    71  	if kid0 := ci.Children()[0].Pos(); kid0 != 0x12345640 {
    72  		t.Errorf("first child is 0x%X, want 0x12345640", kid0)
    73  	}
    74  	if parent := ci.immediateParent().Pos(); parent != 0x12345400 {
    75  		t.Errorf("ci.immediateParent().Pos() = 0x%X, want 0x12345400", parent)
    76  	}
    77  	if parent := ci.Parent(ci.Level() - 2).Pos(); parent != 0x12345000 {
    78  		t.Errorf("ci.Parent(l-2).Pos() = 0x%X, want 0x12345000", parent)
    79  	}
    80  
    81  	if uint64(ci.ChildBegin()) >= uint64(ci) {
    82  		t.Errorf("ci.ChildBegin() is 0x%X, want < 0x%X", ci.ChildBegin(), ci)
    83  	}
    84  	if uint64(ci.ChildEnd()) <= uint64(ci) {
    85  		t.Errorf("ci.ChildEnd() is 0x%X, want > 0x%X", ci.ChildEnd(), ci)
    86  	}
    87  	if ci.ChildEnd() != ci.ChildBegin().Next().Next().Next().Next() {
    88  		t.Errorf("ci.ChildEnd() is 0x%X, want 0x%X", ci.ChildEnd(), ci.ChildBegin().Next().Next().Next().Next())
    89  	}
    90  	if ci.RangeMin() != ci.ChildBeginAtLevel(MaxLevel) {
    91  		t.Errorf("ci.RangeMin() is 0x%X, want 0x%X", ci.RangeMin(), ci.ChildBeginAtLevel(MaxLevel))
    92  	}
    93  	if ci.RangeMax().Next() != ci.ChildEndAtLevel(MaxLevel) {
    94  		t.Errorf("ci.RangeMax().Next() is 0x%X, want 0x%X", ci.RangeMax().Next(), ci.ChildEndAtLevel(MaxLevel))
    95  	}
    96  }
    97  
    98  func TestCellIDContainment(t *testing.T) {
    99  	a := CellID(0x80855c0000000000) // Pittsburg
   100  	b := CellID(0x80855d0000000000) // child of a
   101  	c := CellID(0x80855dc000000000) // child of b
   102  	d := CellID(0x8085630000000000) // part of Pittsburg disjoint from a
   103  	tests := []struct {
   104  		x, y                                 CellID
   105  		xContainsY, yContainsX, xIntersectsY bool
   106  	}{
   107  		{a, a, true, true, true},
   108  		{a, b, true, false, true},
   109  		{a, c, true, false, true},
   110  		{a, d, false, false, false},
   111  		{b, b, true, true, true},
   112  		{b, c, true, false, true},
   113  		{b, d, false, false, false},
   114  		{c, c, true, true, true},
   115  		{c, d, false, false, false},
   116  		{d, d, true, true, true},
   117  	}
   118  	should := func(b bool) string {
   119  		if b {
   120  			return "should"
   121  		}
   122  		return "should not"
   123  	}
   124  	for _, test := range tests {
   125  		if test.x.Contains(test.y) != test.xContainsY {
   126  			t.Errorf("%v %s contain %v", test.x, should(test.xContainsY), test.y)
   127  		}
   128  		if test.x.Intersects(test.y) != test.xIntersectsY {
   129  			t.Errorf("%v %s intersect %v", test.x, should(test.xIntersectsY), test.y)
   130  		}
   131  		if test.y.Contains(test.x) != test.yContainsX {
   132  			t.Errorf("%v %s contain %v", test.y, should(test.yContainsX), test.x)
   133  		}
   134  	}
   135  
   136  	// TODO(dsymonds): Test Contains, Intersects better, such as with adjacent cells.
   137  }
   138  
   139  func TestCellIDString(t *testing.T) {
   140  	ci := CellID(0xbb04000000000000)
   141  	if s, exp := ci.String(), "5/31200"; s != exp {
   142  		t.Errorf("ci.String() = %q, want %q", s, exp)
   143  	}
   144  }
   145  
   146  func TestCellIDFromString(t *testing.T) {
   147  	tests := []struct {
   148  		have string
   149  		want CellID
   150  	}{
   151  		{have: "3/", want: CellIDFromFace(3)},
   152  		{have: "0/21", want: CellIDFromFace(0).Children()[2].Children()[1]},
   153  		{have: "4/000000000000000000000000000000", want: CellIDFromFace(4).RangeMin()},
   154  		{have: "4/0000000000000000000000000000000", want: 0},
   155  		{have: "", want: 0},
   156  		{have: "7/", want: 0},
   157  		{have: " /", want: 0},
   158  		{have: "3:0", want: 0},
   159  		{have: "3/ 12", want: 0},
   160  		{have: "3/1241", want: 0},
   161  	}
   162  
   163  	for _, test := range tests {
   164  		if got := CellIDFromString(test.have); got != test.want {
   165  			t.Errorf("CellIDFromString(%q) = %v, want %v", test.have, got, test.want)
   166  		}
   167  	}
   168  }
   169  
   170  func TestCellIDLatLng(t *testing.T) {
   171  	// You can generate these with the s2cellid2latlngtestcase C++ program in this directory.
   172  	tests := []struct {
   173  		id       CellID
   174  		lat, lng float64
   175  	}{
   176  		{0x47a1cbd595522b39, 49.703498679, 11.770681595},
   177  		{0x46525318b63be0f9, 55.685376759, 12.588490937},
   178  		{0x52b30b71698e729d, 45.486546517, -93.449700022},
   179  		{0x46ed8886cfadda85, 58.299984854, 23.049300056},
   180  		{0x3663f18a24cbe857, 34.364439040, 108.330699969},
   181  		{0x10a06c0a948cf5d, -30.694551352, -30.048758753},
   182  		{0x2b2bfd076787c5df, -25.285264027, 133.823116966},
   183  		{0xb09dff882a7809e1, -75.000000031, 0.000000133},
   184  		{0x94daa3d000000001, -24.694439215, -47.537363213},
   185  		{0x87a1000000000001, 38.899730392, -99.901813021},
   186  		{0x4fc76d5000000001, 81.647200334, -55.631712940},
   187  		{0x3b00955555555555, 10.050986518, 78.293170610},
   188  		{0x1dcc469991555555, -34.055420593, 18.551140038},
   189  		{0xb112966aaaaaaaab, -69.219262171, 49.670072392},
   190  	}
   191  	for _, test := range tests {
   192  		l1 := LatLngFromDegrees(test.lat, test.lng)
   193  		l2 := test.id.LatLng()
   194  		if l1.Distance(l2) > 1e-9*s1.Degree { // ~0.1mm on earth.
   195  			t.Errorf("LatLng() for CellID %x (%s) : got %s, want %s", uint64(test.id), test.id, l2, l1)
   196  		}
   197  		c1 := test.id
   198  		c2 := CellIDFromLatLng(l1)
   199  		if c1 != c2 {
   200  			t.Errorf("CellIDFromLatLng(%s) = %x (%s), want %s", l1, uint64(c2), c2, c1)
   201  		}
   202  	}
   203  }
   204  
   205  func TestCellIDEdgeNeighbors(t *testing.T) {
   206  	// Check the edge neighbors of face 1.
   207  	faces := []int{5, 3, 2, 0}
   208  	for i, nbr := range cellIDFromFaceIJ(1, 0, 0).Parent(0).EdgeNeighbors() {
   209  		if !nbr.isFace() {
   210  			t.Errorf("CellID(%d) is not a face", nbr)
   211  		}
   212  		if got, want := nbr.Face(), faces[i]; got != want {
   213  			t.Errorf("CellID(%d).Face() = %d, want %d", nbr, got, want)
   214  		}
   215  	}
   216  	// Check the edge neighbors of the corner cells at all levels.  This case is
   217  	// trickier because it requires projecting onto adjacent faces.
   218  	const maxIJ = MaxSize - 1
   219  	for level := 1; level <= MaxLevel; level++ {
   220  		id := cellIDFromFaceIJ(1, 0, 0).Parent(level)
   221  		// These neighbors were determined manually using the face and axis
   222  		// relationships.
   223  		levelSizeIJ := sizeIJ(level)
   224  		want := []CellID{
   225  			cellIDFromFaceIJ(5, maxIJ, maxIJ).Parent(level),
   226  			cellIDFromFaceIJ(1, levelSizeIJ, 0).Parent(level),
   227  			cellIDFromFaceIJ(1, 0, levelSizeIJ).Parent(level),
   228  			cellIDFromFaceIJ(0, maxIJ, 0).Parent(level),
   229  		}
   230  		for i, nbr := range id.EdgeNeighbors() {
   231  			if nbr != want[i] {
   232  				t.Errorf("CellID(%d).EdgeNeighbors()[%d] = %v, want %v", id, i, nbr, want[i])
   233  			}
   234  		}
   235  	}
   236  }
   237  
   238  func TestCellIDVertexNeighbors(t *testing.T) {
   239  	// Check the vertex neighbors of the center of face 2 at level 5.
   240  	id := cellIDFromPoint(PointFromCoords(0, 0, 1))
   241  	neighbors := id.VertexNeighbors(5)
   242  	sortCellIDs(neighbors)
   243  
   244  	for n, nbr := range neighbors {
   245  		i, j := 1<<29, 1<<29
   246  		if n < 2 {
   247  			i--
   248  		}
   249  		if n == 0 || n == 3 {
   250  			j--
   251  		}
   252  		want := cellIDFromFaceIJ(2, i, j).Parent(5)
   253  
   254  		if nbr != want {
   255  			t.Errorf("CellID(%s).VertexNeighbors()[%d] = %v, want %v", id, n, nbr, want)
   256  		}
   257  	}
   258  
   259  	// Check the vertex neighbors of the corner of faces 0, 4, and 5.
   260  	id = CellIDFromFacePosLevel(0, 0, MaxLevel)
   261  	neighbors = id.VertexNeighbors(0)
   262  	sortCellIDs(neighbors)
   263  	if len(neighbors) != 3 {
   264  		t.Errorf("len(CellID(%d).VertexNeighbors()) = %d, wanted %d", id, len(neighbors), 3)
   265  	}
   266  	if neighbors[0] != CellIDFromFace(0) {
   267  		t.Errorf("CellID(%d).VertexNeighbors()[0] = %d, wanted %d", id, neighbors[0], CellIDFromFace(0))
   268  	}
   269  	if neighbors[1] != CellIDFromFace(4) {
   270  		t.Errorf("CellID(%d).VertexNeighbors()[1] = %d, wanted %d", id, neighbors[1], CellIDFromFace(4))
   271  	}
   272  }
   273  
   274  // dedupCellIDs returns the unique slice of CellIDs from the sorted input list.
   275  func dedupCellIDs(ids []CellID) []CellID {
   276  	var out []CellID
   277  	var prev CellID
   278  	for _, id := range ids {
   279  		if id != prev {
   280  			out = append(out, id)
   281  		}
   282  		prev = id
   283  	}
   284  
   285  	return out
   286  }
   287  
   288  func TestCellIDAllNeighbors(t *testing.T) {
   289  	// Check that AllNeighbors produces results that are consistent
   290  	// with VertexNeighbors for a bunch of random cells.
   291  	for i := 0; i < 1000; i++ {
   292  		id := randomCellID()
   293  		if id.IsLeaf() {
   294  			id = id.immediateParent()
   295  		}
   296  
   297  		// testAllNeighbors computes approximately 2**(2*(diff+1)) cell ids,
   298  		// so it's not reasonable to use large values of diff.
   299  		maxDiff := minInt(6, MaxLevel-id.Level()-1)
   300  		level := id.Level() + randomUniformInt(maxDiff)
   301  
   302  		// We compute AllNeighbors, and then add in all the children of id
   303  		// at the given level. We then compare this against the result of finding
   304  		// all the vertex neighbors of all the vertices of children of id at the
   305  		// given level. These should give the same result.
   306  		var want []CellID
   307  		all := id.AllNeighbors(level)
   308  		end := id.ChildEndAtLevel(level + 1)
   309  		for c := id.ChildBeginAtLevel(level + 1); c != end; c = c.Next() {
   310  			all = append(all, c.immediateParent())
   311  			want = append(want, c.VertexNeighbors(level)...)
   312  		}
   313  
   314  		// Sort the results and eliminate duplicates.
   315  		sortCellIDs(all)
   316  		sortCellIDs(want)
   317  		all = dedupCellIDs(all)
   318  		want = dedupCellIDs(want)
   319  
   320  		if !reflect.DeepEqual(all, want) {
   321  			t.Errorf("%v.AllNeighbors(%d) = %v, want %v", id, level, all, want)
   322  		}
   323  	}
   324  }
   325  
   326  func TestCellIDTokensNominal(t *testing.T) {
   327  	tests := []struct {
   328  		token string
   329  		id    CellID
   330  	}{
   331  		{"1", 0x1000000000000000},
   332  		{"3", 0x3000000000000000},
   333  		{"14", 0x1400000000000000},
   334  		{"41", 0x4100000000000000},
   335  		{"094", 0x0940000000000000},
   336  		{"537", 0x5370000000000000},
   337  		{"3fec", 0x3fec000000000000},
   338  		{"72f3", 0x72f3000000000000},
   339  		{"52b8c", 0x52b8c00000000000},
   340  		{"990ed", 0x990ed00000000000},
   341  		{"4476dc", 0x4476dc0000000000},
   342  		{"2a724f", 0x2a724f0000000000},
   343  		{"7d4afc4", 0x7d4afc4000000000},
   344  		{"b675785", 0xb675785000000000},
   345  		{"40cd6124", 0x40cd612400000000},
   346  		{"3ba32f81", 0x3ba32f8100000000},
   347  		{"08f569b5c", 0x08f569b5c0000000},
   348  		{"385327157", 0x3853271570000000},
   349  		{"166c4d1954", 0x166c4d1954000000},
   350  		{"96f48d8c39", 0x96f48d8c39000000},
   351  		{"0bca3c7f74c", 0x0bca3c7f74c00000},
   352  		{"1ae3619d12f", 0x1ae3619d12f00000},
   353  		{"07a77802a3fc", 0x07a77802a3fc0000},
   354  		{"4e7887ec1801", 0x4e7887ec18010000},
   355  		{"4adad7ae74124", 0x4adad7ae74124000},
   356  		{"90aba04afe0c5", 0x90aba04afe0c5000},
   357  		{"8ffc3f02af305c", 0x8ffc3f02af305c00},
   358  		{"6fa47550938183", 0x6fa4755093818300},
   359  		{"aa80a565df5e7fc", 0xaa80a565df5e7fc0},
   360  		{"01614b5e968e121", 0x01614b5e968e1210},
   361  		{"aa05238e7bd3ee7c", 0xaa05238e7bd3ee7c},
   362  		{"48a23db9c2963e5b", 0x48a23db9c2963e5b},
   363  	}
   364  	for _, test := range tests {
   365  		ci := CellIDFromToken(test.token)
   366  		if ci != test.id {
   367  			t.Errorf("CellIDFromToken(%q) = %x, want %x", test.token, uint64(ci), uint64(test.id))
   368  		}
   369  
   370  		token := ci.ToToken()
   371  		if token != test.token {
   372  			t.Errorf("ci.ToToken = %q, want %q", token, test.token)
   373  		}
   374  	}
   375  }
   376  
   377  func TestCellIDFromTokensErrorCases(t *testing.T) {
   378  	noneToken := CellID(0).ToToken()
   379  	if noneToken != "X" {
   380  		t.Errorf("CellID(0).Token() = %q, want X", noneToken)
   381  	}
   382  	noneID := CellIDFromToken(noneToken)
   383  	if noneID != CellID(0) {
   384  		t.Errorf("CellIDFromToken(%q) = %x, want 0", noneToken, uint64(noneID))
   385  	}
   386  
   387  	// Sentinel is invalid.
   388  	sentinel := SentinelCellID.ToToken()
   389  	if got, want := CellIDFromToken(sentinel), SentinelCellID; got != want {
   390  		t.Errorf("CellIDFromToken(%v) = %v, want %v", sentinel, got, want)
   391  	}
   392  
   393  	// Check an invalid face.
   394  	face7 := CellIDFromFace(7).ToToken()
   395  	if got, want := CellIDFromToken(face7), CellIDFromFace(7); got != want {
   396  		t.Errorf("CellIDFromToken(%v) = %v, want %v", face7, got, want)
   397  	}
   398  
   399  	tests := []string{
   400  		"876b e99",
   401  		"876bee99\n",
   402  		"876[ee99",
   403  		" 876bee99",
   404  	}
   405  	for _, test := range tests {
   406  		ci := CellIDFromToken(test)
   407  		if uint64(ci) != 0 {
   408  			t.Errorf("CellIDFromToken(%q) = %x, want 0", test, uint64(ci))
   409  		}
   410  	}
   411  }
   412  
   413  func TestIJLevelToBoundUV(t *testing.T) {
   414  	maxIJ := 1<<MaxLevel - 1
   415  
   416  	tests := []struct {
   417  		i     int
   418  		j     int
   419  		level int
   420  		want  r2.Rect
   421  	}{
   422  		// The i/j space is [0, 2^30 - 1) which maps to [-1, 1] for the
   423  		// x/y axes of the face surface. Results are scaled by the size of a cell
   424  		// at the given level. At level 0, everything is one cell of the full size
   425  		// of the space.  At MaxLevel, the bounding rect is almost floating point
   426  		// noise.
   427  
   428  		// What should be out of bounds values, but passes the C++ code as well.
   429  		{
   430  			-1, -1, 0,
   431  			r2.RectFromPoints(r2.Point{-5, -5}, r2.Point{-1, -1}),
   432  		},
   433  		{
   434  			-1 * maxIJ, -1 * maxIJ, 0,
   435  			r2.RectFromPoints(r2.Point{-5, -5}, r2.Point{-1, -1}),
   436  		},
   437  		{
   438  			-1, -1, MaxLevel,
   439  			r2.RectFromPoints(r2.Point{-1.0000000024835267, -1.0000000024835267},
   440  				r2.Point{-1, -1}),
   441  		},
   442  		{
   443  			0, 0, MaxLevel + 1,
   444  			r2.RectFromPoints(r2.Point{-1, -1}, r2.Point{-1, -1}),
   445  		},
   446  
   447  		// Minimum i,j at different levels
   448  		{
   449  			0, 0, 0,
   450  			r2.RectFromPoints(r2.Point{-1, -1}, r2.Point{1, 1}),
   451  		},
   452  		{
   453  			0, 0, MaxLevel / 2,
   454  			r2.RectFromPoints(r2.Point{-1, -1},
   455  				r2.Point{-0.999918621033430099, -0.999918621033430099}),
   456  		},
   457  		{
   458  			0, 0, MaxLevel,
   459  			r2.RectFromPoints(r2.Point{-1, -1},
   460  				r2.Point{-0.999999997516473060, -0.999999997516473060}),
   461  		},
   462  
   463  		// Just a hair off the outer bounds at different levels.
   464  		{
   465  			1, 1, 0,
   466  			r2.RectFromPoints(r2.Point{-1, -1}, r2.Point{1, 1}),
   467  		},
   468  		{
   469  			1, 1, MaxLevel / 2,
   470  			r2.RectFromPoints(r2.Point{-1, -1},
   471  				r2.Point{-0.999918621033430099, -0.999918621033430099}),
   472  		},
   473  		{
   474  			1, 1, MaxLevel,
   475  			r2.RectFromPoints(r2.Point{-0.9999999975164731, -0.9999999975164731},
   476  				r2.Point{-0.9999999950329462, -0.9999999950329462}),
   477  		},
   478  
   479  		// Center point of the i,j space at different levels.
   480  		{
   481  			maxIJ / 2, maxIJ / 2, 0,
   482  			r2.RectFromPoints(r2.Point{-1, -1}, r2.Point{1, 1})},
   483  		{
   484  			maxIJ / 2, maxIJ / 2, MaxLevel / 2,
   485  			r2.RectFromPoints(r2.Point{-0.000040691345930099, -0.000040691345930099},
   486  				r2.Point{0, 0})},
   487  		{
   488  			maxIJ / 2, maxIJ / 2, MaxLevel,
   489  			r2.RectFromPoints(r2.Point{-0.000000001241763433, -0.000000001241763433},
   490  				r2.Point{0, 0})},
   491  
   492  		// Maximum i, j at different levels.
   493  		{
   494  			maxIJ, maxIJ, 0,
   495  			r2.RectFromPoints(r2.Point{-1, -1}, r2.Point{1, 1}),
   496  		},
   497  		{
   498  			maxIJ, maxIJ, MaxLevel / 2,
   499  			r2.RectFromPoints(r2.Point{0.999918621033430099, 0.999918621033430099},
   500  				r2.Point{1, 1}),
   501  		},
   502  		{
   503  			maxIJ, maxIJ, MaxLevel,
   504  			r2.RectFromPoints(r2.Point{0.999999997516473060, 0.999999997516473060},
   505  				r2.Point{1, 1}),
   506  		},
   507  	}
   508  
   509  	for _, test := range tests {
   510  		uv := ijLevelToBoundUV(test.i, test.j, test.level)
   511  		if !float64Eq(uv.X.Lo, test.want.X.Lo) ||
   512  			!float64Eq(uv.X.Hi, test.want.X.Hi) ||
   513  			!float64Eq(uv.Y.Lo, test.want.Y.Lo) ||
   514  			!float64Eq(uv.Y.Hi, test.want.Y.Hi) {
   515  			t.Errorf("ijLevelToBoundUV(%d, %d, %d), got %v, want %v",
   516  				test.i, test.j, test.level, uv, test.want)
   517  		}
   518  	}
   519  }
   520  
   521  func TestCellIDCommonAncestorLevel(t *testing.T) {
   522  	tests := []struct {
   523  		ci     CellID
   524  		other  CellID
   525  		want   int
   526  		wantOk bool
   527  	}{
   528  		// Identical cell IDs.
   529  		{
   530  			CellIDFromFace(0),
   531  			CellIDFromFace(0),
   532  			0,
   533  			true,
   534  		},
   535  		{
   536  			CellIDFromFace(0).ChildBeginAtLevel(30),
   537  			CellIDFromFace(0).ChildBeginAtLevel(30),
   538  			30,
   539  			true,
   540  		},
   541  		// One cell is a descendant of the other.
   542  		{
   543  			CellIDFromFace(0).ChildBeginAtLevel(30),
   544  			CellIDFromFace(0),
   545  			0,
   546  			true,
   547  		},
   548  		{
   549  			CellIDFromFace(5),
   550  			CellIDFromFace(5).ChildEndAtLevel(30).Prev(),
   551  			0,
   552  			true,
   553  		},
   554  		// No common ancestors.
   555  		{
   556  			CellIDFromFace(0),
   557  			CellIDFromFace(5),
   558  			0,
   559  			false,
   560  		},
   561  		{
   562  			CellIDFromFace(2).ChildBeginAtLevel(30),
   563  			CellIDFromFace(3).ChildBeginAtLevel(20),
   564  			0,
   565  			false,
   566  		},
   567  		// Common ancestor distinct from both.
   568  		{
   569  			CellIDFromFace(5).ChildBeginAtLevel(9).Next().ChildBeginAtLevel(15),
   570  			CellIDFromFace(5).ChildBeginAtLevel(9).ChildBeginAtLevel(20),
   571  			8,
   572  			true,
   573  		},
   574  		{
   575  			CellIDFromFace(0).ChildBeginAtLevel(2).ChildBeginAtLevel(30),
   576  			CellIDFromFace(0).ChildBeginAtLevel(2).Next().ChildBeginAtLevel(5),
   577  			1,
   578  			true,
   579  		},
   580  	}
   581  	for _, test := range tests {
   582  		if got, ok := test.ci.CommonAncestorLevel(test.other); ok != test.wantOk || got != test.want {
   583  			t.Errorf("CellID(%v).CommonAncestorLevel(%v) = %d, %t; want %d, %t", test.ci, test.other, got, ok, test.want, test.wantOk)
   584  		}
   585  	}
   586  }
   587  
   588  func TestCellIDDistanceToBegin(t *testing.T) {
   589  	tests := []struct {
   590  		id   CellID
   591  		want int64
   592  	}{
   593  		{
   594  			// at level 0 (i.e. full faces), there are only 6 cells from
   595  			// the last face to the beginning of the Hilbert curve.
   596  			id:   CellIDFromFace(5).ChildEndAtLevel(0),
   597  			want: 6,
   598  		},
   599  		{
   600  			// from the last cell on the last face at the smallest cell size,
   601  			// there are the maximum number of possible cells.
   602  			id:   CellIDFromFace(5).ChildEndAtLevel(MaxLevel),
   603  			want: 6 * (1 << uint(2*MaxLevel)),
   604  		},
   605  		{
   606  			// from the first cell on the first face.
   607  			id:   CellIDFromFace(0).ChildBeginAtLevel(0),
   608  			want: 0,
   609  		},
   610  		{
   611  			// from the first cell at the smallest level on the first face.
   612  			id:   CellIDFromFace(0).ChildBeginAtLevel(MaxLevel),
   613  			want: 0,
   614  		},
   615  	}
   616  
   617  	for _, test := range tests {
   618  		if got := test.id.distanceFromBegin(); got != test.want {
   619  			t.Errorf("%v.distanceToBegin() = %v, want %v", test.id, got, test.want)
   620  		}
   621  	}
   622  
   623  	// Test that advancing from the beginning by the distance from a cell gets
   624  	// us back to that cell.
   625  	id := CellIDFromFacePosLevel(3, 0x12345678, MaxLevel-4)
   626  	if got := CellIDFromFace(0).ChildBeginAtLevel(id.Level()).Advance(id.distanceFromBegin()); got != id {
   627  		t.Errorf("advancing from the beginning by the distance of a cell should return us to that cell. got %v, want %v", got, id)
   628  	}
   629  }
   630  
   631  func TestCellIDWrapping(t *testing.T) {
   632  	id := CellIDFromFacePosLevel(3, 0x12345678, MaxLevel-4)
   633  
   634  	tests := []struct {
   635  		msg  string
   636  		got  CellID
   637  		want CellID
   638  	}{
   639  		{
   640  			"test wrap from beginning to end of Hilbert curve",
   641  			CellIDFromFace(5).ChildEndAtLevel(0).Prev(),
   642  			CellIDFromFace(0).ChildBeginAtLevel(0).PrevWrap(),
   643  		},
   644  		{
   645  			"smallest end leaf wraps to smallest first leaf using PrevWrap",
   646  			CellIDFromFacePosLevel(5, ^uint64(0)>>FaceBits, MaxLevel),
   647  			CellIDFromFace(0).ChildBeginAtLevel(MaxLevel).PrevWrap(),
   648  		},
   649  		{
   650  			"smallest end leaf wraps to smallest first leaf using AdvanceWrap",
   651  			CellIDFromFacePosLevel(5, ^uint64(0)>>FaceBits, MaxLevel),
   652  			CellIDFromFace(0).ChildBeginAtLevel(MaxLevel).AdvanceWrap(-1),
   653  		},
   654  		{
   655  			"PrevWrap is the same as AdvanceWrap(-1)",
   656  			CellIDFromFace(0).ChildBeginAtLevel(MaxLevel).AdvanceWrap(-1),
   657  			CellIDFromFace(0).ChildBeginAtLevel(MaxLevel).PrevWrap(),
   658  		},
   659  		{
   660  			"Prev + NextWrap stays the same at given level",
   661  			CellIDFromFace(0).ChildBeginAtLevel(4),
   662  			CellIDFromFace(5).ChildEndAtLevel(4).Prev().NextWrap(),
   663  		},
   664  		{
   665  			"AdvanceWrap forward and back stays the same at given level",
   666  			CellIDFromFace(0).ChildBeginAtLevel(4),
   667  			CellIDFromFace(5).ChildEndAtLevel(4).Advance(-1).AdvanceWrap(1),
   668  		},
   669  		{
   670  			"Prev().NextWrap() stays same for first cell at level",
   671  			CellIDFromFacePosLevel(0, 0, MaxLevel),
   672  			CellIDFromFace(5).ChildEndAtLevel(MaxLevel).Prev().NextWrap(),
   673  		},
   674  		{
   675  			"AdvanceWrap forward and back stays same for first cell at level",
   676  			CellIDFromFacePosLevel(0, 0, MaxLevel),
   677  			CellIDFromFace(5).ChildEndAtLevel(MaxLevel).Advance(-1).AdvanceWrap(1),
   678  		},
   679  		// Check basic properties of AdvanceWrap().
   680  		{
   681  			"advancing 7 steps around cube should end up one past start.",
   682  			CellIDFromFace(1),
   683  			CellIDFromFace(0).ChildBeginAtLevel(0).AdvanceWrap(7),
   684  		},
   685  		{
   686  			"twice around should end up where we started",
   687  			CellIDFromFace(0).ChildBeginAtLevel(0),
   688  			CellIDFromFace(0).ChildBeginAtLevel(0).AdvanceWrap(12),
   689  		},
   690  		{
   691  			"backwards once around plus one step should be one before we started",
   692  			CellIDFromFace(4),
   693  			CellIDFromFace(5).AdvanceWrap(-7),
   694  		},
   695  		{
   696  			"wrapping even multiple of times around should end where we started",
   697  			CellIDFromFace(0).ChildBeginAtLevel(0),
   698  			CellIDFromFace(0).ChildBeginAtLevel(0).AdvanceWrap(-12000000),
   699  		},
   700  		{
   701  			"wrapping combination of even times around should end where it started",
   702  			CellIDFromFace(0).ChildBeginAtLevel(5).AdvanceWrap(6644),
   703  			CellIDFromFace(0).ChildBeginAtLevel(5).AdvanceWrap(-11788),
   704  		},
   705  		{
   706  			"moving 256 should advance us one cell at max level",
   707  			id.Next().ChildBeginAtLevel(MaxLevel),
   708  			id.ChildBeginAtLevel(MaxLevel).AdvanceWrap(256),
   709  		},
   710  		{
   711  			"wrapping by 4 times cells per face should advance 4 faces",
   712  			CellIDFromFacePosLevel(1, 0, MaxLevel),
   713  			CellIDFromFacePosLevel(5, 0, MaxLevel).AdvanceWrap(2 << (2 * MaxLevel)),
   714  		},
   715  	}
   716  
   717  	for _, test := range tests {
   718  		if test.got != test.want {
   719  			t.Errorf("%s: got %v want %v", test.msg, test.got, test.want)
   720  		}
   721  	}
   722  }
   723  
   724  func TestCellIDAdvance(t *testing.T) {
   725  	tests := []struct {
   726  		ci    CellID
   727  		steps int64
   728  		want  CellID
   729  	}{
   730  		{
   731  			CellIDFromFace(0).ChildBeginAtLevel(0),
   732  			7,
   733  			CellIDFromFace(5).ChildEndAtLevel(0),
   734  		},
   735  		{
   736  			CellIDFromFace(0).ChildBeginAtLevel(0),
   737  			12,
   738  			CellIDFromFace(5).ChildEndAtLevel(0),
   739  		},
   740  		{
   741  			CellIDFromFace(5).ChildEndAtLevel(0),
   742  			-7,
   743  			CellIDFromFace(0).ChildBeginAtLevel(0),
   744  		},
   745  		{
   746  			CellIDFromFace(5).ChildEndAtLevel(0),
   747  			-12000000,
   748  			CellIDFromFace(0).ChildBeginAtLevel(0),
   749  		},
   750  		{
   751  			CellIDFromFace(0).ChildBeginAtLevel(5),
   752  			500,
   753  			CellIDFromFace(5).ChildEndAtLevel(5).Advance(500 - (6 << (2 * 5))),
   754  		},
   755  		{
   756  			CellIDFromFacePosLevel(3, 0x12345678, MaxLevel-4).ChildBeginAtLevel(MaxLevel),
   757  			256,
   758  			CellIDFromFacePosLevel(3, 0x12345678, MaxLevel-4).Next().ChildBeginAtLevel(MaxLevel),
   759  		},
   760  		{
   761  			CellIDFromFacePosLevel(1, 0, MaxLevel),
   762  			4 << (2 * MaxLevel),
   763  			CellIDFromFacePosLevel(5, 0, MaxLevel),
   764  		},
   765  	}
   766  
   767  	for _, test := range tests {
   768  		if got := test.ci.Advance(test.steps); got != test.want {
   769  			t.Errorf("CellID(%v).Advance(%d) = %v; want = %v", test.ci, test.steps, got, test.want)
   770  		}
   771  	}
   772  }
   773  
   774  func TestCellIDFaceSiTi(t *testing.T) {
   775  	id := CellIDFromFacePosLevel(3, 0x12345678, MaxLevel)
   776  	// Check that the (si, ti) coordinates of the center end in a
   777  	// 1 followed by (30 - level) 0's.
   778  	for level := 0; level <= MaxLevel; level++ {
   779  		l := MaxLevel - level
   780  		want := uint32(1) << uint(level)
   781  		mask := uint32(1)<<(uint(level)+1) - 1
   782  
   783  		_, si, ti := id.Parent(l).faceSiTi()
   784  		if want != si&mask {
   785  			t.Errorf("CellID.Parent(%d).faceSiTi(), si = %b, want %b", l, si&mask, want)
   786  		}
   787  		if want != ti&mask {
   788  			t.Errorf("CellID.Parent(%d).faceSiTi(), ti = %b, want %b", l, ti&mask, want)
   789  		}
   790  	}
   791  }
   792  
   793  func TestCellIDContinuity(t *testing.T) {
   794  	const maxWalkLevel = 8
   795  	const cellSize = 1.0 / (1 << maxWalkLevel)
   796  
   797  	// Make sure that sequentially increasing cell ids form a continuous
   798  	// path over the surface of the sphere, i.e. there are no
   799  	// discontinuous jumps from one region to another.
   800  
   801  	maxDist := MaxWidthMetric.Value(maxWalkLevel)
   802  	end := CellIDFromFace(5).ChildEndAtLevel(maxWalkLevel)
   803  	id := CellIDFromFace(0).ChildBeginAtLevel(maxWalkLevel)
   804  
   805  	for ; id != end; id = id.Next() {
   806  
   807  		if got := id.rawPoint().Angle(id.NextWrap().rawPoint()); float64(got) > maxDist {
   808  			t.Errorf("%v.rawPoint().Angle(%v.NextWrap().rawPoint()) = %v > %v", id, id, got, maxDist)
   809  		}
   810  		if id.NextWrap() != id.AdvanceWrap(1) {
   811  			t.Errorf("%v.NextWrap() != %v.AdvanceWrap(1) %v != %v)", id, id, id.NextWrap(), id.AdvanceWrap(1))
   812  		}
   813  		if id != id.NextWrap().AdvanceWrap(-1) {
   814  			t.Errorf("%v.NextWrap().AdvanceWrap(-1) = %v want %v)", id, id.NextWrap().AdvanceWrap(-1), id)
   815  		}
   816  
   817  		// Check that the rawPoint() returns the center of each cell
   818  		// in (s,t) coordinates.
   819  		_, u, v := xyzToFaceUV(id.rawPoint())
   820  		if !float64Eq(math.Remainder(uvToST(u), 0.5*cellSize), 0.0) {
   821  			t.Errorf("uvToST(%v) = %v, want %v", u, uvToST(u), 0.5*cellSize)
   822  		}
   823  		if !float64Eq(math.Remainder(uvToST(v), 0.5*cellSize), 0.0) {
   824  			t.Errorf("uvToST(%v) = %v, want %v", v, uvToST(v), 0.5*cellSize)
   825  		}
   826  	}
   827  }
   828  
   829  // sampleBoundary returns a random point on the boundary of the given rectangle.
   830  func sampleBoundary(rect r2.Rect) (u, v float64) {
   831  	if oneIn(2) {
   832  		v = randomUniformFloat64(rect.Y.Lo, rect.Y.Hi)
   833  		if oneIn(2) {
   834  			u = rect.X.Lo
   835  		} else {
   836  			u = rect.X.Hi
   837  		}
   838  	} else {
   839  		u = randomUniformFloat64(rect.X.Lo, rect.X.Hi)
   840  		if oneIn(2) {
   841  			v = rect.Y.Lo
   842  		} else {
   843  			v = rect.Y.Hi
   844  		}
   845  	}
   846  	return u, v
   847  }
   848  
   849  // projectToBoundary returns the closest point to uv on the boundary of rect.
   850  func projectToBoundary(u, v float64, rect r2.Rect) r2.Point {
   851  	du0 := math.Abs(u - rect.X.Lo)
   852  	du1 := math.Abs(u - rect.X.Hi)
   853  	dv0 := math.Abs(v - rect.Y.Lo)
   854  	dv1 := math.Abs(v - rect.Y.Hi)
   855  
   856  	dmin := math.Min(math.Min(du0, du1), math.Min(dv0, dv1))
   857  	if du0 == dmin {
   858  		return r2.Point{rect.X.Lo, rect.Y.ClampPoint(v)}
   859  	}
   860  	if du1 == dmin {
   861  		return r2.Point{rect.X.Hi, rect.Y.ClampPoint(v)}
   862  	}
   863  	if dv0 == dmin {
   864  		return r2.Point{rect.X.ClampPoint(u), rect.Y.Lo}
   865  	}
   866  
   867  	return r2.Point{rect.X.ClampPoint(u), rect.Y.Hi}
   868  }
   869  
   870  func TestCellIDExpandedByDistanceUV(t *testing.T) {
   871  	const maxDistDegrees = 10
   872  	for i := 0; i < 1000; i++ {
   873  		id := randomCellID()
   874  		distance := s1.Degree * s1.Angle(randomUniformFloat64(-maxDistDegrees, maxDistDegrees))
   875  
   876  		bound := id.boundUV()
   877  		expanded := expandedByDistanceUV(bound, distance)
   878  		for iter := 0; iter < 10; iter++ {
   879  			// Choose a point on the boundary of the rectangle.
   880  			face := randomUniformInt(6)
   881  			centerU, centerV := sampleBoundary(bound)
   882  			center := Point{faceUVToXYZ(face, centerU, centerV).Normalize()}
   883  
   884  			// Now sample a point from a disc of radius (2 * distance).
   885  			p := samplePointFromCap(CapFromCenterHeight(center, 2*math.Abs(float64(distance))))
   886  
   887  			// Find the closest point on the boundary to the sampled point.
   888  			u, v, ok := faceXYZToUV(face, p)
   889  			if !ok {
   890  				continue
   891  			}
   892  
   893  			uv := r2.Point{u, v}
   894  			closestUV := projectToBoundary(u, v, bound)
   895  			closest := faceUVToXYZ(face, closestUV.X, closestUV.Y).Normalize()
   896  			actualDist := p.Distance(Point{closest})
   897  
   898  			if distance >= 0 {
   899  				// expanded should contain all points in the original bound,
   900  				// and also all points within distance of the boundary.
   901  				if bound.ContainsPoint(uv) || actualDist < distance {
   902  					if !expanded.ContainsPoint(uv) {
   903  						t.Errorf("expandedByDistanceUV(%v, %v).ContainsPoint(%v) = false, want true", bound, distance, uv)
   904  					}
   905  				}
   906  			} else {
   907  				// expanded should not contain any points within distance
   908  				// of the original boundary.
   909  				if actualDist < -distance {
   910  					if expanded.ContainsPoint(uv) {
   911  						t.Errorf("negatively expandedByDistanceUV(%v, %v).ContainsPoint(%v) = true, want false", bound, distance, uv)
   912  					}
   913  				}
   914  			}
   915  		}
   916  	}
   917  }
   918  
   919  func TestCellIDMaxTile(t *testing.T) {
   920  	// This method is also tested more thoroughly in s2cellunion_test.
   921  	for iter := 0; iter < 1000; iter++ {
   922  		id := randomCellIDForLevel(10)
   923  
   924  		// Check that limit is returned for tiles at or beyond limit.
   925  		if got, want := id, id.MaxTile(id); got != want {
   926  			t.Errorf("%v.MaxTile(%v) = %v, want %v", id, id, got, want)
   927  		}
   928  		if got, want := id, id.Children()[0].MaxTile(id); got != want {
   929  			t.Errorf("%v.Children()[0].MaxTile(%v) = %v, want %v", id, id, got, want)
   930  		}
   931  		if got, want := id, id.Children()[1].MaxTile(id); got != want {
   932  			t.Errorf("%v.Children()[1].MaxTile(%v) = %v, want %v", id, id, got, want)
   933  		}
   934  		if got, want := id, id.Next().MaxTile(id); got != want {
   935  			t.Errorf("%v.Next().MaxTile(%v) = %v, want %v", id, id, got, want)
   936  		}
   937  		if got, want := id.Children()[0], id.MaxTile(id.Children()[0]); got != want {
   938  			t.Errorf("%v.MaxTile(%v.Children()[0] = %v, want %v", id, id, got, want)
   939  		}
   940  
   941  		// Check that the tile size is increased when possible.
   942  		if got, want := id, id.Children()[0].MaxTile(id.Next()); got != want {
   943  			t.Errorf("%v.Children()[0].MaxTile(%v.Next()) = %v, want %v", id, id, got, want)
   944  		}
   945  
   946  		if got, want := id, id.Children()[0].MaxTile(id.Next().Children()[0]); got != want {
   947  			t.Errorf("%v.Children()[0].MaxTile(%v.Next()) = %v, want %v", id, id, got, want)
   948  		}
   949  
   950  		if got, want := id, id.Children()[0].MaxTile(id.Next().Children()[1].Children()[0]); got != want {
   951  			t.Errorf("%v.Children()[0].MaxTile(%v.Next().Children()[1].Children()[0] = %v, want %v", id, id, got, want)
   952  		}
   953  
   954  		if got, want := id, id.Children()[0].Children()[0].MaxTile(id.Next()); got != want {
   955  			t.Errorf("%v.Children()[0].Children()[0].MaxTile(%v.Next()) = %v, want %v", id, id, got, want)
   956  		}
   957  
   958  		if got, want := id, id.Children()[0].Children()[0].Children()[0].MaxTile(id.Next()); got != want {
   959  			t.Errorf("%v.Children()[0].Children()[0].Children()[0].MaxTile(%v.Next()) = %v, want %v", id, id, got, want)
   960  		}
   961  
   962  		// Check that the tile size is decreased when necessary.
   963  		if got, want := id.Children()[0], id.MaxTile(id.Children()[0].Next()); got != want {
   964  			t.Errorf("%v.Children()[0], id.MaxTile(%v.Children()[0].Next()) = %v, want %v", id, id, got, want)
   965  		}
   966  
   967  		if got, want := id.Children()[0], id.MaxTile(id.Children()[0].Next().Children()[0]); got != want {
   968  			t.Errorf("%v.Children()[0], id.MaxTile(%v.Children()[0].Next().Children()[0]) = %v, want %v", id, id, got, want)
   969  		}
   970  
   971  		if got, want := id.Children()[0], id.MaxTile(id.Children()[0].Next().Children()[1]); got != want {
   972  			t.Errorf("%v.Children()[0], id.MaxTile(%v.Children()[0].Next().Children()[1]) = %v, want %v", id, id, got, want)
   973  		}
   974  
   975  		if got, want := id.Children()[0].Children()[0], id.MaxTile(id.Children()[0].Children()[0].Next()); got != want {
   976  			t.Errorf("%v.Children()[0].Children()[0], id.MaxTile(%v.Children()[0].Children()[0].Next()) = %v, want %v", id, id, got, want)
   977  		}
   978  
   979  		if got, want := id.Children()[0].Children()[0].Children()[0],
   980  			id.MaxTile(id.Children()[0].Children()[0].Children()[0].Next()); got != want {
   981  			t.Errorf("%v.MaxTile(%v.Children()[0].Children()[0].Children()[0].Next()) = %v, want %v", id, id, got, want)
   982  		}
   983  
   984  		// Check that the tile size is otherwise unchanged.
   985  		if got, want := id, id.MaxTile(id.Next()); got != want {
   986  			t.Errorf("%v.MaxTile(%v.Next()) = %v, want %v", id, id, got, want)
   987  		}
   988  
   989  		if got, want := id, id.MaxTile(id.Next().Children()[0]); got != want {
   990  			t.Errorf("%v.MaxTile(%v.Next().Children()[0]) = %v, want %v", id, id, got, want)
   991  		}
   992  
   993  		if got, want := id, id.MaxTile(id.Next().Children()[1].Children()[0]); got != want {
   994  			t.Errorf("%v.MaxTile(%v.Next().Children()[1].Children()[0]) = %v, want %v", id, id, got, want)
   995  		}
   996  	}
   997  }
   998  
   999  func TestCellIDCenterFaceSiTi(t *testing.T) {
  1000  	// Check that the (si, ti) coordinates of the center end in a
  1001  	// 1 followed by (30 - level) 0s.
  1002  
  1003  	id := CellIDFromFacePosLevel(3, 0x12345678, MaxLevel)
  1004  
  1005  	tests := []struct {
  1006  		id          CellID
  1007  		levelOffset uint
  1008  	}{
  1009  		// Leaf level, 30.
  1010  		{id, 0},
  1011  		// Level 29.
  1012  		{id.Parent(MaxLevel - 1), 1},
  1013  		// Level 28.
  1014  		{id.Parent(MaxLevel - 2), 2},
  1015  		// Level 20.
  1016  		{id.Parent(MaxLevel - 10), 10},
  1017  		// Level 10.
  1018  		{id.Parent(MaxLevel - 20), 20},
  1019  		// Level 0.
  1020  		{id.Parent(0), MaxLevel},
  1021  	}
  1022  
  1023  	for _, test := range tests {
  1024  		_, si, ti := test.id.centerFaceSiTi()
  1025  		want := 1 << test.levelOffset
  1026  		mask := (1 << (test.levelOffset + 1)) - 1
  1027  		if want != si&mask {
  1028  			t.Errorf("Level Offset %d. %b != %b", test.levelOffset, want, si&mask)
  1029  		}
  1030  		if want != ti&mask {
  1031  			t.Errorf("Level Offset: %d. %b != %b", test.levelOffset, want, ti&mask)
  1032  		}
  1033  	}
  1034  }
  1035  
  1036  // TODO(roberts): Remaining tests to convert.
  1037  // Coverage
  1038  // TraversalOrder
  1039  

View as plain text