crossing_edge_query_test.go

Documentation: github.com/golang/geo/s2

     1  // Copyright 2017 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  	"reflect"
    20  	"testing"
    21  
    22  	"github.com/golang/geo/s1"
    23  )
    24  
    25  func perturbAtDistance(distance s1.Angle, a0, b0 Point) Point {
    26  	x := InterpolateAtDistance(distance, a0, b0)
    27  	if oneIn(2) {
    28  		if oneIn(2) {
    29  			x.X = math.Nextafter(x.X, 1)
    30  		} else {
    31  			x.X = math.Nextafter(x.X, -1)
    32  		}
    33  		if oneIn(2) {
    34  			x.Y = math.Nextafter(x.Y, 1)
    35  		} else {
    36  			x.Y = math.Nextafter(x.Y, -1)
    37  		}
    38  		if oneIn(2) {
    39  			x.Z = math.Nextafter(x.Z, 1)
    40  		} else {
    41  			x.Z = math.Nextafter(x.Z, -1)
    42  
    43  		}
    44  		x = Point{x.Normalize()}
    45  	}
    46  	return x
    47  }
    48  
    49  // generatePerturbedSubEdges generate sub-edges of some given edge (a,b).
    50  // The length of the sub-edges is distributed exponentially over a large range,
    51  // and the endpoints may be slightly perturbed to one side of (a,b) or the other.
    52  func generatePerturbedSubEdges(a, b Point, count int) []Edge {
    53  	var edges []Edge
    54  
    55  	a = Point{a.Normalize()}
    56  	b = Point{b.Normalize()}
    57  
    58  	length0 := a.Distance(b)
    59  	for i := 0; i < count; i++ {
    60  		length := length0 * s1.Angle(math.Pow(1e-15, randomFloat64()))
    61  		offset := (length0 - length) * s1.Angle(randomFloat64())
    62  		edges = append(edges, Edge{
    63  			perturbAtDistance(offset, a, b),
    64  			perturbAtDistance(offset+length, a, b),
    65  		})
    66  	}
    67  	return edges
    68  }
    69  
    70  // generateCapEdges creates edges whose center is randomly chosen from the given cap, and
    71  // whose length is randomly chosen up to maxLength.
    72  func generateCapEdges(centerCap Cap, maxLength s1.Angle, count int) []Edge {
    73  	var edges []Edge
    74  	for i := 0; i < count; i++ {
    75  		center := samplePointFromCap(centerCap)
    76  		edgeCap := CapFromCenterAngle(center, 0.5*maxLength)
    77  		p1 := samplePointFromCap(edgeCap)
    78  		// Compute p1 reflected through center, and normalize for good measure.
    79  		p2 := Point{(center.Mul(2 * p1.Dot(center.Vector)).Sub(p1.Vector)).Normalize()}
    80  		edges = append(edges, Edge{p1, p2})
    81  	}
    82  	return edges
    83  }
    84  
    85  func testCrossingEdgeQueryAllCrossings(t *testing.T, edges []Edge) {
    86  	s := &edgeVectorShape{}
    87  	for _, edge := range edges {
    88  		s.Add(edge.V0, edge.V1)
    89  	}
    90  
    91  	// Force more subdivision than usual to make the test more challenging.
    92  	index := NewShapeIndex()
    93  	index.maxEdgesPerCell = 1
    94  	index.Add(s)
    95  
    96  	// To check that candidates are being filtered reasonably, we count the
    97  	// total number of candidates that the total number of edge pairs that
    98  	// either intersect or are very close to intersecting.
    99  	var numCandidates, numNearbyPairs int
   100  
   101  	for _, edge := range edges {
   102  		a := edge.V0
   103  		b := edge.V1
   104  
   105  		query := NewCrossingEdgeQuery(index)
   106  		candidates := query.candidates(a, b, s)
   107  
   108  		// Verify that the EdgeMap version of candidates returns the same result.
   109  		edgeMap := query.candidatesEdgeMap(a, b)
   110  		if len(edgeMap) != 1 {
   111  			t.Errorf("there should be only one shape in this map, got %d", len(edgeMap))
   112  			// Skip the next part of the check since we expect only 1
   113  			// value, and you can't get just the first entry in a map.
   114  			continue
   115  		}
   116  		for k, v := range edgeMap {
   117  			if Shape(s) != k {
   118  				t.Errorf("element(%v) of edgeMap should be this shape", k)
   119  			}
   120  			if !reflect.DeepEqual(candidates, v) {
   121  				t.Errorf("edgeMap candidates for this shape = %v, want %v", v, candidates)
   122  			}
   123  		}
   124  		if len(candidates) == 0 {
   125  			t.Errorf("candidates should not be empty")
   126  		}
   127  
   128  		// Now check the actual candidates.
   129  		// Check the results are sorted
   130  		for k, v := range candidates {
   131  			if k < len(candidates)-1 {
   132  				if v > candidates[k+1] {
   133  					t.Errorf("candidates was not sorted. candidates[%d] = %v > candidates[%d] = %v", k, v, k+1, candidates[k+1])
   134  				}
   135  			}
   136  		}
   137  		if got := candidates[0]; got < 0 {
   138  			t.Errorf("the first element should not have a negative edge id")
   139  		}
   140  		if got, want := candidates[len(candidates)-1], s.NumEdges(); got >= want {
   141  			t.Errorf("candidates[%d] = %v, want < %v", len(candidates)-1, got, want)
   142  		}
   143  
   144  		numCandidates += len(candidates)
   145  
   146  		var expectedCrossings, expectedInteriorCrossings []int
   147  		var missingCandidates []int
   148  		for i := 0; i < s.NumEdges(); i++ {
   149  			edge := s.Edge(i)
   150  			c := edge.V0
   151  			d := edge.V1
   152  			sign := CrossingSign(a, b, c, d)
   153  			if sign != DoNotCross {
   154  				expectedCrossings = append(expectedCrossings, i)
   155  				if sign == Cross {
   156  					expectedInteriorCrossings = append(expectedInteriorCrossings, i)
   157  				}
   158  				numNearbyPairs++
   159  
   160  				// try to find this edge number in the set of candidates.
   161  				found := false
   162  				for _, v := range candidates {
   163  					if v == i {
   164  						found = true
   165  					}
   166  				}
   167  				// If we couldn't find it, add it to the missing set.
   168  				if !found {
   169  					missingCandidates = append(missingCandidates, i)
   170  				}
   171  			} else {
   172  				maxDist := MaxDiagMetric.Value(MaxLevel)
   173  				if DistanceFromSegment(a, c, d).Radians() < maxDist ||
   174  					DistanceFromSegment(b, c, d).Radians() < maxDist ||
   175  					DistanceFromSegment(c, a, b).Radians() < maxDist ||
   176  					DistanceFromSegment(d, a, b).Radians() < maxDist {
   177  					numNearbyPairs++
   178  				}
   179  			}
   180  		}
   181  
   182  		if len(missingCandidates) != 0 {
   183  			t.Errorf("missingCandidates should have been empty")
   184  		}
   185  
   186  		// test that Crossings returns only the actual crossing edges.
   187  		actualCrossings := query.Crossings(a, b, s, CrossingTypeAll)
   188  		if !reflect.DeepEqual(expectedCrossings, actualCrossings) {
   189  			t.Errorf("query.Crossings(%v, %v, ...) = %v, want %v", a, b, actualCrossings, expectedCrossings)
   190  		}
   191  
   192  		// Verify that the edge map version of Crossings returns the same result.
   193  		if edgeMap := query.CrossingsEdgeMap(a, b, CrossingTypeAll); len(edgeMap) != 0 {
   194  			if len(edgeMap) != 1 {
   195  				t.Errorf("query.CrossingsEdgeMap(%v, %v) has %d entried, want 1", a, b, len(edgeMap))
   196  			} else {
   197  				for k, v := range edgeMap {
   198  					if s != k {
   199  						t.Errorf("query.CrossingsEdgeMap(%v, %v, ...) shape = %v, want %v", a, b, k, s)
   200  					}
   201  					if !reflect.DeepEqual(expectedCrossings, v) {
   202  						t.Errorf("query.CrossingsEdgeMap(%v, %v) = %v, want %v", a, b, v, expectedCrossings)
   203  					}
   204  				}
   205  			}
   206  		}
   207  
   208  		// Verify that CrossingTypeInterior returns only the interior crossings.
   209  		actualCrossings = query.Crossings(a, b, s, CrossingTypeInterior)
   210  		// TODO(roberts): Move to package "cmp" when s2 can meet the minimum go version.
   211  		// This will handle the case where one slice is nil and the other is non-nil
   212  		// but empty as being equivalent more cleanly.
   213  		if !reflect.DeepEqual(expectedInteriorCrossings, actualCrossings) && (len(actualCrossings) != 0 && len(expectedInteriorCrossings) != 0) {
   214  			t.Errorf("query.Crossings(%v, %v, CrossingTypeInterior) = %v, want %v", a, b, actualCrossings, expectedInteriorCrossings)
   215  		}
   216  	}
   217  
   218  	// There is nothing magical about this particular ratio; this check exists
   219  	// to catch changes that dramatically increase the number of candidates.
   220  	if numCandidates > 3*numNearbyPairs {
   221  		t.Errorf("number of candidates should not be dramatically larger than number of nearby pairs. got %v, want < %v", numCandidates, 3*numNearbyPairs)
   222  	}
   223  
   224  }
   225  
   226  func TestCrossingEdgeQueryCrossingCandidatesPerturbedCubeEdges(t *testing.T) {
   227  	// Test edges that lie in the plane of one of the S2 cube edges. Such edges
   228  	// may lie on the boundary between two cube faces, or pass through a cube
   229  	// vertex, or follow a 45 diagonal across a cube face toward its center.
   230  	//
   231  	// This test is sufficient to demonstrate that padding the cell boundaries
   232  	// is necessary for correctness. (It will fails if ShapeIndexes CellPadding is
   233  	// set to zero.)
   234  	for iter := 0; iter < 10; iter++ {
   235  		face := randomUniformInt(6)
   236  		scale := math.Pow(1e-15, randomFloat64())
   237  		u := scale*2*float64(randomUniformInt(2)) - 1
   238  		v := scale*2*float64(randomUniformInt(2)) - 1
   239  
   240  		a := Point{faceUVToXYZ(face, u, v)}
   241  		b := Point{a.Sub(unitNorm(face).Mul(2))}
   242  		// TODO(roberts): This test is currently slow because *every* crossing test
   243  		// needs to invoke ExpensiveSign.
   244  		edges := generatePerturbedSubEdges(a, b, 30)
   245  		testCrossingEdgeQueryAllCrossings(t, edges)
   246  	}
   247  }
   248  
   249  // Test edges that lie in the plane of one of the S2 cube face axes. These
   250  // edges are special because one coordinate is zero, and they lie on the
   251  // boundaries between the immediate child cells of the cube face.
   252  func TestCrossingEdgeQueryCandidatesPerturbedCubeFaceAxes(t *testing.T) {
   253  	for iter := 0; iter < 5; iter++ {
   254  		face := randomUniformInt(6)
   255  		scale := math.Pow(1e-15, randomFloat64())
   256  		axis := uvwAxis(face, randomUniformInt(2))
   257  		a := Point{axis.Mul(scale).Add(unitNorm(face).Vector)}
   258  		b := Point{axis.Mul(scale).Sub(unitNorm(face).Vector)}
   259  		edges := generatePerturbedSubEdges(a, b, 30)
   260  		testCrossingEdgeQueryAllCrossings(t, edges)
   261  	}
   262  }
   263  
   264  func TestCrossingEdgeQueryCandidatesCapEdgesNearCubeVertex(t *testing.T) {
   265  	// Test a random collection of edges near the S2 cube vertex where the
   266  	// Hilbert curve starts and ends.
   267  	edges := generateCapEdges(CapFromCenterAngle(PointFromCoords(-1, -1, 1), s1.Angle(1e-3)), s1.Angle(1e-4), 1000)
   268  	testCrossingEdgeQueryAllCrossings(t, edges)
   269  }
   270  
   271  func TestCrossingEdgeQueryCandidatesDegenerateEdgeOnCellVertexIsItsOwnCandidate(t *testing.T) {
   272  	for iter := 0; iter < 100; iter++ {
   273  		cell := CellFromCellID(randomCellID())
   274  		edges := []Edge{{cell.Vertex(0), cell.Vertex(0)}}
   275  		testCrossingEdgeQueryAllCrossings(t, edges)
   276  	}
   277  }
   278  
   279  func TestCrossingEdgeQueryCandidatesCollinearEdgesOnCellBoundaries(t *testing.T) {
   280  	const numEdgeIntervals = 8 // 9*8/2 = 36 edges
   281  	for level := 0; level <= MaxLevel; level++ {
   282  		var edges []Edge
   283  		cell := CellFromCellID(randomCellIDForLevel(level))
   284  		i := randomUniformInt(4)
   285  		p1 := cell.Vertex(i % 4)
   286  		p2 := cell.Vertex((i + 1) % 4)
   287  		delta := p2.Sub(p1.Vector).Mul(1 / numEdgeIntervals)
   288  		for i := 0; i <= numEdgeIntervals; i++ {
   289  			for j := 0; j < i; j++ {
   290  				edges = append(edges, Edge{
   291  					Point{p1.Add(delta.Mul(float64(i))).Normalize()},
   292  					Point{p1.Add(delta.Mul(float64(j))).Normalize()},
   293  				})
   294  			}
   295  		}
   296  		testCrossingEdgeQueryAllCrossings(t, edges)
   297  	}
   298  }
   299  
   300  func TestCrossingEdgeQueryCrossingsPolylineCrossings(t *testing.T) {
   301  	index := NewShapeIndex()
   302  	// Three zig-zag lines near the equator.
   303  	index.Add(makePolyline("0:0, 2:1, 0:2, 2:3, 0:4, 2:5, 0:6"))
   304  	index.Add(makePolyline("1:0, 3:1, 1:2, 3:3, 1:4, 3:5, 1:6"))
   305  	index.Add(makePolyline("2:0, 4:1, 2:2, 4:3, 2:4, 4:5, 2:6"))
   306  	index.Begin()
   307  
   308  	var tests = []struct {
   309  		a0, a1 Point
   310  	}{
   311  		{parsePoint("1:0"), parsePoint("1:4")},
   312  		{parsePoint("5:5"), parsePoint("6:6")},
   313  	}
   314  
   315  	for _, test := range tests {
   316  		query := NewCrossingEdgeQuery(index)
   317  
   318  		edgeMap := query.CrossingsEdgeMap(test.a0, test.a1, CrossingTypeAll)
   319  		if len(edgeMap) == 0 {
   320  			continue
   321  		}
   322  
   323  		for shape, edges := range edgeMap {
   324  			polyline := shape.(*Polyline)
   325  			if len(edges) == 0 {
   326  				t.Errorf("shapes with no crossings should have been filtered out")
   327  			}
   328  
   329  			for _, edge := range edges {
   330  				b0 := (*polyline)[edge]
   331  				b1 := (*polyline)[edge+1]
   332  				if got := CrossingSign(test.a0, test.a1, b0, b1); got == DoNotCross {
   333  					t.Errorf("CrossingSign(%v, %v, %v, %v) = %v, want MaybeCross or Cross", test.a0, test.a1, b0, b1, got)
   334  				}
   335  			}
   336  		}
   337  
   338  		// Also test that no edges are missing.
   339  		for _, shape := range index.shapes {
   340  			polyline := shape.(*Polyline)
   341  			edges := edgeMap[shape]
   342  			for e := 0; e < len(*polyline)-1; e++ {
   343  				if got := CrossingSign(test.a0, test.a1, (*polyline)[e], (*polyline)[e+1]); got != DoNotCross {
   344  					// Need to count occurrences of the current edge to see
   345  					// if and how many are in the edge map.
   346  					count := 0
   347  					for _, edge := range edges {
   348  						if edge == e {
   349  							count++
   350  						}
   351  					}
   352  
   353  					if count != 1 {
   354  						t.Errorf("edge %v should appear once in the set of edges, got %v", e, count)
   355  					}
   356  				}
   357  			}
   358  		}
   359  	}
   360  }
   361  
   362  func TestUniqueInts(t *testing.T) {
   363  	tests := []struct {
   364  		have []int
   365  		want []int
   366  	}{
   367  		{
   368  			have: nil,
   369  			want: nil,
   370  		},
   371  		{
   372  			have: []int{},
   373  			want: nil,
   374  		},
   375  		{
   376  			have: []int{1},
   377  			want: []int{1},
   378  		},
   379  		{
   380  			have: []int{3, 2, 1},
   381  			want: []int{1, 2, 3},
   382  		},
   383  		{
   384  			have: []int{4, 4, 4},
   385  			want: []int{4},
   386  		},
   387  		{
   388  			have: []int{1, 2, 3, 4, 2, 3, 5, 4, 6, 1, 2, 3, 4, 5, 7, 8, 1, 3, 1, 2, 3, 9, 3, 2, 1},
   389  			want: []int{1, 2, 3, 4, 5, 6, 7, 8, 9},
   390  		},
   391  	}
   392  
   393  	for _, test := range tests {
   394  		if got := uniqueInts(test.have); !reflect.DeepEqual(got, test.want) {
   395  			t.Errorf("uniqueInts(%v) = %v, want %v", test.have, got, test.want)
   396  		}
   397  	}
   398  }
   399
View as plain text