regioncoverer_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  	"math/rand"
    21  	"reflect"
    22  	"testing"
    23  )
    24  
    25  func TestCovererRandomCells(t *testing.T) {
    26  	rc := &RegionCoverer{MinLevel: 0, MaxLevel: 30, LevelMod: 1, MaxCells: 1}
    27  
    28  	// Test random cell ids at all levels.
    29  	for i := 0; i < 10000; i++ {
    30  		id := randomCellID()
    31  		covering := rc.Covering(Region(CellFromCellID(id)))
    32  		if len(covering) != 1 {
    33  			t.Errorf("Iteration %d, cell ID token %s, got covering size = %d, want covering size = 1", i, id.ToToken(), len(covering))
    34  			// if the covering isn't len 1, the next check will panic
    35  			break
    36  		}
    37  		if (covering)[0] != id {
    38  			t.Errorf("Iteration %d, cell ID token %s, got covering = %v, want covering = %v", i, id.ToToken(), covering, id)
    39  		}
    40  	}
    41  }
    42  
    43  // checkCovering reports whether covering is a valid cover for the region.
    44  func checkCovering(t *testing.T, rc *RegionCoverer, r Region, covering CellUnion, interior bool) {
    45  	// Keep track of how many cells have the same rc.MinLevel ancestor.
    46  	minLevelCells := map[CellID]int{}
    47  	var tempCover CellUnion
    48  	for _, ci := range covering {
    49  		level := ci.Level()
    50  		if level < rc.MinLevel {
    51  			t.Errorf("CellID(%s).Level() = %d, want >= %d", ci.ToToken(), level, rc.MinLevel)
    52  		}
    53  		if level > rc.MaxLevel {
    54  			t.Errorf("CellID(%s).Level() = %d, want <= %d", ci.ToToken(), level, rc.MaxLevel)
    55  		}
    56  		if rem := (level - rc.MinLevel) % rc.LevelMod; rem != 0 {
    57  			t.Errorf("(CellID(%s).Level() - MinLevel) mod LevelMod = %d, want = %d", ci.ToToken(), rem, 0)
    58  		}
    59  		tempCover = append(tempCover, ci)
    60  		minLevelCells[ci.Parent(rc.MinLevel)]++
    61  	}
    62  	if len(covering) > rc.MaxCells {
    63  		// If the covering has more than the requested number of cells, then check
    64  		// that the cell count cannot be reduced by using the parent of some cell.
    65  		for ci, count := range minLevelCells {
    66  			if count > 1 {
    67  				t.Errorf("Min level CellID %s, count = %d, want = %d", ci.ToToken(), count, 1)
    68  			}
    69  		}
    70  	}
    71  	if interior {
    72  		for _, ci := range covering {
    73  			if !r.ContainsCell(CellFromCellID(ci)) {
    74  				t.Errorf("Region(%v).ContainsCell(%v) = %t, want = %t", r, CellFromCellID(ci), false, true)
    75  			}
    76  		}
    77  	} else {
    78  		tempCover.Normalize()
    79  		checkCoveringTight(t, r, tempCover, true, 0)
    80  	}
    81  }
    82  
    83  // checkCoveringTight checks that "cover" completely covers the given region.
    84  // If "checkTight" is true, also checks that it does not contain any cells that
    85  // do not intersect the given region. ("id" is only used internally.)
    86  func checkCoveringTight(t *testing.T, r Region, cover CellUnion, checkTight bool, id CellID) {
    87  	if !id.IsValid() {
    88  		for f := 0; f < 6; f++ {
    89  			checkCoveringTight(t, r, cover, checkTight, CellIDFromFace(f))
    90  		}
    91  		return
    92  	}
    93  
    94  	if !r.IntersectsCell(CellFromCellID(id)) {
    95  		// If region does not intersect id, then neither should the covering.
    96  		if got := cover.IntersectsCellID(id); checkTight && got {
    97  			t.Errorf("CellUnion(%v).IntersectsCellID(%s) = %t; want = %t", cover, id.ToToken(), got, false)
    98  		}
    99  	} else if !cover.ContainsCellID(id) {
   100  		// The region may intersect id, but we can't assert that the covering
   101  		// intersects id because we may discover that the region does not actually
   102  		// intersect upon further subdivision.  (IntersectsCell is not exact.)
   103  		if got := r.ContainsCell(CellFromCellID(id)); got {
   104  			t.Errorf("Region(%v).ContainsCell(%v) = %t; want = %t", r, CellFromCellID(id), got, false)
   105  		}
   106  		if got := id.IsLeaf(); got {
   107  			t.Errorf("CellID(%s).IsLeaf() = %t; want = %t", id.ToToken(), got, false)
   108  		}
   109  
   110  		for child := id.ChildBegin(); child != id.ChildEnd(); child = child.Next() {
   111  			checkCoveringTight(t, r, cover, checkTight, child)
   112  		}
   113  	}
   114  }
   115  
   116  func TestCovererRandomCaps(t *testing.T) {
   117  	rc := &RegionCoverer{MinLevel: 0, MaxLevel: 30, LevelMod: 1, MaxCells: 1}
   118  	for i := 0; i < 1000; i++ {
   119  		rc.MinLevel = int(rand.Int31n(MaxLevel + 1))
   120  		rc.MaxLevel = int(rand.Int31n(MaxLevel + 1))
   121  		for rc.MinLevel > rc.MaxLevel {
   122  			rc.MinLevel = int(rand.Int31n(MaxLevel + 1))
   123  			rc.MaxLevel = int(rand.Int31n(MaxLevel + 1))
   124  		}
   125  		rc.LevelMod = int(1 + rand.Int31n(3))
   126  		rc.MaxCells = skewedInt(10)
   127  
   128  		maxArea := math.Min(4*math.Pi, float64(3*rc.MaxCells+1)*AvgAreaMetric.Value(rc.MinLevel))
   129  		r := Region(randomCap(0.1*AvgAreaMetric.Value(MaxLevel), maxArea))
   130  
   131  		covering := rc.Covering(r)
   132  		checkCovering(t, rc, r, covering, false)
   133  		interior := rc.InteriorCovering(r)
   134  		checkCovering(t, rc, r, interior, true)
   135  
   136  		// Check that Covering is deterministic.
   137  		covering2 := rc.Covering(r)
   138  		if !reflect.DeepEqual(covering, covering2) {
   139  			t.Errorf("Iteration %d, got covering = %v, want covering = %v", i, covering2, covering)
   140  		}
   141  
   142  		// Also check Denormalize. The denormalized covering
   143  		// may still be different and smaller than "covering" because
   144  		// s2.RegionCoverer does not guarantee that it will not output all four
   145  		// children of the same parent.
   146  		covering.Denormalize(rc.MinLevel, rc.LevelMod)
   147  		checkCovering(t, rc, r, covering, false)
   148  	}
   149  }
   150  
   151  func TestRegionCovererInteriorCovering(t *testing.T) {
   152  	// We construct the region the following way. Start with Cell of level l.
   153  	// Remove from it one of its grandchildren (level l+2). If we then set
   154  	//   minLevel < l + 1
   155  	//   MaxLevel > l + 2
   156  	//   maxCells = 3
   157  	// the best interior covering should contain 3 children of the initial cell,
   158  	// that were not effected by removal of a grandchild.
   159  	const level = 12
   160  	smallCell := cellIDFromPoint(randomPoint()).Parent(level + 2)
   161  	largeCell := smallCell.Parent(level)
   162  
   163  	smallCellUnion := CellUnion([]CellID{smallCell})
   164  	largeCellUnion := CellUnion([]CellID{largeCell})
   165  	diff := CellUnionFromDifference(largeCellUnion, smallCellUnion)
   166  
   167  	coverer := &RegionCoverer{
   168  		MaxCells: 3,
   169  		MaxLevel: level + 3,
   170  		MinLevel: level,
   171  	}
   172  
   173  	interior := coverer.InteriorCovering(&diff)
   174  	if len(interior) != 3 {
   175  		t.Fatalf("len(coverer.InteriorCovering(%v)) = %v, want 3", diff, len(interior))
   176  	}
   177  	for i := 0; i < 3; i++ {
   178  		if got, want := interior[i].Level(), level+1; got != want {
   179  			t.Errorf("interior[%d].Level() = %v, want %v", i, got, want)
   180  		}
   181  	}
   182  }
   183  
   184  func TestRegionCovererSimpleRegionCovering(t *testing.T) {
   185  	const MaxLevel = MaxLevel
   186  	for i := 0; i < 100; i++ {
   187  		level := randomUniformInt(MaxLevel + 1)
   188  		maxArea := math.Min(4*math.Pi, 1000.0*AvgAreaMetric.Value(level))
   189  		c := randomCap(0.1*AvgAreaMetric.Value(MaxLevel), maxArea)
   190  		covering := SimpleRegionCovering(c, c.Center(), level)
   191  		rc := &RegionCoverer{MaxLevel: level, MinLevel: level, MaxCells: math.MaxInt32, LevelMod: 1}
   192  		checkCovering(t, rc, c, covering, false)
   193  	}
   194  }
   195  
   196  func TestRegionCovererIsCanonical(t *testing.T) {
   197  	tests := []struct {
   198  		cells []string
   199  		cov   *RegionCoverer
   200  		want  bool
   201  	}{
   202  		// InvalidCellID
   203  		{cells: []string{"1/"}, cov: NewRegionCoverer(), want: true},
   204  		{cells: []string{"invalid"}, cov: NewRegionCoverer(), want: false},
   205  		// Unsorted
   206  		{cells: []string{"1/1", "1/3"}, cov: NewRegionCoverer(), want: true},
   207  		{cells: []string{"1/3", "1/1"}, cov: NewRegionCoverer(), want: false},
   208  
   209  		// Overlapping
   210  		{cells: []string{"1/2", "1/33"}, cov: NewRegionCoverer(), want: true},
   211  		{cells: []string{"1/3", "1/33"}, cov: NewRegionCoverer(), want: false},
   212  
   213  		// MinLevel
   214  		{
   215  			cells: []string{"1/31"},
   216  			cov:   &RegionCoverer{MinLevel: 2, MaxLevel: 30, LevelMod: 1, MaxCells: 8},
   217  			want:  true,
   218  		},
   219  		{
   220  			cells: []string{"1/3"},
   221  			cov:   &RegionCoverer{MinLevel: 2, MaxLevel: 30, LevelMod: 1, MaxCells: 8},
   222  			want:  false,
   223  		},
   224  
   225  		// MaxLevel
   226  		{
   227  			cells: []string{"1/31"},
   228  			cov:   &RegionCoverer{MinLevel: 0, MaxLevel: 2, LevelMod: 1, MaxCells: 8},
   229  			want:  true,
   230  		},
   231  		{
   232  			cells: []string{"1/312"},
   233  			cov:   &RegionCoverer{MinLevel: 0, MaxLevel: 2, LevelMod: 1, MaxCells: 8},
   234  			want:  false,
   235  		},
   236  
   237  		// LevelMod
   238  		{
   239  			cells: []string{"1/31"},
   240  			cov:   &RegionCoverer{MinLevel: 0, MaxLevel: 30, LevelMod: 2, MaxCells: 8},
   241  			want:  true,
   242  		},
   243  		{
   244  			cells: []string{"1/312"},
   245  			cov:   &RegionCoverer{MinLevel: 0, MaxLevel: 30, LevelMod: 2, MaxCells: 8},
   246  			want:  false,
   247  		},
   248  
   249  		// MaxCells
   250  		{cells: []string{"1/1", "1/3"}, cov: &RegionCoverer{MinLevel: 0, MaxLevel: 30, LevelMod: 1, MaxCells: 2}, want: true},
   251  		{cells: []string{"1/1", "1/3", "2/"}, cov: &RegionCoverer{MinLevel: 0, MaxLevel: 30, LevelMod: 1, MaxCells: 2}, want: false},
   252  		{cells: []string{"1/123", "2/1", "3/0122"}, cov: &RegionCoverer{MinLevel: 0, MaxLevel: 30, LevelMod: 1, MaxCells: 2}, want: true},
   253  
   254  		// Normalized
   255  		// Test that no sequence of cells could be replaced by an ancestor.
   256  		{
   257  			cells: []string{"1/01", "1/02", "1/03", "1/10", "1/11"},
   258  			cov:   NewRegionCoverer(),
   259  			want:  true,
   260  		},
   261  		{
   262  			cells: []string{"1/00", "1/01", "1/02", "1/03", "1/10"},
   263  			cov:   NewRegionCoverer(),
   264  			want:  false,
   265  		},
   266  
   267  		{
   268  			cells: []string{"0/22", "1/01", "1/02", "1/03", "1/10"},
   269  			cov:   NewRegionCoverer(),
   270  			want:  true,
   271  		},
   272  		{
   273  			cells: []string{"0/22", "1/00", "1/01", "1/02", "1/03"},
   274  			cov:   NewRegionCoverer(),
   275  			want:  false,
   276  		},
   277  
   278  		{
   279  			cells: []string{"1/1101", "1/1102", "1/1103", "1/1110", "1/1111", "1/1112",
   280  				"1/1113", "1/1120", "1/1121", "1/1122", "1/1123", "1/1130",
   281  				"1/1131", "1/1132", "1/1133", "1/1200"},
   282  			cov:  &RegionCoverer{MinLevel: 0, MaxLevel: 30, LevelMod: 2, MaxCells: 20},
   283  			want: true,
   284  		},
   285  		{
   286  			cells: []string{"1/1100", "1/1101", "1/1102", "1/1103", "1/1110", "1/1111",
   287  				"1/1112", "1/1113", "1/1120", "1/1121", "1/1122", "1/1123",
   288  				"1/1130", "1/1131", "1/1132", "1/1133"},
   289  			cov:  &RegionCoverer{MinLevel: 0, MaxLevel: 30, LevelMod: 2, MaxCells: 20},
   290  			want: false,
   291  		},
   292  	}
   293  	for _, test := range tests {
   294  		cu := makeCellUnion(test.cells...)
   295  		if got := test.cov.IsCanonical(cu); got != test.want {
   296  			t.Errorf("IsCanonical(%v) = %t, want %t", cu, got, test.want)
   297  		}
   298  	}
   299  }
   300  
   301  const numCoveringBMRegions = 1000
   302  
   303  func BenchmarkRegionCovererCoveringCap(b *testing.B) {
   304  	benchmarkRegionCovererCovering(b, func(n int) string {
   305  		return fmt.Sprintf("Cap%d", n)
   306  	},
   307  		func(n int) []Region {
   308  			regions := make([]Region, numCoveringBMRegions)
   309  			for i := 0; i < numCoveringBMRegions; i++ {
   310  				regions[i] = randomCap(0.1*AvgAreaMetric.Value(MaxLevel), 4*math.Pi)
   311  			}
   312  			return regions
   313  		})
   314  }
   315  
   316  func BenchmarkRegionCovererCoveringCell(b *testing.B) {
   317  	benchmarkRegionCovererCovering(b, func(n int) string {
   318  		return fmt.Sprintf("Cell%d", n)
   319  	},
   320  		func(n int) []Region {
   321  			regions := make([]Region, numCoveringBMRegions)
   322  			for i := 0; i < numCoveringBMRegions; i++ {
   323  				regions[i] = CellFromCellID(randomCellIDForLevel(MaxLevel - randomUniformInt(n)))
   324  			}
   325  			return regions
   326  		})
   327  }
   328  
   329  func BenchmarkRegionCovererCoveringLoop(b *testing.B) {
   330  	benchmarkRegionCovererCovering(b, func(n int) string {
   331  		return fmt.Sprintf("Loop-%d-edges", int(math.Pow(2.0, float64(n))))
   332  	},
   333  		func(n int) []Region {
   334  			size := int(math.Pow(2.0, float64(n)))
   335  			regions := make([]Region, numCoveringBMRegions)
   336  			for i := 0; i < numCoveringBMRegions; i++ {
   337  				regions[i] = RegularLoop(randomPoint(), kmToAngle(10.0), size)
   338  			}
   339  			return regions
   340  		})
   341  }
   342  
   343  func BenchmarkRegionCovererCoveringCellUnion(b *testing.B) {
   344  	benchmarkRegionCovererCovering(b, func(n int) string {
   345  		return fmt.Sprintf("CellUnion-%d-cells", int(math.Pow(2.0, float64(n))))
   346  	},
   347  		func(n int) []Region {
   348  			size := int(math.Pow(2.0, float64(n)))
   349  			regions := make([]Region, numCoveringBMRegions)
   350  			for i := 0; i < numCoveringBMRegions; i++ {
   351  				cu := randomCellUnion(size)
   352  				regions[i] = &cu
   353  			}
   354  			return regions
   355  		})
   356  }
   357  
   358  // TODO(roberts): Add more benchmarking that changes the values in the coverer (min/max level, # cells).
   359  
   360  // benchmark Covering using the supplied func to generate a slice of random Regions of
   361  // the given type to choose from for the benchmark.
   362  //
   363  // e.g. Loops with [4..~2^n] edges, CellUnions of 2^n random Cells, random Cells and Caps
   364  func benchmarkRegionCovererCovering(b *testing.B, genLabel func(n int) string, genRegions func(n int) []Region) {
   365  	rc := &RegionCoverer{MinLevel: 0, MaxLevel: 30, LevelMod: 1, MaxCells: 8}
   366  
   367  	// Range over a variety of region complexities.
   368  	for n := 2; n <= 16; n++ {
   369  		b.Run(genLabel(n),
   370  			func(b *testing.B) {
   371  				b.StopTimer()
   372  				regions := genRegions(n)
   373  				l := len(regions)
   374  				b.StartTimer()
   375  				for i := 0; i < b.N; i++ {
   376  					rc.Covering(regions[i%l])
   377  				}
   378  			})
   379  	}
   380  }
   381  
   382  // TODO(roberts): Differences from C++
   383  //  func TestRegionCovererAccuracy(t *testing.T) {
   384  //  func TestRegionCovererFastCoveringHugeFixedLevelCovering(t *testing.T) {
   385  //  func TestRegionCovererCanonicalizeCoveringUnsortedDuplicateCells(t *testing.T) {
   386  //  func TestRegionCovererCanonicalizeCoveringMaxLevelExceeded(t *testing.T) {
   387  //  func TestRegionCovererCanonicalizeCoveringWrongLevelMod(t *testing.T) {
   388  //  func TestRegionCovererCanonicalizeCoveringReplacedByParent(t *testing.T) {
   389  //  func TestRegionCovererCanonicalizeCoveringDenormalizedCellUnion(t *testing.T) {
   390  //  func TestRegionCovererCanonicalizeCoveringMaxCellsMergesSmallest(t *testing.T) {
   391  //  func TestRegionCovererCanonicalizeCoveringMaxCellsMergesRepeatedly(t *testing.T) {
   392
View as plain text