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

Documentation: github.com/golang/geo/s2

     1  // Copyright 2019 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  	"reflect"
    19  	"sort"
    20  	"testing"
    21  
    22  	"github.com/golang/geo/s1"
    23  )
    24  
    25  func TestDistanceTargetMaxCellTargetCapBound(t *testing.T) {
    26  	var md maxDistance
    27  	zero := md.zero()
    28  
    29  	for i := 0; i < 100; i++ {
    30  		cell := CellFromCellID(randomCellID())
    31  		target := NewMaxDistanceToCellTarget(cell)
    32  		c := target.capBound()
    33  
    34  		for j := 0; j < 100; j++ {
    35  			pTest := randomPoint()
    36  			// Check points outside of cap to be away from maxDistance's zero().
    37  			if !c.ContainsPoint(pTest) {
    38  				if got := cell.MaxDistance(pTest); !zero.less(maxDistance(got)) {
    39  					t.Errorf("%v.MaxDistance(%v) = %v, want < %v", cell, pTest, got, zero)
    40  				}
    41  			}
    42  		}
    43  	}
    44  }
    45  
    46  func TestDistanceTargetMaxCellTargetUpdateDistance(t *testing.T) {
    47  	var ok bool
    48  
    49  	targetCell := CellFromCellID(cellIDFromPoint(parsePoint("0:1")))
    50  	target := NewMaxDistanceToCellTarget(targetCell)
    51  
    52  	dist0 := maxDistance(0)
    53  	dist10 := maxDistance(s1.ChordAngleFromAngle(s1.Angle(10) * s1.Degree))
    54  
    55  	// Update max distance target to point.
    56  	p := parsePoint("0:0")
    57  	if _, ok = target.updateDistanceToPoint(p, dist0); !ok {
    58  		t.Errorf("target.updateDistanceToPoint(%v, %v) should have succeeded", p, dist0)
    59  	}
    60  	if _, ok = target.updateDistanceToPoint(p, dist10); ok {
    61  		t.Errorf("target.updateDistanceToPoint(%v, %v) should have failed", p, dist10)
    62  	}
    63  
    64  	// Reset dist0 which was updated.
    65  	dist0 = maxDistance(0)
    66  	// Test for edges.
    67  	pts := parsePoints("0:2, 0:3")
    68  	edge := Edge{pts[0], pts[1]}
    69  	if _, ok := target.updateDistanceToEdge(edge, dist0); !ok {
    70  		t.Errorf("target.updateDistanceToEdge(%v, %v) should have succeeded", edge, dist0)
    71  	}
    72  	// Second call should fail.
    73  	if _, ok := target.updateDistanceToEdge(edge, dist10); ok {
    74  		t.Errorf("target.updateDistanceToEdge(%v, %v) should have failed", edge, dist10)
    75  	}
    76  
    77  	// Reset dist0 which was updated.
    78  	dist0 = maxDistance(0)
    79  	// Test for cell.
    80  	cell := CellFromCellID(cellIDFromPoint(parsePoint("0:0")))
    81  	if _, ok = target.updateDistanceToCell(cell, dist0); !ok {
    82  		t.Errorf("target.updateDistanceToCell(%v, %v) should have succeeded", cell, dist0)
    83  	}
    84  	// Leaf cell will be tiny compared to 10 degrees - expect no update.
    85  	if _, ok = target.updateDistanceToCell(cell, dist10); ok {
    86  		t.Errorf("target.updateDistanceToCell(%v, %v) should have failed", cell, dist10)
    87  	}
    88  }
    89  
    90  func TestDistanceTargetMaxCellTargetUpdateDistanceToCellAntipodal(t *testing.T) {
    91  	var maxDist maxDistance
    92  
    93  	p := parsePoint("0:0")
    94  	targetCell := CellFromCellID(cellIDFromPoint(p))
    95  	target := NewMaxDistanceToCellTarget(targetCell)
    96  	dist := maxDist.infinity()
    97  	cell := CellFromCellID(cellIDFromPoint(Point{p.Mul(-1)}))
    98  
    99  	// First call should pass.
   100  	dist0, ok := target.updateDistanceToCell(cell, dist)
   101  	if !ok {
   102  		t.Errorf("target.updateDistanceToCell(%v, %v) should have succeeded", cell, dist)
   103  	}
   104  	if dist0.chordAngle() != s1.StraightChordAngle {
   105  		t.Errorf("target.updateDistanceToCell() = %v, want %v", dist0.chordAngle(), s1.StraightChordAngle)
   106  	}
   107  	// Second call should fail.
   108  	if _, ok := target.updateDistanceToCell(cell, dist0); ok {
   109  		t.Errorf("target.updateDistanceToCell(%v, %v) should have failed", cell, dist0)
   110  	}
   111  }
   112  
   113  func TestDistanceTargetMaxCellTargetUpdateDistanceToCellWhenEqual(t *testing.T) {
   114  	var maxDist maxDistance
   115  
   116  	targetCell := CellFromCellID(cellIDFromPoint(parsePoint("0:1")))
   117  	target := NewMaxDistanceToCellTarget(targetCell)
   118  	dist := maxDist.infinity()
   119  	cell := CellFromCellID(cellIDFromPoint(parsePoint("0:0")))
   120  
   121  	// First call should pass.
   122  	dist0, ok := target.updateDistanceToCell(cell, dist)
   123  	if !ok {
   124  		t.Errorf("target.updateDistanceToCell(%v, %v) should have succeeded", cell, dist)
   125  	}
   126  	// Second call should fail.
   127  	if _, ok := target.updateDistanceToCell(cell, dist0); ok {
   128  		t.Errorf("target.updateDistanceToCell(%v, %v) should have failed", cell, dist0)
   129  	}
   130  }
   131  
   132  func TestDistanceTargetMaxCellTargetUpdateDistanceToEdgeWhenEqual(t *testing.T) {
   133  	var maxDist maxDistance
   134  
   135  	targetCell := CellFromCellID(cellIDFromPoint(parsePoint("0:1")))
   136  	target := NewMaxDistanceToCellTarget(targetCell)
   137  	dist := maxDist.infinity()
   138  	pts := parsePoints("0:-1, 0:1")
   139  	edge := Edge{pts[0], pts[1]}
   140  
   141  	// First call should pass.
   142  	dist0, ok := target.updateDistanceToEdge(edge, dist)
   143  	if !ok {
   144  		t.Errorf("target.updateDistanceToEdge(%v, %v) should have succeeded", edge, dist)
   145  	}
   146  	// Second call should fail.
   147  	if _, ok := target.updateDistanceToEdge(edge, dist0); ok {
   148  		t.Errorf("target.updateDistanceToEdge(%v, %v) should have failed", edge, dist0)
   149  	}
   150  }
   151  
   152  func TestDistanceTargetMaxCellTargetVisitContainingShapes(t *testing.T) {
   153  	index := makeShapeIndex("1:1 # 1:1, 2:2 # 0:0, 0:3, 3:0 | 6:6, 6:9, 9:6 | -1:-1, -1:5, 5:-1")
   154  	// Only shapes 2 and 4 should contain a very small cell near
   155  	// the antipode of 1:1.
   156  	targetCell := CellFromCellID(cellIDFromPoint(Point{parsePoint("1:1").Mul(-1)}))
   157  	target := NewMaxDistanceToCellTarget(targetCell)
   158  
   159  	if got, want := containingShapesForTarget(target, index, 1), []int{2}; !reflect.DeepEqual(got, want) {
   160  		t.Errorf("containingShapesForTarget(%v, %q, 1) = %+v, want %+v", target, shapeIndexDebugString(index), got, want)
   161  	}
   162  	if got, want := containingShapesForTarget(target, index, 5), []int{2, 4}; !reflect.DeepEqual(got, want) {
   163  		t.Errorf("containingShapesForTarget(%v, %q, 5) = %+v, want %+v", target, shapeIndexDebugString(index), got, want)
   164  	}
   165  
   166  	// For a larger antipodal cell that properly contains one or more index
   167  	// cells, all shapes that intersect the first such cell in S2CellId order are
   168  	// returned.  In the test below, this happens to again be the 1st and 3rd
   169  	// polygons (whose shape_ids are 2 and 4).
   170  	target2 := NewMaxDistanceToCellTarget(CellFromCellID(targetCell.ID().Parent(5)))
   171  	if got, want := containingShapesForTarget(target2, index, 5), []int{2, 4}; !reflect.DeepEqual(got, want) {
   172  		t.Errorf("containingShapesForTarget(%v, %q, 5) = %+v, want %+v", target2, shapeIndexDebugString(index), got, want)
   173  	}
   174  }
   175  
   176  func TestDistanceTargetMaxPointTargetUpdateDistance(t *testing.T) {
   177  	var ok bool
   178  	var dist0, dist10 distance
   179  	target := NewMaxDistanceToPointTarget(parsePoint("0:0"))
   180  	dist0 = maxDistance(0)
   181  	dist10 = maxDistance(s1.ChordAngleFromAngle(s1.Angle(10) * s1.Degree))
   182  
   183  	// Update max distance target to point.
   184  	p := parsePoint("1:0")
   185  	if dist0, ok = target.updateDistanceToPoint(p, dist0); !ok {
   186  		t.Errorf("target.updateDistanceToPoint(%v, %v) should have succeeded", p, dist0)
   187  	}
   188  	if got, want := dist0.chordAngle().Angle().Degrees(), 1.0; !float64Near(got, want, epsilon) {
   189  		t.Errorf("target.updateDistanceToPoint(%v, %v) = %v, want ~%v", p, dist0.chordAngle(), got, want)
   190  	}
   191  	if _, ok = target.updateDistanceToPoint(p, dist10); ok {
   192  		t.Errorf("target.updateDistanceToPoint(%v, %v) should have failed", p, dist0)
   193  
   194  	}
   195  
   196  	// Reset dist0 which was updated.
   197  	dist0 = maxDistance(0)
   198  	// Test for edges.
   199  	pts := parsePoints("0:-1, 0:1")
   200  	edge := Edge{pts[0], pts[1]}
   201  	if dist0, ok = target.updateDistanceToEdge(edge, dist0); !ok {
   202  		t.Errorf("target.updateDistanceToEdge(%v, %v) should have succeeded", edge, dist0)
   203  	}
   204  	if got, want := dist0.chordAngle().Angle().Degrees(), 1.0; !float64Near(got, want, epsilon) {
   205  		t.Errorf("target.updateDistanceToEdge(%v, %v) = %v, want ~%v", edge, dist0.chordAngle(), got, want)
   206  	}
   207  	if _, ok = target.updateDistanceToEdge(edge, dist10); ok {
   208  		t.Errorf("target.updateDistanceToEdge(%v, %v) should have failed", edge, dist10)
   209  	}
   210  
   211  	// Reset dist0 which was updated.
   212  	dist0 = maxDistance(0)
   213  	// Test for cell.
   214  	cell := CellFromCellID(cellIDFromPoint(parsePoint("0:0")))
   215  	if _, ok = target.updateDistanceToCell(cell, dist0); !ok {
   216  		t.Errorf("target.updateDistanceToCell(%v, %v) should have succeeded", cell, dist0)
   217  	}
   218  	// Leaf cell will be tiny compared to 10 degrees - expect no update.
   219  	if _, ok = target.updateDistanceToCell(cell, dist10); ok {
   220  		t.Errorf("target.updateDistanceToCell(%v, %v) should have failed", cell, dist10)
   221  	}
   222  }
   223  
   224  func TestDistanceTargetMaxPointTargetUpdateDistanceToCellWhenEqual(t *testing.T) {
   225  	var maxDist maxDistance
   226  
   227  	target := NewMaxDistanceToPointTarget(parsePoint("1:0"))
   228  	dist := maxDist.infinity()
   229  	cell := CellFromCellID(cellIDFromPoint(parsePoint("0:0")))
   230  
   231  	// First call should pass.
   232  	dist0, ok := target.updateDistanceToCell(cell, dist)
   233  	if !ok {
   234  		t.Errorf("target.updateDistanceToCell(%v, %v) should have succeeded", cell, dist)
   235  	}
   236  	// Second call should fail.
   237  	if _, ok := target.updateDistanceToCell(cell, dist0); ok {
   238  		t.Errorf("target.updateDistanceToCell(%v, %v) should have failed", cell, dist0)
   239  	}
   240  }
   241  
   242  func TestDistanceTargetMaxPointTargetUpdateDistanceToEdgeWhenEqual(t *testing.T) {
   243  	var maxDist maxDistance
   244  
   245  	// Verifies that UpdateDistance only returns true when the new distance
   246  	// is less than the old distance (not less than or equal to).
   247  	target := NewMaxDistanceToPointTarget(parsePoint("1:0"))
   248  	dist := maxDist.infinity()
   249  	pts := parsePoints("0:-1, 0:1")
   250  	edge := Edge{pts[0], pts[1]}
   251  
   252  	// First call should pass.
   253  	dist0, ok := target.updateDistanceToEdge(edge, dist)
   254  	if !ok {
   255  		t.Errorf("target.updateDistanceToEdge(%v, %v) should have succeeded", edge, dist)
   256  	}
   257  	// Second call should fail.
   258  	if _, ok := target.updateDistanceToEdge(edge, dist0); ok {
   259  		t.Errorf("target.updateDistanceToEdge(%v, %v) should have failed", edge, dist0)
   260  	}
   261  }
   262  
   263  func containingShapesForTarget(target distanceTarget, index *ShapeIndex, maxShapes int) []int {
   264  	shapeIDs := map[int32]bool{}
   265  	target.visitContainingShapes(index,
   266  		func(containingShape Shape, targetPoint Point) bool {
   267  			// TODO(roberts): Update this if Shapes get an ID.
   268  			shapeIDs[index.idForShape(containingShape)] = true
   269  			return len(shapeIDs) < maxShapes
   270  		})
   271  	var ids []int
   272  	for k := range shapeIDs {
   273  		ids = append(ids, int(k))
   274  	}
   275  	sort.Ints(ids)
   276  	return ids
   277  }
   278  
   279  func TestDistanceTargetMaxPointTargetVisitContainingShapes(t *testing.T) {
   280  	// Only shapes 2 and 4 should contain the target point.
   281  	index := makeShapeIndex("1:1 # 1:1, 2:2 # 0:0, 0:3, 3:0 | 6:6, 6:9, 9:6 | 0:0, 0:4, 4:0")
   282  
   283  	// Test against antipodal point.
   284  	point := Point{parsePoint("1:1").Mul(-1)}
   285  	target := NewMaxDistanceToPointTarget(point)
   286  
   287  	if got, want := containingShapesForTarget(target, index, 1), []int{2}; !reflect.DeepEqual(got, want) {
   288  		t.Errorf("containingShapesForTarget(%v, %q, 1) = %+v, want %+v", point, shapeIndexDebugString(index), got, want)
   289  	}
   290  	if got, want := containingShapesForTarget(target, index, 5), []int{2, 4}; !reflect.DeepEqual(got, want) {
   291  		t.Errorf("containingShapesForTarget(%v, %q, 5) = %+v, want %+v", point, shapeIndexDebugString(index), got, want)
   292  	}
   293  }
   294  
   295  func TestDistanceTargetMaxEdgeTargetUpdateDistance(t *testing.T) {
   296  	var ok bool
   297  	var dist0, dist10 distance
   298  
   299  	targetPts := parsePoints("0:-1, 0:1")
   300  	targetEdge := Edge{targetPts[0], targetPts[1]}
   301  	target := NewMaxDistanceToEdgeTarget(targetEdge)
   302  
   303  	dist0 = maxDistance(0)
   304  	dist10 = maxDistance(s1.ChordAngleFromAngle(s1.Angle(10) * s1.Degree))
   305  
   306  	// Update max distance target to point.
   307  	p := parsePoint("0:2")
   308  	if dist0, ok = target.updateDistanceToPoint(p, dist0); !ok {
   309  		t.Errorf("target.updateDistanceToPoint(%v, %v) should have succeeded", p, dist0)
   310  	}
   311  	if got, want := dist0.chordAngle().Angle().Degrees(), 3.0; !float64Near(got, want, epsilon) {
   312  		t.Errorf("target.updateDistanceToPoint(%v, %v) = %v, want ~%v", p, dist0.chordAngle(), got, want)
   313  	}
   314  	if _, ok = target.updateDistanceToPoint(p, dist10); ok {
   315  		t.Errorf("target.updateDistanceToPoint(%v, %v) should have failed", p, dist10)
   316  	}
   317  
   318  	// Reset dist0 which was updated.
   319  	dist0 = maxDistance(0)
   320  	// Test for edges.
   321  	pts := parsePoints("0:2, 0:3")
   322  	edge := Edge{pts[0], pts[1]}
   323  	if dist0, ok = target.updateDistanceToEdge(edge, dist0); !ok {
   324  		t.Errorf("target.updateDistanceToEdge(%v, %v) should have succeeded", edge, dist0)
   325  	}
   326  	if got, want := dist0.chordAngle().Angle().Degrees(), 4.0; !float64Near(got, want, epsilon) {
   327  		t.Errorf("target.updateDistanceToEdge(%v, %v) = %v, want ~%v", p, dist0.chordAngle(), got, want)
   328  	}
   329  	if _, ok = target.updateDistanceToEdge(edge, dist10); ok {
   330  		t.Errorf("target.updateDistanceToEdge(%v, %v) should have failed", edge, dist10)
   331  	}
   332  
   333  	// Reset dist0 which was updated.
   334  	dist0 = maxDistance(0)
   335  	// Test for cell.
   336  	cell := CellFromCellID(cellIDFromPoint(parsePoint("0:0")))
   337  	if _, ok = target.updateDistanceToCell(cell, dist0); !ok {
   338  		t.Errorf("target.updateDistanceToCell(%v, %v) should have succeeded", cell, dist0)
   339  	}
   340  	// Leaf cell will be tiny compared to 10 degrees - expect no update.
   341  	if _, ok = target.updateDistanceToCell(cell, dist10); ok {
   342  		t.Errorf("target.updateDistanceToCell(%v, %v) should have failed", cell, dist10)
   343  	}
   344  }
   345  
   346  func TestDistanceTargetMaxEdgeTargetUpdateDistanceToCellWhenEqual(t *testing.T) {
   347  	var maxDist maxDistance
   348  
   349  	targetEdge := parsePoints("1:0, 1:1")
   350  	target := NewMaxDistanceToEdgeTarget(Edge{targetEdge[0], targetEdge[1]})
   351  	dist := maxDist.infinity()
   352  	cell := CellFromCellID(cellIDFromPoint(parsePoint("0:0")))
   353  
   354  	// First call should pass.
   355  	dist0, ok := target.updateDistanceToCell(cell, dist)
   356  	if !ok {
   357  		t.Errorf("target.updateDistanceToCell(%v, %v) should have succeeded", cell, dist)
   358  	}
   359  	// Second call should fail.
   360  	if _, ok := target.updateDistanceToCell(cell, dist0); ok {
   361  		t.Errorf("target.updateDistanceToCell(%v, %v) should have failed", cell, dist0)
   362  	}
   363  }
   364  
   365  func TestDistanceTargetMaxEdgeTargetUpdateDistanceToEdgeAntipodal(t *testing.T) {
   366  	var maxDist maxDistance
   367  
   368  	targetPts := parsePoints("0:89, 0:91")
   369  	targetEdge := Edge{targetPts[0], targetPts[1]}
   370  	target := NewMaxDistanceToEdgeTarget(targetEdge)
   371  	dist := maxDist.infinity()
   372  	pts := parsePoints("1:-90, -1:-90")
   373  	edge := Edge{pts[0], pts[1]}
   374  
   375  	// First call should pass.
   376  	dist0, ok := target.updateDistanceToEdge(edge, dist)
   377  	if !ok {
   378  		t.Errorf("target.updateDistanceToEdge(%v, %v) should have succeeded", edge, dist)
   379  	}
   380  
   381  	if dist0.chordAngle() != s1.StraightChordAngle {
   382  		t.Errorf("target.updateDistanceToPoint(%v, %v) = %v, want %v", edge, dist0, dist0, s1.StraightChordAngle)
   383  	}
   384  }
   385  
   386  func TestDistanceTargetMaxEdgeTargetUpdateDistanceToEdgeWhenEqual(t *testing.T) {
   387  	var maxDist maxDistance
   388  
   389  	targetEdge := parsePoints("1:0, 1:1")
   390  	target := NewMaxDistanceToEdgeTarget(Edge{targetEdge[0], targetEdge[1]})
   391  	dist := maxDist.infinity()
   392  	pts := parsePoints("0:-1, 0:1")
   393  	edge := Edge{pts[0], pts[1]}
   394  
   395  	// First call should pass.
   396  	dist0, ok := target.updateDistanceToEdge(edge, dist)
   397  	if !ok {
   398  		t.Errorf("target.updateDistanceToEdge(%v, %v) should have succeeded", edge, dist)
   399  	}
   400  	// Second call should fail.
   401  	if _, ok := target.updateDistanceToEdge(edge, dist0); ok {
   402  		t.Errorf("target.updateDistanceToEdge(%v, %v) should have failed", edge, dist0)
   403  	}
   404  }
   405  
   406  func TestDistanceTargetMaxEdgeTargetVisitContainingShapes(t *testing.T) {
   407  	// Only shapes 2 and 4 should contain the target edge.
   408  	index := makeShapeIndex("1:1 # 1:1, 2:2 # 0:0, 0:3, 3:0 | 6:6, 6:9, 9:6 | 0:0, 0:4, 4:0")
   409  
   410  	// Test against antipodal edge.
   411  	pts := parsePoints("1:2, 2:1")
   412  	edge := Edge{Point{pts[0].Mul(-1)}, Point{pts[1].Mul(-1)}}
   413  	target := NewMaxDistanceToEdgeTarget(edge)
   414  
   415  	if got, want := containingShapesForTarget(target, index, 1), []int{2}; !reflect.DeepEqual(got, want) {
   416  		t.Errorf("containingShapesForTarget(%v, %q, 1) = %+v, want %+v", target, shapeIndexDebugString(index), got, want)
   417  	}
   418  	if got, want := containingShapesForTarget(target, index, 5), []int{2, 4}; !reflect.DeepEqual(got, want) {
   419  		t.Errorf("containingShapesForTarget(%v, %q, 5) = %+v, want %+v", target, shapeIndexDebugString(index), got, want)
   420  	}
   421  }
   422  
   423  func TestDistanceTargetMaxShapeIndexTargetCapBound(t *testing.T) {
   424  	var md maxDistance
   425  	zero := md.zero()
   426  	inf := md.infinity()
   427  
   428  	index := NewShapeIndex()
   429  	index.Add(PolygonFromCell(CellFromCellID(randomCellID())))
   430  	pv := PointVector([]Point{randomPoint()})
   431  	index.Add(Shape(&pv))
   432  	target := NewMaxDistanceToShapeIndexTarget(index)
   433  	c := target.capBound()
   434  
   435  	for j := 0; j < 100; j++ {
   436  		pTest := randomPoint()
   437  		// Check points outside of cap to be away from maxDistance's zero().
   438  		if !c.ContainsPoint(pTest) {
   439  			var curDist distance = inf
   440  			var ok bool
   441  			if curDist, ok = target.updateDistanceToPoint(pTest, curDist); !ok {
   442  				t.Errorf("updateDistanceToPoint failed, but should have succeeded")
   443  				continue
   444  			}
   445  			if !zero.less(curDist) {
   446  				t.Errorf("point %v outside of cap should be less than %v distance, but were %v", pTest, zero, curDist)
   447  			}
   448  		}
   449  	}
   450  }
   451  
   452  func TestDistanceTargetMaxShapeIndexTargetUpdateDistanceToCellWhenEqual(t *testing.T) {
   453  	var maxDist maxDistance
   454  
   455  	index := makeShapeIndex("1:0 # #")
   456  	target := NewMaxDistanceToShapeIndexTarget(index)
   457  	dist := maxDist.infinity()
   458  	cell := CellFromCellID(cellIDFromPoint(parsePoint("0:0")))
   459  
   460  	// First call should pass.
   461  	dist0, ok := target.updateDistanceToCell(cell, dist)
   462  	if !ok {
   463  		t.Errorf("target.updateDistanceToCell(%v, %v) should have succeeded", cell, dist)
   464  	}
   465  	// Second call should fail.
   466  	if _, ok := target.updateDistanceToCell(cell, dist0); ok {
   467  		t.Errorf("target.updateDistanceToCell(%v, %v) should have failed", cell, dist0)
   468  	}
   469  }
   470  
   471  func TestDistanceTargetMaxShapeIndexTargetUpdateDistanceToEdgeWhenEqual(t *testing.T) {
   472  	var maxDist maxDistance
   473  
   474  	index := makeShapeIndex("1:0 # #")
   475  	target := NewMaxDistanceToShapeIndexTarget(index)
   476  	dist := maxDist.infinity()
   477  	pts := parsePoints("0:-1, 0:1")
   478  	edge := Edge{pts[0], pts[1]}
   479  
   480  	// First call should pass.
   481  	dist0, ok := target.updateDistanceToEdge(edge, dist)
   482  	if !ok {
   483  		t.Errorf("target.updateDistanceToEdge(%v, %v) should have succeeded", edge, dist)
   484  	}
   485  	// Second call should fail.
   486  	if _, ok := target.updateDistanceToEdge(edge, dist0); ok {
   487  		t.Errorf("target.updateDistanceToEdge(%v, %v) should have failed", edge, dist0)
   488  	}
   489  }
   490  
   491  // Negates S2 points to reflect them through the sphere.
   492  func reflectPoints(pts []Point) []Point {
   493  	var negativePts []Point
   494  	for _, p := range pts {
   495  		negativePts = append(negativePts, Point{p.Mul(-1)})
   496  	}
   497  	return negativePts
   498  }
   499  
   500  func TestDistanceTargetMaxShapeIndexTargetVisitContainingShapes(t *testing.T) {
   501  	// Create an index containing a repeated grouping of one point, one
   502  	// polyline, and one polygon.
   503  	index := makeShapeIndex("1:1 | 4:4 | 7:7 | 10:10 # " +
   504  		"1:1, 1:2 | 4:4, 4:5 | 7:7, 7:8 | 10:10, 10:11 # " +
   505  		"0:0, 0:3, 3:0 | 3:3, 3:6, 6:3 | 6:6, 6:9, 9:6 | 9:9, 9:12, 12:9")
   506  
   507  	// Construct a target consisting of one point, one polyline, and one polygon
   508  	// with two loops where only the second loop is contained by a polygon in
   509  	// the index above.
   510  	targetIndex := NewShapeIndex()
   511  
   512  	pts := PointVector(reflectPoints(parsePoints("1:1")))
   513  	targetIndex.Add(&pts)
   514  
   515  	line := Polyline(reflectPoints(parsePoints("4:5, 5:4")))
   516  	targetIndex.Add(&line)
   517  
   518  	loops := [][]Point{
   519  		reflectPoints(parsePoints("20:20, 20:21, 21:20")),
   520  		reflectPoints(parsePoints("10:10, 10:11, 11:10")),
   521  	}
   522  	laxPoly := LaxPolygonFromPoints(loops)
   523  	targetIndex.Add(laxPoly)
   524  
   525  	target := NewMaxDistanceToShapeIndexTarget(targetIndex)
   526  
   527  	// These are the shape_ids of the 1st, 2nd, and 4th polygons of "index"
   528  	// (noting that the 4 points are represented by one S2PointVectorShape).
   529  	if got, want := containingShapesForTarget(target, index, 5), []int{5, 6, 8}; !reflect.DeepEqual(got, want) {
   530  		t.Errorf("containingShapesForTarget(%v, %q, 5) = %+v, want %+v", target, shapeIndexDebugString(index), got, want)
   531  	}
   532  }
   533  
   534  func TestDistanceTargetMaxShapeIndexTargetVisitContainingShapesEmptyAndFull(t *testing.T) {
   535  	// Verify that VisitContainingShapes never returns empty polygons and always
   536  	// returns full polygons (i.e., those containing the entire sphere).
   537  
   538  	// Creating an index containing one empty and one full polygon.
   539  	index := makeShapeIndex("# # empty | full")
   540  
   541  	// Check only the full polygon is returned for a point target.
   542  	pointIndex := makeShapeIndex("1:1 # #")
   543  	pointTarget := NewMinDistanceToShapeIndexTarget(pointIndex)
   544  	if got, want := containingShapesForTarget(pointTarget, index, 5), []int{1}; !reflect.DeepEqual(got, want) {
   545  		t.Errorf("containingShapesForTarget(%v, %q, 5) = %+v, want %+v", pointTarget, shapeIndexDebugString(index), got, want)
   546  	}
   547  
   548  	// Check only the full polygon is returned for a full polygon target.
   549  	fullPolygonIndex := makeShapeIndex("# # full")
   550  	fullTarget := NewMinDistanceToShapeIndexTarget(fullPolygonIndex)
   551  	if got, want := containingShapesForTarget(fullTarget, index, 5), []int{1}; !reflect.DeepEqual(got, want) {
   552  		t.Errorf("containingShapesForTarget(%v, %q, 5) = %+v, want %+v", fullTarget, shapeIndexDebugString(index), got, want)
   553  	}
   554  
   555  	// Check that nothing is returned for an empty polygon target.  (An empty
   556  	// polygon has no connected components and does not intersect anything, so
   557  	// according to the API of GetContainingShapes nothing should be returned.)
   558  	emptyPolygonIndex := makeShapeIndex("# # empty")
   559  	emptyTarget := NewMinDistanceToShapeIndexTarget(emptyPolygonIndex)
   560  	if got, want := containingShapesForTarget(emptyTarget, index, 5), []int(nil); !reflect.DeepEqual(got, want) {
   561  		t.Errorf("containingShapesForTarget(%v, %q, 5) = %+v, want %+v", emptyTarget, shapeIndexDebugString(index), got, want)
   562  	}
   563  }
   564  

View as plain text