min_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  	"testing"
    20  )
    21  
    22  func TestDistanceTargetMinCellTargetUpdateDistanceToCellWhenEqual(t *testing.T) {
    23  	var minDist minDistance
    24  
    25  	targetCell := CellFromCellID(cellIDFromPoint(parsePoint("0:1")))
    26  	target := NewMinDistanceToCellTarget(targetCell)
    27  	dist := minDist.infinity()
    28  	cell := CellFromCellID(cellIDFromPoint(parsePoint("0:0")))
    29  
    30  	// First call should pass.
    31  	dist0, ok := target.updateDistanceToCell(cell, dist)
    32  	if !ok {
    33  		t.Errorf("target.updateDistanceToCell(%v, %v) should have succeeded", cell, dist)
    34  	}
    35  	// Second call should fail.
    36  	if _, ok := target.updateDistanceToCell(cell, dist0); ok {
    37  		t.Errorf("target.updateDistanceToCell(%v, %v) should have failed", cell, dist0)
    38  	}
    39  }
    40  
    41  func TestDistanceTargetMinCellTargetUpdateDistanceToEdgeWhenEqual(t *testing.T) {
    42  	var minDist minDistance
    43  
    44  	targetCell := CellFromCellID(cellIDFromPoint(parsePoint("0:1")))
    45  	target := NewMinDistanceToCellTarget(targetCell)
    46  	dist := minDist.infinity()
    47  	pts := parsePoints("0:-1, 0:1")
    48  	edge := Edge{pts[0], pts[1]}
    49  
    50  	// First call should pass.
    51  	dist0, ok := target.updateDistanceToEdge(edge, dist)
    52  	if !ok {
    53  		t.Errorf("target.updateDistanceToEdge(%v, %v) should have succeeded", edge, dist)
    54  	}
    55  	// Second call should fail.
    56  	if _, ok := target.updateDistanceToEdge(edge, dist0); ok {
    57  		t.Errorf("target.updateDistanceToEdge(%v, %v) should have failed", edge, dist0)
    58  	}
    59  }
    60  
    61  func TestDistanceTargetMinCellTargetVisitContainingShapes(t *testing.T) {
    62  	// Only shapes 2 and 4 should contain a very small cell near 1:1.
    63  	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")
    64  	targetCell := CellFromCellID(cellIDFromPoint(parsePoint("1:1")))
    65  	target := NewMinDistanceToCellTarget(targetCell)
    66  
    67  	if got, want := containingShapesForTarget(target, index, 1), []int{2}; !reflect.DeepEqual(got, want) {
    68  		t.Errorf("containingShapesForTarget(%v, %q, 1) = %+v, want %+v", target, shapeIndexDebugString(index), got, want)
    69  	}
    70  	if got, want := containingShapesForTarget(target, index, 5), []int{2, 4}; !reflect.DeepEqual(got, want) {
    71  		t.Errorf("containingShapesForTarget(%v, %q, 5) = %+v, want %+v", target, shapeIndexDebugString(index), got, want)
    72  	}
    73  
    74  	// For a larger cell that properly contains one or more index cells, all
    75  	// shapes that intersect the first such cell in CellID order are returned.
    76  	// In the test below, this happens to again be the 1st and 3rd polygons
    77  	// (whose shape_ids are 2 and 4).
    78  	target2 := NewMinDistanceToCellTarget(CellFromCellID(targetCell.ID().Parent(5)))
    79  	if got, want := containingShapesForTarget(target2, index, 5), []int{2, 4}; !reflect.DeepEqual(got, want) {
    80  		t.Errorf("containingShapesForTarget(%v, %q, 5) = %+v, want %+v", target2, shapeIndexDebugString(index), got, want)
    81  	}
    82  }
    83  
    84  func TestDistanceTargetMinCellUnionTargetUpdateDistanceToCellWhenEqual(t *testing.T) {
    85  	// TODO(roberts): Uncomment when implemented.
    86  	/*
    87  		var minDist minDistance
    88  
    89  		targetCellUnion := CellUnion([]CellID{cellIDFromPoint(parsePoint("0:1"))})
    90  		target := NewMinDistanceToCellUnionTarget(targetCellUnion)
    91  		dist := minDist.infinity()
    92  		cell := CellFromCellID(cellIDFromPoint(parsePoint("0:0")))
    93  
    94  		// First call should pass.
    95  		dist0, ok := target.updateDistanceToCell(cell, dist)
    96  		if !ok {
    97  			t.Errorf("target.updateDistanceToCell(%v, %v) should have succeeded", cell, dist)
    98  		}
    99  		// Second call should fail.
   100  		if dist1, ok := target.updateDistanceToCell(cell, dist0); ok {
   101  			t.Errorf("target.updateDistanceToCell(%v, %v) should have failed", cell, dist0)
   102  		}
   103  	*/
   104  }
   105  
   106  func TestDistanceTargetMinCellUnionTargetUpdateDistanceToEdgeWhenEqual(t *testing.T) {
   107  	// TODO(roberts): Uncomment when implemented.
   108  	/*
   109  		var minDist minDistance
   110  
   111  		targetCellUnion := CellUnion([]CellID{cellIDFromPoint(parsePoint("0:1"))})
   112  		target := NewMinDistanceToCellUnionTarget(targetCellUnion)
   113  		dist := minDist.infinity()
   114  		pts := parsePoints("0:-1, 0:1")
   115  		edge := Edge{pts[0], pts[1]}
   116  
   117  		// First call should pass.
   118  		dist0, ok := target.updateDistanceToEdge(edge, dist)
   119  		if !ok {
   120  			t.Errorf("target.updateDistanceToEdge(%v, %v) should have succeeded", edge, dist)
   121  		}
   122  		// Second call should fail.
   123  		if dist1, ok := target.updateDistanceToEdge(edge, dist0); ok {
   124  			t.Errorf("target.updateDistanceToEdge(%v, %v) should have failed", edge, dist0)
   125  		}
   126  	*/
   127  }
   128  
   129  func TestDistanceTargetMinCellUnionTargetVisitContainingShapes(t *testing.T) {
   130  	// TODO(roberts): Uncomment when implemented.
   131  	/*
   132  		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")
   133  
   134  		// Shapes 2 and 4 contain the leaf cell near 1:1, while shape 3 contains the
   135  		// leaf cell near 7:7.
   136  		targetCellUnion := CellUnion([]CellID{
   137  			cellIDFromPoint(parsePoint("1:1")),
   138  			cellIDFromPoint(parsePoint("7:7")),
   139  		})
   140  		target := NewMinDistanceToCellUnionTarget(targetCellUnion)
   141  
   142  		if got, want := containingShapesForTarget(target, index, 1), []int{2}; !reflect.DeepEqual(got, want) {
   143  			t.Errorf("containingShapesForTarget(%v, %q, 1) = %+v, want %+v", targetEdge, shapeIndexDebugString(index), got, want)
   144  		}
   145  		if got, want := containingShapesForTarget(target, index, 5), []int{2, 3, 4}; !reflect.DeepEqual(got, want) {
   146  			t.Errorf("containingShapesForTarget(%v, %q, 5) = %+v, want %+v", targetEdge, shapeIndexDebugString(index), got, want)
   147  		}
   148  	*/
   149  }
   150  
   151  func TestDistanceTargetMinEdgeTargetUpdateDistanceToCellWhenEqual(t *testing.T) {
   152  	var minDist minDistance
   153  
   154  	targetEdge := parsePoints("1:0, 1:1")
   155  	target := NewMinDistanceToEdgeTarget(Edge{targetEdge[0], targetEdge[1]})
   156  	dist := minDist.infinity()
   157  	cell := CellFromCellID(cellIDFromPoint(parsePoint("0:0")))
   158  
   159  	// First call should pass.
   160  	dist0, ok := target.updateDistanceToCell(cell, dist)
   161  	if !ok {
   162  		t.Errorf("target.updateDistanceToCell(%v, %v) should have succeeded", cell, dist)
   163  	}
   164  	// Second call should fail.
   165  	if _, ok := target.updateDistanceToCell(cell, dist0); ok {
   166  		t.Errorf("target.updateDistanceToCell(%v, %v) should have failed", cell, dist0)
   167  	}
   168  }
   169  
   170  func TestDistanceTargetMinEdgeTargetUpdateDistanceToEdgeWhenEqual(t *testing.T) {
   171  	var minDist minDistance
   172  
   173  	targetEdge := parsePoints("1:0, 1:1")
   174  	target := NewMinDistanceToEdgeTarget(Edge{targetEdge[0], targetEdge[1]})
   175  	dist := minDist.infinity()
   176  	pts := parsePoints("0:-1, 0:1")
   177  	edge := Edge{pts[0], pts[1]}
   178  
   179  	// First call should pass.
   180  	dist0, ok := target.updateDistanceToEdge(edge, dist)
   181  	if !ok {
   182  		t.Errorf("target.updateDistanceToEdge(%v, %v) should have succeeded", edge, dist)
   183  	}
   184  	// Second call should fail.
   185  	if _, ok := target.updateDistanceToEdge(edge, dist0); ok {
   186  		t.Errorf("target.updateDistanceToEdge(%v, %v) should have failed", edge, dist0)
   187  	}
   188  }
   189  
   190  func TestDistanceTargetMinEdgeTargetVisitContainingShapes(t *testing.T) {
   191  	// Only shapes 2 and 4 should contain the target point.
   192  	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")
   193  
   194  	targetEdge := parsePoints("1:2, 2:1")
   195  	target := NewMinDistanceToEdgeTarget(Edge{targetEdge[0], targetEdge[1]})
   196  
   197  	if got, want := containingShapesForTarget(target, index, 1), []int{2}; !reflect.DeepEqual(got, want) {
   198  		t.Errorf("containingShapesForTarget(%v, %q, 1) = %+v, want %+v", targetEdge, shapeIndexDebugString(index), got, want)
   199  	}
   200  	if got, want := containingShapesForTarget(target, index, 5), []int{2, 4}; !reflect.DeepEqual(got, want) {
   201  		t.Errorf("containingShapesForTarget(%v, %q, 5) = %+v, want %+v", targetEdge, shapeIndexDebugString(index), got, want)
   202  	}
   203  }
   204  
   205  func TestDistanceTargetMinPointTargetUpdateDistanceToCellWhenEqual(t *testing.T) {
   206  	target := NewMinDistanceToPointTarget(parsePoint("1:0"))
   207  	var minDist minDistance
   208  	dist := minDist.infinity()
   209  	cell := CellFromCellID(cellIDFromPoint(parsePoint("0:0")))
   210  
   211  	// First call should pass.
   212  	dist1, ok := target.updateDistanceToCell(cell, dist)
   213  	if !ok {
   214  		t.Errorf("target.updateDistanceToCell(%v, %v) should have succeeded", cell, dist)
   215  	}
   216  	// Second call should fail.
   217  	if _, ok := target.updateDistanceToCell(cell, dist1); ok {
   218  		t.Errorf("target.updateDistanceToCell(%v, %v) should have failed", cell, dist)
   219  	}
   220  }
   221  
   222  func TestDistanceTargetMinPointTargetUpdateDistanceToEdgeWhenEqual(t *testing.T) {
   223  	target := NewMinDistanceToPointTarget(parsePoint("1:0"))
   224  	var minDist minDistance
   225  	dist := minDist.infinity()
   226  	edge := parsePoints("0:-1, 0:1")
   227  
   228  	// First call should pass.
   229  	dist1, ok := target.updateDistanceToEdge(Edge{edge[0], edge[1]}, dist)
   230  	if !ok {
   231  		t.Errorf("target.updateDistanceToEdge(%v, %v) should have succeeded", edge, dist)
   232  	}
   233  	// Second call should fail.
   234  	if _, ok := target.updateDistanceToEdge(Edge{edge[0], edge[1]}, dist1); ok {
   235  		t.Errorf("target.updateDistanceToEdge(%v, %v) should have failed", edge, dist1)
   236  	}
   237  }
   238  
   239  func TestDistanceTargetMinPointTargetVisitContainingShapes(t *testing.T) {
   240  	// Only shapes 2 and 4 should contain the target point.
   241  	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")
   242  	point := parsePoint("1:1")
   243  	target := NewMinDistanceToPointTarget(point)
   244  
   245  	if got, want := containingShapesForTarget(target, index, 1), []int{2}; !reflect.DeepEqual(got, want) {
   246  		t.Errorf("containingShapesForTarget(%v, %q, 1) = %+v, want %+v", point, shapeIndexDebugString(index), got, want)
   247  	}
   248  	if got, want := containingShapesForTarget(target, index, 5), []int{2, 4}; !reflect.DeepEqual(got, want) {
   249  		t.Errorf("containingShapesForTarget(%v, %q, 5) = %+v, want %+v", point, shapeIndexDebugString(index), got, want)
   250  	}
   251  }
   252  
   253  func TestDistanceTargetMinShapeIndexTargetUpdateDistanceToCellWhenEqual(t *testing.T) {
   254  	index := makeShapeIndex("1:0 # #")
   255  	target := NewMinDistanceToShapeIndexTarget(index)
   256  	var minDist minDistance
   257  	dist := minDist.infinity()
   258  	cell := CellFromCellID(cellIDFromPoint(parsePoint("0:0")))
   259  
   260  	// First call should pass.
   261  	dist1, ok := target.updateDistanceToCell(cell, dist)
   262  	if !ok {
   263  		t.Errorf("target.updateDistanceToCell(%v, %v) should have succeeded", cell, dist)
   264  	}
   265  
   266  	// Repeat call should fail.
   267  	if _, ok := target.updateDistanceToCell(cell, dist1); ok {
   268  		t.Errorf("target.updateDistanceToCell(%v, %v) should have failed", cell, dist1)
   269  	}
   270  }
   271  
   272  func TestDistanceTargetMinShapeIndexTargetUpdateDistanceToEdgeWhenEqual(t *testing.T) {
   273  	index := makeShapeIndex("1:0 # #")
   274  	target := NewMinDistanceToShapeIndexTarget(index)
   275  	var minDist minDistance
   276  	dist := minDist.infinity()
   277  
   278  	pts := parsePoints("0:-1, 0:1")
   279  	edge := Edge{pts[0], pts[1]}
   280  
   281  	// First call should pass.
   282  	dist0, ok := target.updateDistanceToEdge(edge, dist)
   283  	if !ok {
   284  		t.Errorf("target.updateDistanceToEdge(%v, %v) should have succeeded", edge, dist)
   285  	}
   286  	// Second call should fail.
   287  	if _, ok := target.updateDistanceToEdge(edge, dist0); ok {
   288  		t.Errorf("target.updateDistanceToEdge(%v, %v) should have failed", edge, dist0)
   289  	}
   290  }
   291  
   292  func TestDistanceTargetMinShapeIndexTargetVisitContainingShapes(t *testing.T) {
   293  	// Create an index containing a repeated grouping of one point, one
   294  	// polyline, and one polygon.
   295  	index := makeShapeIndex("1:1 | 4:4 | 7:7 | 10:10 # " +
   296  		"1:1, 1:2 | 4:4, 4:5 | 7:7, 7:8 | 10:10, 10:11 # " +
   297  		"0:0, 0:3, 3:0 | 3:3, 3:6, 6:3 | 6:6, 6:9, 9:6 | 9:9, 9:12, 12:9")
   298  
   299  	// Construct a target consisting of one point, one polyline, and one polygon
   300  	// with two loops where only the second loop is contained by a polygon in
   301  	// the index above.
   302  	targetIndex := makeShapeIndex("1:1 # 4:5, 5:4 # 20:20, 20:21, 21:20; 10:10, 10:11, 11:10")
   303  	target := NewMinDistanceToShapeIndexTarget(targetIndex)
   304  
   305  	// These are the shape_ids of the 1st, 2nd, and 4th polygons of "index"
   306  	// (noting that the 4 points are represented by one PointVectorShape).
   307  	if got, want := containingShapesForTarget(target, index, 5), []int{5, 6, 8}; !reflect.DeepEqual(got, want) {
   308  		t.Errorf("containingShapesForTarget(%v, %q, 5) = %+v, want %+v", target, shapeIndexDebugString(index), got, want)
   309  	}
   310  }
   311  
   312  func TestDistanceTargetMinShapeIndexTargetVisitContainingShapesEmptyAndFull(t *testing.T) {
   313  	// Verify that VisitContainingShapes never returns empty polygons and always
   314  	// returns full polygons (i.e., those containing the entire sphere).
   315  
   316  	// Creating an index containing one empty and one full polygon.
   317  	index := makeShapeIndex("# # empty | full")
   318  
   319  	// Check only the full polygon is returned for a point target.
   320  	pointIndex := makeShapeIndex("1:1 # #")
   321  	pointTarget := NewMinDistanceToShapeIndexTarget(pointIndex)
   322  	if got, want := containingShapesForTarget(pointTarget, index, 5), []int{1}; !reflect.DeepEqual(got, want) {
   323  		t.Errorf("containingShapesForTarget(%v, %q, 5) = %+v, want %+v", pointTarget, shapeIndexDebugString(index), got, want)
   324  	}
   325  
   326  	// Check only the full polygon is returned for a full polygon target.
   327  	fullPolygonIndex := makeShapeIndex("# # full")
   328  	fullTarget := NewMinDistanceToShapeIndexTarget(fullPolygonIndex)
   329  	if got, want := containingShapesForTarget(fullTarget, index, 5), []int{1}; !reflect.DeepEqual(got, want) {
   330  		t.Errorf("containingShapesForTarget(%v, %q, 5) = %+v, want %+v", fullTarget, shapeIndexDebugString(index), got, want)
   331  	}
   332  
   333  	// Check that nothing is returned for an empty polygon target.  (An empty
   334  	// polygon has no connected components and does not intersect anything, so
   335  	// according to the API of GetContainingShapes nothing should be returned.)
   336  	emptyPolygonIndex := makeShapeIndex("# # empty")
   337  	emptyTarget := NewMinDistanceToShapeIndexTarget(emptyPolygonIndex)
   338  	if got, want := containingShapesForTarget(emptyTarget, index, 5), []int(nil); !reflect.DeepEqual(got, want) {
   339  		t.Errorf("containingShapesForTarget(%v, %q, 5) = %+v, want %+v", emptyTarget, shapeIndexDebugString(index), got, want)
   340  	}
   341  }
   342
View as plain text