shapeindex_region_test.go

Documentation: github.com/golang/geo/s2

     1  // Copyright 2023 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  	"testing"
    19  )
    20  
    21  // set padding to at least twice the maximum error for reliable results.
    22  const shapeIndexCellPadding = 2 * (faceClipErrorUVCoord + intersectsRectErrorUVDist)
    23  
    24  func padCell(id CellID, paddingUV float64) Shape {
    25  	face, i, j, _ := id.faceIJOrientation()
    26  
    27  	uv := ijLevelToBoundUV(i, j, id.Level()).ExpandedByMargin(paddingUV)
    28  
    29  	vertices := make([]Point, 4)
    30  	for i, v := range uv.Vertices() {
    31  		vertices[i] = Point{faceUVToXYZ(face, v.X, v.Y).Normalize()}
    32  	}
    33  
    34  	return LaxLoopFromPoints(vertices)
    35  }
    36  
    37  func TestShapeIndexRegionCapBound(t *testing.T) {
    38  	id := CellIDFromString("3/0123012301230123012301230123")
    39  
    40  	// Add a polygon that is slightly smaller than the cell being tested.
    41  	index := NewShapeIndex()
    42  	index.Add(padCell(id, -shapeIndexCellPadding))
    43  
    44  	cellBound := CellFromCellID(id).CapBound()
    45  	indexBound := index.Region().CapBound()
    46  	if !indexBound.Contains(cellBound) {
    47  		t.Errorf("%v.Contains(%v) = false, want true", indexBound, cellBound)
    48  	}
    49  
    50  	// Note that CellUnion.CapBound returns a slightly larger bound than
    51  	// Cell.CapBound even when the cell union consists of a single CellID.
    52  	if got, want := indexBound.Radius(), 1.00001*cellBound.Radius(); got > want {
    53  		t.Errorf("%v.CapBound.Radius() = %v, want %v", index, got, want)
    54  	}
    55  }
    56  
    57  func TestShapeIndexRegionRectBound(t *testing.T) {
    58  	id := CellIDFromString("3/0123012301230123012301230123")
    59  
    60  	// Add a polygon that is slightly smaller than the cell being tested.
    61  	index := NewShapeIndex()
    62  	index.Add(padCell(id, -shapeIndexCellPadding))
    63  	cellBound := CellFromCellID(id).RectBound()
    64  	indexBound := index.Region().RectBound()
    65  
    66  	if indexBound != cellBound {
    67  		t.Errorf("%v.RectBound() = %v, want %v", index, indexBound, cellBound)
    68  	}
    69  }
    70  
    71  func TestShapeIndexRegionCellUnionBoundMultipleFaces(t *testing.T) {
    72  	have := []CellID{
    73  		CellIDFromString("3/00123"),
    74  		CellIDFromString("2/11200013"),
    75  	}
    76  
    77  	index := NewShapeIndex()
    78  	for _, id := range have {
    79  		index.Add(padCell(id, -shapeIndexCellPadding))
    80  	}
    81  
    82  	got := index.Region().CellUnionBound()
    83  
    84  	sortCellIDs(have)
    85  
    86  	if !CellUnion(have).Equal(CellUnion(got)) {
    87  		t.Errorf("%v.CellUnionBound() = %v, want %v", index, got, have)
    88  	}
    89  }
    90  
    91  func TestShapeIndexRegionCellUnionBoundOneFace(t *testing.T) {
    92  	// This tests consists of 3 pairs of CellIDs.  Each pair is located within
    93  	// one of the children of face 5, namely the cells 5/0, 5/1, and 5/3.
    94  	// We expect CellUnionBound to compute the smallest cell that bounds the
    95  	// pair on each face.
    96  	have := []CellID{
    97  		CellIDFromString("5/010"),
    98  		CellIDFromString("5/0211030"),
    99  		CellIDFromString("5/110230123"),
   100  		CellIDFromString("5/11023021133"),
   101  		CellIDFromString("5/311020003003030303"),
   102  		CellIDFromString("5/311020023"),
   103  	}
   104  
   105  	want := []CellID{
   106  		CellIDFromString("5/0"),
   107  		CellIDFromString("5/110230"),
   108  		CellIDFromString("5/3110200"),
   109  	}
   110  
   111  	index := NewShapeIndex()
   112  	for _, id := range have {
   113  		// Add each shape 3 times to ensure that the ShapeIndex subdivides.
   114  		index.Add(padCell(id, -shapeIndexCellPadding))
   115  		index.Add(padCell(id, -shapeIndexCellPadding))
   116  		index.Add(padCell(id, -shapeIndexCellPadding))
   117  	}
   118  
   119  	sortCellIDs(have)
   120  
   121  	got := index.Region().CellUnionBound()
   122  	if !CellUnion(want).Equal(CellUnion(got)) {
   123  		t.Errorf("%v.CellUnionBound() = %v, want %v", index, got, want)
   124  	}
   125  }
   126  
   127  // TODO(roberts): remaining tests
   128  // func TestShapeIndexRegionContainsCellMultipleShapes(t *testing.T) { }
   129  // func TestShapeIndexRegionIntersectsShrunkenCell(t *testing.T){ }
   130  // func TestShapeIndexRegionIntersectsExactCell(t *testing.T){ }
   131  // Add VisitIntersectingShapes tests
   132  // Benchmarks
   133
View as plain text