paddedcell_test.go

Documentation: github.com/golang/geo/s2

     1  // Copyright 2016 Google Inc. All rights reserved.
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  package s2
    16  
    17  import (
    18  	"math"
    19  	"testing"
    20  
    21  	"github.com/golang/geo/r1"
    22  	"github.com/golang/geo/r2"
    23  )
    24  
    25  func TestPaddedCellMethods(t *testing.T) {
    26  	// Test the PaddedCell methods that have approximate Cell equivalents.
    27  	for i := 0; i < 1000; i++ {
    28  		cid := randomCellID()
    29  		padding := math.Pow(1e-15, randomFloat64())
    30  		cell := CellFromCellID(cid)
    31  		pCell := PaddedCellFromCellID(cid, padding)
    32  
    33  		if cell.id != pCell.id {
    34  			t.Errorf("%v.id = %v, want %v", pCell, pCell.id, cell.id)
    35  		}
    36  		if cell.id.Level() != pCell.Level() {
    37  			t.Errorf("%v.Level() = %v, want %v", pCell, pCell.Level(), cell.id.Level())
    38  		}
    39  
    40  		if padding != pCell.Padding() {
    41  			t.Errorf("%v.Padding() = %v, want %v", pCell, pCell.Padding(), padding)
    42  		}
    43  
    44  		if got, want := pCell.Bound(), cell.BoundUV().ExpandedByMargin(padding); got != want {
    45  			t.Errorf("%v.BoundUV() = %v, want %v", pCell, got, want)
    46  		}
    47  
    48  		r := r2.RectFromPoints(cell.id.centerUV()).ExpandedByMargin(padding)
    49  		if r != pCell.Middle() {
    50  			t.Errorf("%v.Middle() = %v, want %v", pCell, pCell.Middle(), r)
    51  		}
    52  
    53  		if cell.id.Point() != pCell.Center() {
    54  			t.Errorf("%v.Center() = %v, want %v", pCell, pCell.Center(), cell.id.Point())
    55  		}
    56  		if cid.IsLeaf() {
    57  			continue
    58  		}
    59  
    60  		children, ok := cell.Children()
    61  		if !ok {
    62  			t.Errorf("%v.Children() failed but should not have", cell)
    63  			continue
    64  		}
    65  		for pos := 0; pos < 4; pos++ {
    66  			i, j := pCell.ChildIJ(pos)
    67  
    68  			cellChild := children[pos]
    69  			pCellChild := PaddedCellFromParentIJ(pCell, i, j)
    70  			if cellChild.id != pCellChild.id {
    71  				t.Errorf("%v.id = %v, want %v", pCellChild, pCellChild.id, cellChild.id)
    72  			}
    73  			if cellChild.id.Level() != pCellChild.Level() {
    74  				t.Errorf("%v.Level() = %v, want %v", pCellChild, pCellChild.Level(), cellChild.id.Level())
    75  			}
    76  
    77  			if padding != pCellChild.Padding() {
    78  				t.Errorf("%v.Padding() = %v, want %v", pCellChild, pCellChild.Padding(), padding)
    79  			}
    80  
    81  			if got, want := pCellChild.Bound(), cellChild.BoundUV().ExpandedByMargin(padding); got != want {
    82  				t.Errorf("%v.BoundUV() = %v, want %v", pCellChild, got, want)
    83  			}
    84  
    85  			r := r2.RectFromPoints(cellChild.id.centerUV()).ExpandedByMargin(padding)
    86  			if got := pCellChild.Middle(); !r.ApproxEqual(got) {
    87  				t.Errorf("%v.Middle() = %v, want %v", pCellChild, got, r)
    88  			}
    89  
    90  			if cellChild.id.Point() != pCellChild.Center() {
    91  				t.Errorf("%v.Center() = %v, want %v", pCellChild, pCellChild.Center(), cellChild.id.Point())
    92  			}
    93  
    94  		}
    95  	}
    96  }
    97  
    98  func TestPaddedCellEntryExitVertices(t *testing.T) {
    99  	for i := 0; i < 1000; i++ {
   100  		id := randomCellID()
   101  		unpadded := PaddedCellFromCellID(id, 0)
   102  		padded := PaddedCellFromCellID(id, 0.5)
   103  
   104  		// Check that entry/exit vertices do not depend on padding.
   105  		if unpadded.EntryVertex() != padded.EntryVertex() {
   106  			t.Errorf("entry vertex should not depend on padding; %v != %v", unpadded.EntryVertex(), padded.EntryVertex())
   107  		}
   108  
   109  		if unpadded.ExitVertex() != padded.ExitVertex() {
   110  			t.Errorf("exit vertex should not depend on padding; %v != %v", unpadded.ExitVertex(), padded.ExitVertex())
   111  		}
   112  
   113  		// Check that the exit vertex of one cell is the same as the entry vertex
   114  		// of the immediately following cell. This also tests wrapping from the
   115  		// end to the start of the CellID curve with high probability.
   116  		if got := PaddedCellFromCellID(id.NextWrap(), 0).EntryVertex(); unpadded.ExitVertex() != got {
   117  			t.Errorf("PaddedCellFromCellID(%v.NextWrap(), 0).EntryVertex() = %v, want %v", id, got, unpadded.ExitVertex())
   118  		}
   119  
   120  		// Check that the entry vertex of a cell is the same as the entry vertex
   121  		// of its first child, and similarly for the exit vertex.
   122  		if id.IsLeaf() {
   123  			continue
   124  		}
   125  		if got := PaddedCellFromCellID(id.Children()[0], 0).EntryVertex(); unpadded.EntryVertex() != got {
   126  			t.Errorf("PaddedCellFromCellID(%v.Children()[0], 0).EntryVertex() = %v, want %v", id, got, unpadded.EntryVertex())
   127  		}
   128  		if got := PaddedCellFromCellID(id.Children()[3], 0).ExitVertex(); unpadded.ExitVertex() != got {
   129  			t.Errorf("PaddedCellFromCellID(%v.Children()[3], 0).ExitVertex() = %v, want %v", id, got, unpadded.ExitVertex())
   130  		}
   131  	}
   132  }
   133  
   134  func TestPaddedCellShrinkToFit(t *testing.T) {
   135  	for iter := 0; iter < 1000; iter++ {
   136  		// Start with the desired result and work backwards.
   137  		result := randomCellID()
   138  		resultUV := result.boundUV()
   139  		sizeUV := resultUV.Size()
   140  
   141  		// Find the biggest rectangle that fits in "result" after padding.
   142  		// (These calculations ignore numerical errors.)
   143  		maxPadding := 0.5 * math.Min(sizeUV.X, sizeUV.Y)
   144  		padding := maxPadding * randomFloat64()
   145  		maxRect := resultUV.ExpandedByMargin(-padding)
   146  
   147  		// Start with a random subset of the maximum rectangle.
   148  		a := r2.Point{
   149  			randomUniformFloat64(maxRect.X.Lo, maxRect.X.Hi),
   150  			randomUniformFloat64(maxRect.Y.Lo, maxRect.Y.Hi),
   151  		}
   152  		b := r2.Point{
   153  			randomUniformFloat64(maxRect.X.Lo, maxRect.X.Hi),
   154  			randomUniformFloat64(maxRect.Y.Lo, maxRect.Y.Hi),
   155  		}
   156  
   157  		if !result.IsLeaf() {
   158  			// If the result is not a leaf cell, we must ensure that no child of
   159  			// result also satisfies the conditions of ShrinkToFit().  We do this
   160  			// by ensuring that rect intersects at least two children of result
   161  			// (after padding).
   162  			useY := oneIn(2)
   163  			center := result.centerUV().X
   164  			if useY {
   165  				center = result.centerUV().Y
   166  			}
   167  
   168  			// Find the range of coordinates that are shared between child cells
   169  			// along that axis.
   170  			shared := r1.Interval{center - padding, center + padding}
   171  			if useY {
   172  				shared = shared.Intersection(maxRect.Y)
   173  			} else {
   174  				shared = shared.Intersection(maxRect.X)
   175  			}
   176  			mid := randomUniformFloat64(shared.Lo, shared.Hi)
   177  
   178  			if useY {
   179  				a.Y = randomUniformFloat64(maxRect.Y.Lo, mid)
   180  				b.Y = randomUniformFloat64(mid, maxRect.Y.Hi)
   181  			} else {
   182  				a.X = randomUniformFloat64(maxRect.X.Lo, mid)
   183  				b.X = randomUniformFloat64(mid, maxRect.X.Hi)
   184  			}
   185  		}
   186  		rect := r2.RectFromPoints(a, b)
   187  
   188  		// Choose an arbitrary ancestor as the PaddedCell.
   189  		initialID := result.Parent(randomUniformInt(result.Level() + 1))
   190  		pCell := PaddedCellFromCellID(initialID, padding)
   191  		if got := pCell.ShrinkToFit(rect); got != result {
   192  			t.Errorf("%v.ShrinkToFit(%v) = %v, want %v", pCell, rect, got, result)
   193  		}
   194  	}
   195  }
   196
View as plain text