Source file src/github.com/golang/geo/s2/cellunion_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/r1"
    23  	"github.com/golang/geo/s1"
    24  )
    25  
    26  func TestCellUnionDuplicateCellsNotValid(t *testing.T) {
    27  	id := cellIDFromPoint(PointFromCoords(1, 0, 0))
    28  	cu := CellUnion([]CellID{id, id})
    29  	if cu.IsValid() {
    30  		t.Errorf("%v.IsValid() = true, want false", cu)
    31  	}
    32  }
    33  
    34  func TestCellUnionUnsortedCellsNotValid(t *testing.T) {
    35  	id := cellIDFromPoint(PointFromCoords(1, 0, 0)).Parent(10)
    36  	cu := CellUnion([]CellID{id, id.Prev()})
    37  	if cu.IsValid() {
    38  		t.Errorf("%v.IsValid() = true, want false", cu)
    39  	}
    40  }
    41  
    42  func TestCellUnionIsNormalized(t *testing.T) {
    43  	id := cellIDFromPoint(PointFromCoords(1, 0, 0)).Parent(10)
    44  	children := id.Children()
    45  	cu := CellUnion([]CellID{children[0], children[1], children[2], children[3]})
    46  	if !(cu.IsValid()) {
    47  		t.Errorf("%v.IsValid() = false, want true", cu)
    48  	}
    49  	if cu.IsNormalized() {
    50  		t.Errorf("%v.IsNormalized() = true, want false", cu)
    51  	}
    52  }
    53  
    54  func TestCellUnionInvalidCellIdNotValid(t *testing.T) {
    55  	cu := CellUnion([]CellID{CellID(0)})
    56  	if cu.IsValid() {
    57  		t.Error("CellUnion containing an invalid CellID should not be valid")
    58  	}
    59  }
    60  
    61  func TestCellUnionAreSiblings(t *testing.T) {
    62  	id := cellIDFromPoint(PointFromCoords(1, 0, 0)).Parent(10)
    63  	children := id.Children()
    64  	if siblings := areSiblings(children[0], children[1], children[2], children[3]); !siblings {
    65  		t.Errorf("areSiblings(%v, %v, %v, %v) = false, want true", children[0], children[1], children[2], children[3])
    66  	}
    67  
    68  	if siblings := areSiblings(id, children[1], children[2], children[3]); siblings {
    69  		t.Errorf("areSiblings(%v, %v, %v, %v) = true, want false", id, children[1], children[2], children[3])
    70  	}
    71  }
    72  
    73  func TestCellUnionNormalization(t *testing.T) {
    74  	cu := CellUnion{
    75  		0x80855c0000000000, // A: a cell over Pittsburg CA
    76  		0x80855d0000000000, // B, a child of A
    77  		0x8085634000000000, // first child of X, disjoint from A
    78  		0x808563c000000000, // second child of X
    79  		0x80855dc000000000, // a child of B
    80  		0x808562c000000000, // third child of X
    81  		0x8085624000000000, // fourth child of X
    82  		0x80855d0000000000, // B again
    83  	}
    84  	exp := CellUnion{
    85  		0x80855c0000000000, // A
    86  		0x8085630000000000, // X
    87  	}
    88  	cu.Normalize()
    89  	if !reflect.DeepEqual(cu, exp) {
    90  		t.Errorf("got %v, want %v", cu, exp)
    91  	}
    92  
    93  	// add a redundant cell
    94  	/* TODO(dsymonds)
    95  	cu.Add(0x808562c000000000)
    96  	if !reflect.DeepEqual(cu, exp) {
    97  		t.Errorf("after redundant add, got %v, want %v", cu, exp)
    98  	}
    99  	*/
   100  }
   101  
   102  func TestCellUnionBasic(t *testing.T) {
   103  	empty := CellUnion{}
   104  	empty.Normalize()
   105  	if len(empty) != 0 {
   106  		t.Errorf("empty CellUnion had %d cells, want 0", len(empty))
   107  	}
   108  
   109  	face1ID := CellIDFromFace(1)
   110  	face1Cell := CellFromCellID(face1ID)
   111  	face1Union := CellUnion{face1ID}
   112  	face1Union.Normalize()
   113  	if len(face1Union) != 1 {
   114  		t.Errorf("%v had %d cells, want 1", face1Union, len(face1Union))
   115  	}
   116  	if face1ID != face1Union[0] {
   117  		t.Errorf("%v[0] = %v, want %v", face1Union, face1Union[0], face1ID)
   118  	}
   119  	if got := face1Union.ContainsCell(face1Cell); !got {
   120  		t.Errorf("%v.ContainsCell(%v) = %t, want %t", face1Union, face1Cell, got, true)
   121  	}
   122  
   123  	face2ID := CellIDFromFace(2)
   124  	face2Cell := CellFromCellID(face2ID)
   125  	face2Union := CellUnion{face2ID}
   126  	face2Union.Normalize()
   127  	if len(face2Union) != 1 {
   128  		t.Errorf("%v had %d cells, want 1", face2Union, len(face2Union))
   129  	}
   130  	if face2ID != face2Union[0] {
   131  		t.Errorf("%v[0] = %v, want %v", face2Union, face2Union[0], face2ID)
   132  	}
   133  
   134  	if got := face1Union.ContainsCell(face2Cell); got {
   135  		t.Errorf("%v.ContainsCell(%v) = %t, want %t", face1Union, face2Cell, got, false)
   136  	}
   137  
   138  }
   139  
   140  func TestCellUnion(t *testing.T) {
   141  	tests := []struct {
   142  		cells     []CellID // A test CellUnion.
   143  		contained []CellID // List of cellIDs contained in the CellUnion.
   144  		overlaps  []CellID // List of CellIDs that intersects the CellUnion but not contained in it.
   145  		disjoint  []CellID // List of CellIDs that are disjoint from the CellUnion.
   146  	}{
   147  		{
   148  			// Single cell around NYC, and some simple nearby probes
   149  			cells: []CellID{0x89c25c0000000000},
   150  			contained: []CellID{
   151  				CellID(0x89c25c0000000000).ChildBegin(),
   152  				CellID(0x89c25c0000000000).ChildBeginAtLevel(28),
   153  			},
   154  			overlaps: []CellID{
   155  				CellID(0x89c25c0000000000).immediateParent(),
   156  				CellIDFromFace(CellID(0x89c25c0000000000).Face()), // the whole face
   157  			},
   158  			disjoint: []CellID{
   159  				CellID(0x89c25c0000000000).Next(),                       // Cell next to this one at same level
   160  				CellID(0x89c25c0000000000).Next().ChildBeginAtLevel(28), // Cell next to this one at deep level
   161  				0x89c2700000000000,                                      // Big(er) neighbor cell
   162  				0x89e9000000000000,                                      // Very big next door cell.
   163  				0x89c1000000000000,                                      // Very big cell, smaller value than probe
   164  			},
   165  		},
   166  
   167  		{
   168  			// NYC and SFO:
   169  			cells: []CellID{
   170  				0x89c25b0000000000, // NYC
   171  				0x89c2590000000000, // NYC
   172  				0x89c2f70000000000, // NYC
   173  				0x89c2f50000000000, // NYC
   174  				0x8085870000000000, // SFO
   175  				0x8085810000000000, // SFO
   176  				0x808f7d0000000000, // SFO
   177  				0x808f7f0000000000, // SFO
   178  			},
   179  			contained: []CellID{
   180  				0x808f7ef300000000, // SFO
   181  				0x808f7e5cf0000000, // SFO
   182  				0x808587f000000000, // SFO
   183  				0x89c25ac000000000, // NYC
   184  				0x89c259a400000000, // NYC
   185  				0x89c258fa10000000, // NYC
   186  				0x89c258f174007000, // NYC
   187  			},
   188  			overlaps: []CellID{
   189  				0x808c000000000000, // Big SFO
   190  				0x89c4000000000000, // Big NYC
   191  			},
   192  			disjoint: []CellID{
   193  				0x89c15a4fcb1bb000, // outside NYC
   194  				0x89c15a4e4aa95000, // outside NYC
   195  				0x8094000000000000, // outside SFO (big)
   196  				0x8096f10000000000, // outside SFO (smaller)
   197  
   198  				0x87c0000000000000, // Midwest very big
   199  			},
   200  		},
   201  		{
   202  			// CellUnion with cells at many levels:
   203  			cells: []CellID{
   204  				0x8100000000000000, // starting around california
   205  				0x8740000000000000, // adjacent cells at increasing
   206  				0x8790000000000000, // levels, moving eastward.
   207  				0x87f4000000000000,
   208  				0x87f9000000000000, // going down across the midwest
   209  				0x87ff400000000000,
   210  				0x87ff900000000000,
   211  				0x87fff40000000000,
   212  				0x87fff90000000000,
   213  				0x87ffff4000000000,
   214  				0x87ffff9000000000,
   215  				0x87fffff400000000,
   216  				0x87fffff900000000,
   217  				0x87ffffff40000000,
   218  				0x87ffffff90000000,
   219  				0x87fffffff4000000,
   220  				0x87fffffff9000000,
   221  				0x87ffffffff400000, // to a very small cell in Wisconsin
   222  			},
   223  			contained: []CellID{
   224  				0x808f400000000000,
   225  				0x80eb118b00000000,
   226  				0x8136a7a11d000000,
   227  				0x8136a7a11dac0000,
   228  				0x876c7c0000000000,
   229  				0x87f96d0000000000,
   230  				0x87ffffffff400000,
   231  			},
   232  			overlaps: []CellID{
   233  				CellID(0x8100000000000000).immediateParent(),
   234  				CellID(0x8740000000000000).immediateParent(),
   235  			},
   236  			disjoint: []CellID{
   237  				0x52aaaaaaab300000,
   238  				0x52aaaaaaacd00000,
   239  				0x87fffffffa100000,
   240  				0x87ffffffed500000,
   241  				0x87ffffffa0100000,
   242  				0x87fffffed5540000,
   243  				0x87fffffed6240000,
   244  				0x52aaaacccb340000,
   245  				0x87a0000400000000,
   246  				0x87a000001f000000,
   247  				0x87a0000029d00000,
   248  				0x9500000000000000,
   249  			},
   250  		},
   251  	}
   252  	for _, test := range tests {
   253  		union := CellUnion(test.cells)
   254  		union.Normalize()
   255  
   256  		// Ensure self-containment tests are correct.
   257  		for _, id := range test.cells {
   258  			if !union.IntersectsCellID(id) {
   259  				t.Errorf("CellUnion %v should self-intersect %v but does not", union, id)
   260  			}
   261  			if !union.ContainsCellID(id) {
   262  				t.Errorf("CellUnion %v should self-contain %v but does not", union, id)
   263  			}
   264  		}
   265  		// Test for containment specified in test case.
   266  		for _, id := range test.contained {
   267  			if !union.IntersectsCellID(id) {
   268  				t.Errorf("CellUnion %v should intersect %v but does not", union, id)
   269  			}
   270  			if !union.ContainsCellID(id) {
   271  				t.Errorf("CellUnion %v should contain %v but does not", union, id)
   272  			}
   273  		}
   274  		// Make sure the CellUnion intersect these cells but do not contain.
   275  		for _, id := range test.overlaps {
   276  			if !union.IntersectsCellID(id) {
   277  				t.Errorf("CellUnion %v should intersect %v but does not", union, id)
   278  			}
   279  			if union.ContainsCellID(id) {
   280  				t.Errorf("CellUnion %v should not contain %v but does", union, id)
   281  			}
   282  		}
   283  		// Negative cases make sure the CellUnion neither contain nor intersect these cells
   284  		for _, id := range test.disjoint {
   285  			if union.IntersectsCellID(id) {
   286  				t.Errorf("CellUnion %v should not intersect %v but does", union, id)
   287  			}
   288  			if union.ContainsCellID(id) {
   289  				t.Errorf("CellUnion %v should not contain %v but does", union, id)
   290  			}
   291  		}
   292  	}
   293  }
   294  
   295  func addCells(id CellID, selected bool, input *[]CellID, expected *[]CellID, t *testing.T) {
   296  	// Decides whether to add "id" and/or some of its descendants to the test case.  If "selected"
   297  	// is true, then the region covered by "id" *must* be added to the test case (either by adding
   298  	// "id" itself, or some combination of its descendants, or both).  If cell ids are to the test
   299  	// case "input", then the corresponding expected result after simplification is added to
   300  	// "expected".
   301  
   302  	if id == 0 {
   303  		// Initial call: decide whether to add cell(s) from each face.
   304  		for face := 0; face < 6; face++ {
   305  			addCells(CellIDFromFace(face), false, input, expected, t)
   306  		}
   307  		return
   308  	}
   309  
   310  	if id.IsLeaf() {
   311  		// The oneIn() call below ensures that the parent of a leaf cell will always be selected (if
   312  		// we make it that far down the hierarchy).
   313  		if selected != true {
   314  			t.Errorf("id IsLeaf() and not selected")
   315  		}
   316  		*input = append(*input, id)
   317  		return
   318  	}
   319  
   320  	// The following code ensures that the probability of selecting a cell at each level is
   321  	// approximately the same, i.e. we test normalization of cells at all levels.
   322  	if !selected && oneIn(MaxLevel-id.Level()) {
   323  		//  Once a cell has been selected, the expected output is predetermined.  We then make sure
   324  		//  that cells are selected that will normalize to the desired output.
   325  		*expected = append(*expected, id)
   326  		selected = true
   327  
   328  	}
   329  
   330  	// With the rnd.OneIn() constants below, this function adds an average
   331  	// of 5/6 * (kMaxLevel - level) cells to "input" where "level" is the
   332  	// level at which the cell was first selected (level 15 on average).
   333  	// Therefore the average number of input cells in a test case is about
   334  	// (5/6 * 15 * 6) = 75.  The average number of output cells is about 6.
   335  
   336  	// If a cell is selected, we add it to "input" with probability 5/6.
   337  	added := false
   338  	if selected && !oneIn(6) {
   339  		*input = append(*input, id)
   340  		added = true
   341  	}
   342  	numChildren := 0
   343  	for child := id.ChildBegin(); child != id.ChildEnd(); child = child.Next() {
   344  		// If the cell is selected, on average we recurse on 4/12 = 1/3 child.
   345  		// This intentionally may result in a cell and some of its children
   346  		// being included in the test case.
   347  		//
   348  		// If the cell is not selected, on average we recurse on one child.
   349  		// We also make sure that we do not recurse on all 4 children, since
   350  		// then we might include all 4 children in the input case by accident
   351  		// (in which case the expected output would not be correct).
   352  		recurse := false
   353  		if selected {
   354  			recurse = oneIn(12)
   355  		} else {
   356  			recurse = oneIn(4)
   357  		}
   358  		if recurse && numChildren < 3 {
   359  			addCells(child, selected, input, expected, t)
   360  			numChildren++
   361  		}
   362  		// If this cell was selected but the cell itself was not added, we
   363  		// must ensure that all 4 children (or some combination of their
   364  		// descendants) are added.
   365  
   366  		if selected && !added {
   367  			addCells(child, selected, input, expected, t)
   368  		}
   369  	}
   370  }
   371  
   372  func TestCellUnionNormalizePseudoRandom(t *testing.T) {
   373  	// Try a bunch of random test cases, and keep track of average statistics
   374  	// for normalization (to see if they agree with the analysis above).
   375  
   376  	inSum := 0
   377  	outSum := 0
   378  	iters := 2000
   379  
   380  	for i := 0; i < iters; i++ {
   381  		input := []CellID{}
   382  		expected := []CellID{}
   383  		addCells(CellID(0), false, &input, &expected, t)
   384  		inSum += len(input)
   385  		outSum += len(expected)
   386  		cellunion := CellUnion(input)
   387  		cellunion.Normalize()
   388  
   389  		if len(expected) != len(cellunion) {
   390  			t.Errorf("Expected size of union to be %d, but got %d.",
   391  				len(expected), len(cellunion))
   392  		}
   393  
   394  		// Test CapBound().
   395  		cb := cellunion.CapBound()
   396  		for _, ci := range cellunion {
   397  			if !cb.ContainsCell(CellFromCellID(ci)) {
   398  				t.Errorf("CapBound %v of union %v should contain cellID %v", cb, cellunion, ci)
   399  			}
   400  		}
   401  
   402  		for _, j := range input {
   403  			if !cellunion.ContainsCellID(j) {
   404  				t.Errorf("Expected containment of CellID %v", j)
   405  			}
   406  
   407  			if cellunion.IntersectsCellID(j) == false {
   408  				t.Errorf("Expected intersection with %v.", j)
   409  			}
   410  
   411  			if !j.isFace() {
   412  				if cellunion.IntersectsCellID(j.immediateParent()) == false {
   413  					t.Errorf("Expected intersection with parent cell %v.", j.immediateParent())
   414  					if j.Level() > 1 {
   415  						if cellunion.IntersectsCellID(j.immediateParent().immediateParent()) == false {
   416  							t.Errorf("Expected intersection with parent's parent %v.",
   417  								j.immediateParent().immediateParent())
   418  						}
   419  						if cellunion.IntersectsCellID(j.Parent(0)) == false {
   420  							t.Errorf("Expected intersection with parent %v at level 0.", j.Parent(0))
   421  						}
   422  					}
   423  				}
   424  			}
   425  
   426  			if !j.IsLeaf() {
   427  				if cellunion.ContainsCellID(j.ChildBegin()) == false {
   428  					t.Errorf("Expected containment of %v.", j.ChildBegin())
   429  				}
   430  				if cellunion.IntersectsCellID(j.ChildBegin()) == false {
   431  					t.Errorf("Expected intersection with %v.", j.ChildBegin())
   432  				}
   433  				if cellunion.ContainsCellID(j.ChildEnd().Prev()) == false {
   434  					t.Errorf("Expected containment of %v.", j.ChildEnd().Prev())
   435  				}
   436  				if cellunion.IntersectsCellID(j.ChildEnd().Prev()) == false {
   437  					t.Errorf("Expected intersection with %v.", j.ChildEnd().Prev())
   438  				}
   439  				if cellunion.ContainsCellID(j.ChildBeginAtLevel(MaxLevel)) == false {
   440  					t.Errorf("Expected containment of %v.", j.ChildBeginAtLevel(MaxLevel))
   441  				}
   442  				if cellunion.IntersectsCellID(j.ChildBeginAtLevel(MaxLevel)) == false {
   443  					t.Errorf("Expected intersection with %v.", j.ChildBeginAtLevel(MaxLevel))
   444  				}
   445  			}
   446  		}
   447  
   448  		for _, exp := range expected {
   449  			if !exp.isFace() {
   450  				if cellunion.ContainsCellID(exp.Parent(exp.Level() - 1)) {
   451  					t.Errorf("cellunion should not contain its parent %v", exp.Parent(exp.Level()-1))
   452  				}
   453  				if cellunion.ContainsCellID(exp.Parent(0)) {
   454  					t.Errorf("cellunion should not contain the top level parent %v", exp.Parent(0))
   455  				}
   456  			}
   457  		}
   458  
   459  		var test []CellID
   460  		var dummy []CellID
   461  		addCells(CellID(0), false, &test, &dummy, t)
   462  		for _, j := range test {
   463  			intersects := false
   464  			contains := false
   465  			for _, k := range expected {
   466  				if k.Contains(j) {
   467  					contains = true
   468  				}
   469  				if k.Intersects(j) {
   470  					intersects = true
   471  				}
   472  			}
   473  			if cellunion.ContainsCellID(j) != contains {
   474  				t.Errorf("Expected contains with %v.", (uint64)(j))
   475  			}
   476  			if cellunion.IntersectsCellID(j) != intersects {
   477  				t.Errorf("Expected intersection with %v.", (uint64)(j))
   478  			}
   479  		}
   480  	}
   481  	t.Logf("avg in %.2f, avg out %.2f\n", (float64)(inSum)/(float64)(iters), (float64)(outSum)/(float64)(iters))
   482  }
   483  
   484  func TestCellUnionDenormalize(t *testing.T) {
   485  	tests := []struct {
   486  		name string
   487  		minL int
   488  		lMod int
   489  		cu   *CellUnion
   490  		exp  *CellUnion
   491  	}{
   492  		{
   493  			"not expanded, level mod == 1",
   494  			10,
   495  			1,
   496  			&CellUnion{
   497  				CellIDFromFace(2).ChildBeginAtLevel(11),
   498  				CellIDFromFace(2).ChildBeginAtLevel(11),
   499  				CellIDFromFace(3).ChildBeginAtLevel(14),
   500  				CellIDFromFace(0).ChildBeginAtLevel(10),
   501  			},
   502  			&CellUnion{
   503  				CellIDFromFace(2).ChildBeginAtLevel(11),
   504  				CellIDFromFace(2).ChildBeginAtLevel(11),
   505  				CellIDFromFace(3).ChildBeginAtLevel(14),
   506  				CellIDFromFace(0).ChildBeginAtLevel(10),
   507  			},
   508  		},
   509  		{
   510  			"not expanded, level mod > 1",
   511  			10,
   512  			2,
   513  			&CellUnion{
   514  				CellIDFromFace(2).ChildBeginAtLevel(12),
   515  				CellIDFromFace(2).ChildBeginAtLevel(12),
   516  				CellIDFromFace(3).ChildBeginAtLevel(14),
   517  				CellIDFromFace(0).ChildBeginAtLevel(10),
   518  			},
   519  			&CellUnion{
   520  				CellIDFromFace(2).ChildBeginAtLevel(12),
   521  				CellIDFromFace(2).ChildBeginAtLevel(12),
   522  				CellIDFromFace(3).ChildBeginAtLevel(14),
   523  				CellIDFromFace(0).ChildBeginAtLevel(10),
   524  			},
   525  		},
   526  		{
   527  			"expended, (level - min_level) is not multiple of level mod",
   528  			10,
   529  			3,
   530  			&CellUnion{
   531  				CellIDFromFace(2).ChildBeginAtLevel(12),
   532  				CellIDFromFace(5).ChildBeginAtLevel(11),
   533  			},
   534  			&CellUnion{
   535  				CellIDFromFace(2).ChildBeginAtLevel(12).Children()[0],
   536  				CellIDFromFace(2).ChildBeginAtLevel(12).Children()[1],
   537  				CellIDFromFace(2).ChildBeginAtLevel(12).Children()[2],
   538  				CellIDFromFace(2).ChildBeginAtLevel(12).Children()[3],
   539  				CellIDFromFace(5).ChildBeginAtLevel(11).Children()[0].Children()[0],
   540  				CellIDFromFace(5).ChildBeginAtLevel(11).Children()[0].Children()[1],
   541  				CellIDFromFace(5).ChildBeginAtLevel(11).Children()[0].Children()[2],
   542  				CellIDFromFace(5).ChildBeginAtLevel(11).Children()[0].Children()[3],
   543  				CellIDFromFace(5).ChildBeginAtLevel(11).Children()[1].Children()[0],
   544  				CellIDFromFace(5).ChildBeginAtLevel(11).Children()[1].Children()[1],
   545  				CellIDFromFace(5).ChildBeginAtLevel(11).Children()[1].Children()[2],
   546  				CellIDFromFace(5).ChildBeginAtLevel(11).Children()[1].Children()[3],
   547  				CellIDFromFace(5).ChildBeginAtLevel(11).Children()[2].Children()[0],
   548  				CellIDFromFace(5).ChildBeginAtLevel(11).Children()[2].Children()[1],
   549  				CellIDFromFace(5).ChildBeginAtLevel(11).Children()[2].Children()[2],
   550  				CellIDFromFace(5).ChildBeginAtLevel(11).Children()[2].Children()[3],
   551  				CellIDFromFace(5).ChildBeginAtLevel(11).Children()[3].Children()[0],
   552  				CellIDFromFace(5).ChildBeginAtLevel(11).Children()[3].Children()[1],
   553  				CellIDFromFace(5).ChildBeginAtLevel(11).Children()[3].Children()[2],
   554  				CellIDFromFace(5).ChildBeginAtLevel(11).Children()[3].Children()[3],
   555  			},
   556  		},
   557  		{
   558  			"expended, level < min_level",
   559  			10,
   560  			3,
   561  			&CellUnion{
   562  				CellIDFromFace(2).ChildBeginAtLevel(9),
   563  			},
   564  			&CellUnion{
   565  				CellIDFromFace(2).ChildBeginAtLevel(9).Children()[0],
   566  				CellIDFromFace(2).ChildBeginAtLevel(9).Children()[1],
   567  				CellIDFromFace(2).ChildBeginAtLevel(9).Children()[2],
   568  				CellIDFromFace(2).ChildBeginAtLevel(9).Children()[3],
   569  			},
   570  		},
   571  	}
   572  	for _, test := range tests {
   573  		if test.cu.Denormalize(test.minL, test.lMod); !reflect.DeepEqual(test.cu, test.exp) {
   574  			t.Errorf("test: %s; got %v, want %v", test.name, test.cu, test.exp)
   575  		}
   576  	}
   577  }
   578  
   579  func TestCellUnionRectBound(t *testing.T) {
   580  	tests := []struct {
   581  		cu   *CellUnion
   582  		want Rect
   583  	}{
   584  		{&CellUnion{}, EmptyRect()},
   585  		{
   586  			&CellUnion{CellIDFromFace(1)},
   587  			Rect{
   588  				r1.Interval{-math.Pi / 4, math.Pi / 4},
   589  				s1.Interval{math.Pi / 4, 3 * math.Pi / 4},
   590  			},
   591  		},
   592  		{
   593  			&CellUnion{
   594  				0x808c000000000000, // Big SFO
   595  			},
   596  			Rect{
   597  				r1.Interval{
   598  					float64(s1.Degree * 34.644220547108482),
   599  					float64(s1.Degree * 38.011928357226651),
   600  				},
   601  				s1.Interval{
   602  					float64(s1.Degree * -124.508522987668428),
   603  					float64(s1.Degree * -121.628309835221216),
   604  				},
   605  			},
   606  		},
   607  		{
   608  			&CellUnion{
   609  				0x89c4000000000000, // Big NYC
   610  			},
   611  			Rect{
   612  				r1.Interval{
   613  					float64(s1.Degree * 38.794595155857657),
   614  					float64(s1.Degree * 41.747046884651063),
   615  				},
   616  				s1.Interval{
   617  					float64(s1.Degree * -76.456308667788633),
   618  					float64(s1.Degree * -73.465162142654819),
   619  				},
   620  			},
   621  		},
   622  		{
   623  			&CellUnion{
   624  				0x89c4000000000000, // Big NYC
   625  				0x808c000000000000, // Big SFO
   626  			},
   627  			Rect{
   628  				r1.Interval{
   629  					float64(s1.Degree * 34.644220547108482),
   630  					float64(s1.Degree * 41.747046884651063),
   631  				},
   632  				s1.Interval{
   633  					float64(s1.Degree * -124.508522987668428),
   634  					float64(s1.Degree * -73.465162142654819),
   635  				},
   636  			},
   637  		},
   638  	}
   639  
   640  	for _, test := range tests {
   641  		if got := test.cu.RectBound(); !rectsApproxEqual(got, test.want, epsilon, epsilon) {
   642  			t.Errorf("%v.RectBound() = %v, want %v", test.cu, got, test.want)
   643  		}
   644  	}
   645  }
   646  
   647  func TestCellUnionLeafCellsCovered(t *testing.T) {
   648  	fiveFaces := CellUnion{CellIDFromFace(0)}
   649  	fiveFaces.ExpandAtLevel(0)
   650  	wholeWorld := CellUnion{CellIDFromFace(0)}
   651  	wholeWorld.ExpandAtLevel(0)
   652  	wholeWorld.ExpandAtLevel(0)
   653  
   654  	tests := []struct {
   655  		have []CellID
   656  		want int64
   657  	}{
   658  		{},
   659  		{
   660  			have: []CellID{},
   661  			want: 0,
   662  		},
   663  		{
   664  			// One leaf cell on face 0.
   665  			have: []CellID{
   666  				CellIDFromFace(0).ChildBeginAtLevel(MaxLevel),
   667  			},
   668  			want: 1,
   669  		},
   670  		{
   671  			// Face 0 itself (which includes the previous leaf cell).
   672  			have: []CellID{
   673  				CellIDFromFace(0).ChildBeginAtLevel(MaxLevel),
   674  				CellIDFromFace(0),
   675  			},
   676  			want: 1 << 60,
   677  		},
   678  		{
   679  			have: fiveFaces,
   680  			want: 5 << 60,
   681  		},
   682  		{
   683  			have: wholeWorld,
   684  			want: 6 << 60,
   685  		},
   686  		{
   687  			// Add some disjoint cells.
   688  			have: []CellID{
   689  				CellIDFromFace(0).ChildBeginAtLevel(MaxLevel),
   690  				CellIDFromFace(0),
   691  				CellIDFromFace(1).ChildBeginAtLevel(1),
   692  				CellIDFromFace(2).ChildBeginAtLevel(2),
   693  				CellIDFromFace(2).ChildEndAtLevel(2).Prev(),
   694  				CellIDFromFace(3).ChildBeginAtLevel(14),
   695  				CellIDFromFace(4).ChildBeginAtLevel(27),
   696  				CellIDFromFace(4).ChildEndAtLevel(15).Prev(),
   697  				CellIDFromFace(5).ChildBeginAtLevel(30),
   698  			},
   699  			want: 1 + (1 << 6) + (1 << 30) + (1 << 32) +
   700  				(2 << 56) + (1 << 58) + (1 << 60),
   701  		},
   702  	}
   703  
   704  	for _, test := range tests {
   705  		cu := CellUnion(test.have)
   706  		cu.Normalize()
   707  		if got := cu.LeafCellsCovered(); got != test.want {
   708  			t.Errorf("CellUnion(%v).LeafCellsCovered() = %v, want %v", cu, got, test.want)
   709  		}
   710  	}
   711  }
   712  
   713  func TestCellUnionFromRange(t *testing.T) {
   714  	for iter := 0; iter < 2000; iter++ {
   715  		min := randomCellIDForLevel(MaxLevel)
   716  		max := randomCellIDForLevel(MaxLevel)
   717  		if min > max {
   718  			min, max = max, min
   719  		}
   720  
   721  		cu := CellUnionFromRange(min, max.Next())
   722  		if len(cu) <= 0 {
   723  			t.Errorf("len(CellUnionFromRange(%v, %v)) = %d, want > 0", min, max.Next(), len(cu))
   724  		}
   725  		if min != cu[0].RangeMin() {
   726  			t.Errorf("%v.RangeMin of CellUnion should not be below the minimum value it was created from %v", cu[0], min)
   727  		}
   728  		if max != cu[len(cu)-1].RangeMax() {
   729  			t.Errorf("%v.RangeMax of CellUnion should not be above the maximum value it was created from %v", cu[len(cu)-1], max)
   730  		}
   731  		for i := 1; i < len(cu); i++ {
   732  			if got, want := cu[i].RangeMin(), cu[i-1].RangeMax().Next(); got != want {
   733  				t.Errorf("%v.RangeMin() = %v, want %v", cu[i], got, want)
   734  			}
   735  		}
   736  	}
   737  
   738  	// Focus on test cases that generate an empty or full range.
   739  
   740  	// Test an empty range before the minimum CellID.
   741  	idBegin := CellIDFromFace(0).ChildBeginAtLevel(MaxLevel)
   742  	cu := CellUnionFromRange(idBegin, idBegin)
   743  	if len(cu) != 0 {
   744  		t.Errorf("CellUnionFromRange with begin and end as the first CellID should be empty, got %d", len(cu))
   745  	}
   746  
   747  	// Test an empty range after the maximum CellID.
   748  	idEnd := CellIDFromFace(5).ChildEndAtLevel(MaxLevel)
   749  	cu = CellUnionFromRange(idEnd, idEnd)
   750  	if len(cu) != 0 {
   751  		t.Errorf("CellUnionFromRange with begin and end as the last CellID should be empty, got %d", len(cu))
   752  	}
   753  
   754  	// Test the full sphere.
   755  	cu = CellUnionFromRange(idBegin, idEnd)
   756  	if len(cu) != 6 {
   757  		t.Errorf("CellUnionFromRange from first CellID to last CellID should have 6 cells, got %d", len(cu))
   758  	}
   759  
   760  	for i := 0; i < len(cu); i++ {
   761  		if !cu[i].isFace() {
   762  			t.Errorf("CellUnionFromRange for full sphere cu[%d].isFace() = %t, want %t", i, cu[i].isFace(), true)
   763  		}
   764  	}
   765  }
   766  
   767  func TestCellUnionFromUnionDiffIntersection(t *testing.T) {
   768  	const iters = 2000
   769  	for i := 0; i < iters; i++ {
   770  		input := []CellID{}
   771  		expected := []CellID{}
   772  		addCells(CellID(0), false, &input, &expected, t)
   773  
   774  		var x, y, xOrY, xAndY []CellID
   775  		for _, id := range input {
   776  			inX := oneIn(2)
   777  			inY := oneIn(2)
   778  
   779  			if inX {
   780  				x = append(x, id)
   781  			}
   782  			if inY {
   783  				y = append(y, id)
   784  			}
   785  			if inX || inY {
   786  				xOrY = append(xOrY, id)
   787  			}
   788  		}
   789  
   790  		xcells := CellUnion(x)
   791  		xcells.Normalize()
   792  		ycells := CellUnion(y)
   793  		ycells.Normalize()
   794  		xOrYExpected := CellUnion(xOrY)
   795  		xOrYExpected.Normalize()
   796  
   797  		xOrYCells := CellUnionFromUnion(xcells, ycells)
   798  
   799  		if !xOrYCells.Equal(xOrYExpected) {
   800  			t.Errorf("CellUnionFromUnion(%v, %v) = %v, want %v", xcells, ycells, xOrYCells, xOrYExpected)
   801  		}
   802  
   803  		// Compute the intersection of x with each cell of y,
   804  		// check that this intersection is correct, and append the
   805  		// results to xAndYExpected.
   806  		for _, yid := range ycells {
   807  			u := CellUnionFromIntersectionWithCellID(xcells, yid)
   808  			for _, xid := range xcells {
   809  				if xid.Contains(yid) {
   810  					if !(len(u) == 1 && u[0] == yid) {
   811  						t.Errorf("CellUnionFromIntersectionWithCellID(%v, %v) = %v with len: %d, want len of 1.", xcells, yid, u, len(u))
   812  					}
   813  				} else if yid.Contains(xid) {
   814  					if !u.ContainsCellID(xid) {
   815  						t.Errorf("%v.ContainsCellID(%v) = false, want true", u, xid)
   816  					}
   817  				}
   818  			}
   819  			for _, uCellID := range u {
   820  				if !xcells.ContainsCellID(uCellID) {
   821  					t.Errorf("%v.ContainsCellID(%v) = false, but should contain CellID that was used to create CellUnion", xcells, uCellID)
   822  				}
   823  				if !yid.Contains(uCellID) {
   824  					t.Errorf("%v.Contains(%v) = false, but should contain CellID that was used to create CellUnion", yid, uCellID)
   825  				}
   826  			}
   827  
   828  			xAndY = append(xAndY, u...)
   829  		}
   830  
   831  		xAndYExpected := CellUnion(xAndY)
   832  		xAndYExpected.Normalize()
   833  
   834  		xAndYCells := CellUnionFromIntersection(xcells, ycells)
   835  		if !xAndYCells.Equal(xAndYExpected) {
   836  			t.Errorf("CellUnionFromIntersection(%v, %v) = %v, want %v", xcells, ycells, xAndYCells, xAndYExpected)
   837  		}
   838  
   839  		xMinusYCells := CellUnionFromDifference(xcells, ycells)
   840  		yMinusXCells := CellUnionFromDifference(ycells, xcells)
   841  		if !xcells.Contains(xMinusYCells) {
   842  			t.Errorf("%v.Contains(%v) = false, want true", xcells, xMinusYCells)
   843  		}
   844  		if xMinusYCells.Intersects(ycells) {
   845  			t.Errorf("%v.Intersects(%v) = true, want false", xMinusYCells, ycells)
   846  		}
   847  		if !ycells.Contains(yMinusXCells) {
   848  			t.Errorf("%v.Contains(%v) = false, want true", ycells, yMinusXCells)
   849  		}
   850  		if yMinusXCells.Intersects(xcells) {
   851  			t.Errorf("%v.Intersects(%v) = true, want false", yMinusXCells, xcells)
   852  		}
   853  		if xMinusYCells.Intersects(yMinusXCells) {
   854  			t.Errorf("%v.Intersects(%v) = true, want false", xMinusYCells, yMinusXCells)
   855  		}
   856  
   857  		diffUnion := CellUnionFromUnion(xMinusYCells, yMinusXCells)
   858  		diffIntersectionUnion := CellUnionFromUnion(diffUnion, xAndYCells)
   859  		if !diffIntersectionUnion.Equal(xOrYCells) {
   860  			t.Errorf("Union(%v, %v).Union(%v) = %v, want %v", xMinusYCells, yMinusXCells, xAndYCells, diffIntersectionUnion, xOrYCells)
   861  		}
   862  	}
   863  }
   864  
   865  // cellUnionDistanceFromAxis returns the maximum geodesic distance from axis to any point of
   866  // the given CellUnion.
   867  func cellUnionDistanceFromAxis(cu CellUnion, axis Point) float64 {
   868  	var maxDist float64
   869  	for _, cid := range cu {
   870  		cell := CellFromCellID(cid)
   871  		for j := 0; j < 4; j++ {
   872  			a := cell.Vertex(j)
   873  			b := cell.Vertex((j + 1) & 3)
   874  			var dist float64
   875  			// The maximum distance is not always attained at a cell vertex: if at
   876  			// least one vertex is in the opposite hemisphere from axis then the
   877  			// maximum may be attained along an edge. We solve this by computing
   878  			// the minimum distance from the edge to (-axis) instead. We can't
   879  			// simply do this all the time because DistanceFromSegment() has
   880  			// poor accuracy when the result is close to Pi.
   881  			//
   882  			// TODO: Improve edgeutil's DistanceFromSegment accuracy near Pi.
   883  			if a.Angle(axis.Vector) > math.Pi/2 || b.Angle(axis.Vector) > math.Pi/2 {
   884  				dist = math.Pi - DistanceFromSegment(Point{axis.Mul(-1)}, a, b).Radians()
   885  			} else {
   886  				dist = float64(a.Angle(axis.Vector))
   887  			}
   888  			maxDist = math.Max(maxDist, dist)
   889  		}
   890  	}
   891  	return maxDist
   892  }
   893  
   894  func TestCellUnionExpand(t *testing.T) {
   895  	// This test generates coverings for caps of random sizes, expands
   896  	// the coverings by a random radius, and then make sure that the new
   897  	// covering covers the expanded cap.  It also makes sure that the
   898  	// new covering is not too much larger than expected.
   899  	for i := 0; i < 5000; i++ {
   900  		rndCap := randomCap(AvgAreaMetric.Value(MaxLevel), 4*math.Pi)
   901  
   902  		// Expand the cap area by a random factor whose log is uniformly
   903  		// distributed between 0 and log(1e2).
   904  		expandedCap := CapFromCenterHeight(
   905  			rndCap.center, math.Min(2.0, math.Pow(1e2, randomFloat64())*rndCap.Height()))
   906  
   907  		radius := (expandedCap.Radius() - rndCap.Radius()).Radians()
   908  		maxLevelDiff := randomUniformInt(8)
   909  
   910  		// Generate a covering for the original cap, and measure the maximum
   911  		// distance from the cap center to any point in the covering.
   912  		coverer := &RegionCoverer{
   913  			MaxLevel: MaxLevel,
   914  			MaxCells: 1 + skewedInt(10),
   915  			LevelMod: 1,
   916  		}
   917  		covering := coverer.CellUnion(rndCap)
   918  		checkCellUnionCovering(t, rndCap, covering, true, 0)
   919  		coveringRadius := cellUnionDistanceFromAxis(covering, rndCap.center)
   920  
   921  		// This code duplicates the logic in Expand(min_radius, max_level_diff)
   922  		// that figures out an appropriate cell level to use for the expansion.
   923  		minLevel := MaxLevel
   924  		for _, cid := range covering {
   925  			minLevel = minInt(minLevel, cid.Level())
   926  		}
   927  		expandLevel := minInt(minLevel+maxLevelDiff, MinWidthMetric.MaxLevel(radius))
   928  
   929  		// Generate a covering for the expanded cap, and measure the new maximum
   930  		// distance from the cap center to any point in the covering.
   931  		covering.ExpandByRadius(s1.Angle(radius), maxLevelDiff)
   932  		checkCellUnionCovering(t, expandedCap, covering, false, 0)
   933  		expandedCoveringRadius := cellUnionDistanceFromAxis(covering, rndCap.center)
   934  
   935  		// If the covering includes a tiny cell along the boundary, in theory the
   936  		// maximum angle of the covering from the cap center can increase by up to
   937  		// twice the maximum length of a cell diagonal.
   938  		if expandedCoveringRadius-coveringRadius >= 2*MaxDiagMetric.Value(expandLevel) {
   939  			t.Errorf("covering.ExpandByRadius(%v, %v) distance from center = %v want < %v", radius, maxLevelDiff, expandedCoveringRadius-coveringRadius, 2*MaxDiagMetric.Value(expandLevel))
   940  		}
   941  	}
   942  }
   943  
   944  // checkCellUnionCovering checks that the given covering completely covers the given region.
   945  // If checkTight is true, it also checks that it does not contain any cells that do not
   946  // intersect the given region. The id is the CellID to start at for the checks. If an
   947  // invalid value is used as the ID, then all faces are checked.
   948  func checkCellUnionCovering(t *testing.T, r Region, covering CellUnion, checkTight bool, id CellID) {
   949  	if !id.IsValid() {
   950  		for face := 0; face < 6; face++ {
   951  			checkCellUnionCovering(t, r, covering, checkTight, CellIDFromFace(face))
   952  		}
   953  		return
   954  	}
   955  
   956  	if !r.IntersectsCell(CellFromCellID(id)) {
   957  		// If region does not intersect the id, then neither should the covering.
   958  		if checkTight {
   959  			if covering.IntersectsCellID(id) {
   960  				t.Errorf("%v.IntersectsCellID(%v) = true, want false", covering, id)
   961  			}
   962  		}
   963  		return
   964  	}
   965  	if !covering.ContainsCellID(id) {
   966  		// The region may intersect id, but we can't assert that the covering
   967  		// intersects id because we may discover that the region does not actually
   968  		// intersect upon further subdivision.  (IntersectsCell is not exact.)
   969  		if r.ContainsCell(CellFromCellID(id)) {
   970  			t.Errorf("%v.ContainsCell(%v) = true, want false", r, id)
   971  			return
   972  		}
   973  		if id.IsLeaf() {
   974  			t.Errorf("%v.IsLeaf() = true, want false", id)
   975  			return
   976  		}
   977  		for child := id.ChildBegin(); child != id.ChildEnd(); child = child.Next() {
   978  			checkCellUnionCovering(t, r, covering, checkTight, child)
   979  		}
   980  	}
   981  }
   982  
   983  func TestCellUnionEmpty(t *testing.T) {
   984  	var empty CellUnion
   985  
   986  	// Normalize()
   987  	empty.Normalize()
   988  	if len(empty) != 0 {
   989  		t.Errorf("len(empty.Normalize()) = %d, want 0", len(empty))
   990  	}
   991  
   992  	// Denormalize(...)
   993  	empty.Denormalize(0, 2)
   994  	if len(empty) != 0 {
   995  		t.Errorf("len(empty.Denormalize(0, 2)) = %d, want 0", len(empty))
   996  	}
   997  
   998  	face1ID := CellIDFromFace(1)
   999  	// Contains(...)
  1000  	if empty.ContainsCellID(face1ID) {
  1001  		t.Errorf("empty.ContainsCellID(%v) = true, want false", face1ID)
  1002  	}
  1003  	if !empty.Contains(empty) {
  1004  		t.Errorf("empty.Contains(%v) = false, want true", empty)
  1005  	}
  1006  
  1007  	// Intersects(...)
  1008  	if empty.IntersectsCellID(face1ID) {
  1009  		t.Errorf("empty.IntersectsCellID(%v) = true, want false", face1ID)
  1010  	}
  1011  	if empty.Intersects(empty) {
  1012  		t.Errorf("empty.Intersects(%v) = true, want false", empty)
  1013  	}
  1014  
  1015  	// Union(...)
  1016  	cellUnion := CellUnionFromUnion(empty, empty)
  1017  	if len(cellUnion) != 0 {
  1018  		t.Errorf("CellUnionFromUnion(empty, empty) has %v cells, want 0", len(cellUnion))
  1019  	}
  1020  
  1021  	// Intersection(...)
  1022  	intersection := CellUnionFromIntersectionWithCellID(empty, face1ID)
  1023  	if len(intersection) != 0 {
  1024  		t.Errorf("CellUnionFromIntersectionWithCellID(%v, %v) = %v cells, want 0", empty, face1ID, len(intersection))
  1025  	}
  1026  
  1027  	intersection = CellUnionFromIntersection(empty, empty)
  1028  	if len(intersection) != 0 {
  1029  		t.Errorf("CellUnionFromIntersection(%v, %v) = %v cells, want 0", empty, empty, len(intersection))
  1030  	}
  1031  
  1032  	// Difference(...)
  1033  	difference := CellUnionFromDifference(empty, empty)
  1034  	if len(difference) != 0 {
  1035  		t.Errorf("CellUnionFromDifference(%v, %v) = %v cells, want 0", empty, empty, len(difference))
  1036  	}
  1037  
  1038  	// Expand(...)
  1039  	empty.ExpandByRadius(s1.Angle(1), 20)
  1040  	if len(empty) != 0 {
  1041  		t.Errorf("empty.ExpandByRadius(1, 20) = %v cells, want 0", len(empty))
  1042  	}
  1043  
  1044  	empty.ExpandAtLevel(10)
  1045  	if len(empty) != 0 {
  1046  		t.Errorf("empty.ExpandAtLevel(10) = %v cells, want 0", len(empty))
  1047  	}
  1048  }
  1049  
  1050  func BenchmarkCellUnionFromRange(b *testing.B) {
  1051  	x := CellIDFromFace(0).ChildBeginAtLevel(MaxLevel)
  1052  	y := CellIDFromFace(5).ChildEndAtLevel(MaxLevel)
  1053  	for i := 0; i < b.N; i++ {
  1054  		CellUnionFromRange(x, y)
  1055  	}
  1056  }
  1057  

View as plain text