edge_query_closest_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  	"fmt"
    19  	"testing"
    20  
    21  	"github.com/golang/geo/r3"
    22  	"github.com/golang/geo/s1"
    23  )
    24  
    25  func TestClosestEdgeQueryNoEdges(t *testing.T) {
    26  	index := &ShapeIndex{}
    27  	query := NewClosestEdgeQuery(index, nil)
    28  	target := NewMinDistanceToPointTarget(PointFromCoords(1, 0, 0))
    29  	edge := query.findEdge(target, query.opts)
    30  
    31  	if edge.shapeID != -1 {
    32  		t.Errorf("shapeID for empty index should be -1, got %v", edge.shapeID)
    33  	}
    34  	if edge.edgeID != -1 {
    35  		t.Errorf("edgeID for empty index should be -1, got %v", edge.edgeID)
    36  	}
    37  	if got, want := edge.Distance(), s1.InfChordAngle(); got != want {
    38  		t.Errorf("edge.Distance = %+v, want %+v", got, want)
    39  	}
    40  
    41  	if got, want := query.Distance(target), s1.InfChordAngle(); got != want {
    42  		t.Errorf("query.Distance(%v) = %+v, want %+v", target, got, want)
    43  	}
    44  }
    45  
    46  func TestClosestEdgeQueryBasicTest(t *testing.T) {
    47  	index := makeShapeIndex("1:1 | 1:2 | 1:3 # #")
    48  	opts := NewClosestEdgeQueryOptions().
    49  		MaxResults(1).
    50  		DistanceLimit(s1.ChordAngleFromAngle(s1.Angle(3) * s1.Degree)).
    51  		MaxError(s1.ChordAngleFromAngle(s1.Angle(0.001) * s1.Degree))
    52  
    53  	query := NewClosestEdgeQuery(index, opts)
    54  	target := NewMinDistanceToPointTarget(parsePoint("2:2"))
    55  	result := query.findEdge(target, query.opts)
    56  
    57  	if got, want := result.edgeID, int32(1); got != want {
    58  		t.Errorf("query.findEdge(%v).edgeID = %v, want %v", target, got, want)
    59  	}
    60  	if got, want := query.Distance(target).Angle().Degrees(), 1.0; !float64Near(got, want, epsilon) {
    61  		t.Errorf("query.Distance(%v) = %v, want %v", target, got, want)
    62  	}
    63  	if !query.IsDistanceLess(target, s1.ChordAngleFromAngle(s1.Angle(1.5)*s1.Degree)) {
    64  		t.Errorf("query.IsDistanceLess(%v, 1.5) should be true but wasn't", target)
    65  	}
    66  }
    67  
    68  func TestClosestEdgeQueryDistanceEqualToLimit(t *testing.T) {
    69  	// Tests the behavior of IsDistanceLess, IsDistanceLessOrEqual, and
    70  	// IsConservativeDistanceLessOrEqual (and the corresponding Options) when
    71  	// the distance to the target exactly equals the chosen limit.
    72  	p0 := parsePoint("23:12")
    73  	p1 := parsePoint("47:11")
    74  	index := NewShapeIndex()
    75  	pv := PointVector([]Point{p0})
    76  	index.Add(Shape(&pv))
    77  	query := NewClosestEdgeQuery(index, nil)
    78  
    79  	// Start with two identical points and a zero distance.
    80  	target0 := NewMinDistanceToPointTarget(p0)
    81  	dist0 := s1.ChordAngle(0)
    82  	if query.IsDistanceLess(target0, dist0) {
    83  		t.Errorf("query.IsDistanceLess(%v, %v) = true, want false", target0, dist0)
    84  	}
    85  	if !query.IsDistanceLess(target0, dist0.Successor()) {
    86  		t.Errorf("query.IsDistanceLess(%v, %v) = false, want true", target0, dist0)
    87  	}
    88  	if !query.IsConservativeDistanceLessOrEqual(target0, dist0) {
    89  		t.Errorf("query.IsConservativeDistanceLessOrEqual(%v, %v) = false, want true", target0, dist0)
    90  	}
    91  
    92  	// Now try two points separated by a non-zero distance.
    93  	target1 := NewMinDistanceToPointTarget(p1)
    94  	dist1 := ChordAngleBetweenPoints(p0, p1)
    95  	if query.IsDistanceLess(target1, dist1) {
    96  		t.Errorf("query.IsDistanceLess(%v, %v) = true, want false", target1, dist1)
    97  	}
    98  	if !query.IsDistanceLess(target1, dist1.Successor()) {
    99  		t.Errorf("query.IsDistanceLess(%v, %v) = false, want true", target1, dist1)
   100  	}
   101  	if !query.IsConservativeDistanceLessOrEqual(target1, dist1) {
   102  		t.Errorf("query.IsConservativeDistanceLessOrEqual(%v, %v) = false, want true", target1, dist1)
   103  	}
   104  }
   105  
   106  func TestClosestEdgeQueryTrueDistanceLessThanChordAngleDistance(t *testing.T) {
   107  	// Tests that IsConservativeDistanceLessOrEqual returns points where the
   108  	// true distance is slightly less than the one computed by ChordAngle.
   109  	//
   110  	// The points below had the worst error from among 100,000 random pairs.
   111  	p0 := Point{r3.Vector{0.78516762584829192, -0.50200400690845970, -0.36263449417782678}}
   112  	p1 := Point{r3.Vector{0.78563011732429433, -0.50187655940493503, -0.36180828883938054}}
   113  	pv := &PointVector{p0}
   114  
   115  	index := NewShapeIndex()
   116  	index.Add(pv)
   117  	query := NewClosestEdgeQuery(index, nil)
   118  
   119  	// The ChordAngle distance is ~4 ulps greater than the true distance.
   120  	dist := ChordAngleBetweenPoints(p0, p1)
   121  	limit := dist.Predecessor().Predecessor().Predecessor().Predecessor()
   122  	if got, want := CompareDistance(p0, p1, limit), 0; got >= want {
   123  		t.Errorf("CompareDistance(%v, %v, %v) = %v, want >= %v", p0, p1, limit, got, want)
   124  	}
   125  
   126  	// Verify that IsConservativeDistanceLessOrEqual() still returns "p1".
   127  	target := NewMinDistanceToPointTarget(p1)
   128  	if query.IsDistanceLess(target, limit) {
   129  		t.Errorf("query.IsDistanceLess(%v, %v) = true, want false", target, dist)
   130  	}
   131  	if query.IsDistanceLess(target, limit.Successor()) {
   132  		t.Errorf("query.IsDistanceLessOrEqual(%v, %v) = true, want false", target, dist)
   133  	}
   134  	if !query.IsConservativeDistanceLessOrEqual(target, limit) {
   135  		t.Errorf("query.IsConservativeDistanceLessOrEqual(%v, %v) = false, want true", target, dist)
   136  	}
   137  }
   138  
   139  func TestClosestEdgeQueryTargetPointInsideIndexedPolygon(t *testing.T) {
   140  	// Tests a target point in the interior of an indexed polygon.
   141  	// (The index also includes a polyline loop with no interior.)
   142  	index := makeShapeIndex("# 0:0, 0:5, 5:5, 5:0 # 0:10, 0:15, 5:15, 5:10")
   143  	opts := NewClosestEdgeQueryOptions().
   144  		IncludeInteriors(true).
   145  		DistanceLimit(s1.ChordAngleFromAngle(s1.Angle(1) * s1.Degree))
   146  	query := NewClosestEdgeQuery(index, opts)
   147  
   148  	target := NewMinDistanceToPointTarget(parsePoint("2:12"))
   149  
   150  	results := query.FindEdges(target)
   151  	if len(results) != 1 {
   152  		t.Fatalf("len(results) = %v, want 1", len(results))
   153  	}
   154  
   155  	r0 := results[0]
   156  	if r0.Distance() != 0 {
   157  		t.Errorf("result[0].Distance = %v, want 0", r0.Distance())
   158  	}
   159  	if r0.shapeID != 1 {
   160  		t.Errorf("result[0].shapeID = %v, want 1", r0.shapeID)
   161  	}
   162  	if r0.edgeID != -1 {
   163  		t.Errorf("result[0].edgeID = %v, want -1", r0.edgeID)
   164  	}
   165  	if !r0.IsInterior() {
   166  		t.Errorf("first edge should have been interior to the polygon")
   167  	}
   168  	if r0.IsEmpty() {
   169  		t.Errorf("result should not have been empty")
   170  	}
   171  }
   172  
   173  func TestClosestEdgeQueryTargetPolygonContainingIndexedPoints(t *testing.T) {
   174  	// Two points are contained within a polyline loop (no interior) and two
   175  	// points are contained within a polygon.
   176  	index := makeShapeIndex("2:2 | 3:3 | 1:11 | 3:13 # #")
   177  	opts := NewClosestEdgeQueryOptions().
   178  		UseBruteForce(false).
   179  		DistanceLimit(s1.ChordAngleFromAngle(s1.Angle(1) * s1.Degree))
   180  	query := NewClosestEdgeQuery(index, opts)
   181  
   182  	targetIndex := makeShapeIndex("# 0:0, 0:5, 5:5, 5:0 # 0:10, 0:15, 5:15, 5:10")
   183  	target := NewMinDistanceToShapeIndexTarget(targetIndex)
   184  
   185  	target.setIncludeInteriors(true)
   186  	results := query.FindEdges(target)
   187  
   188  	// All points should be returned since we did not specify MaxResults.
   189  	if len(results) != 2 {
   190  		t.Errorf("2 shapes should have matched. Got %d shapes", len(results))
   191  	}
   192  
   193  	r0 := results[0]
   194  	if r0.Distance() != 0 {
   195  		t.Errorf("result[0].Distance != 0, want 0")
   196  	}
   197  	if r0.shapeID != 0 {
   198  		t.Errorf("result[0].shapeID = %v, want 0", r0.shapeID)
   199  	}
   200  	if r0.edgeID != 2 {
   201  		t.Errorf("result[0].edgeID = %v, want 0", r0.edgeID) // 1:11
   202  	}
   203  
   204  	r1 := results[1]
   205  	if r1.Distance() != 0 {
   206  		t.Errorf("result[1].Distance != 0, want 0")
   207  	}
   208  	if r1.shapeID != 0 {
   209  		t.Errorf("result[1].shapeID = %v, want 0", r1.shapeID)
   210  	}
   211  	if r1.edgeID != 3 {
   212  		t.Errorf("result[1].edgeID = %v, want 3", r1.edgeID) // 3:13
   213  	}
   214  }
   215  
   216  // BenchmarkEdgeQueryFindEdges encapulates the benchmarks into a more standard
   217  // form to cut down on repeated copy and paste with all the combinations of
   218  // benchmarks for EdgeQuery.
   219  func BenchmarkEdgeQueryFindEdges(b *testing.B) {
   220  	generators := []struct {
   221  		name string
   222  		gen  shapeIndexGeneratorFunc
   223  	}{
   224  		{"Fractal", fractalLoopShapeIndexGenerator},
   225  		{"Regular", loopShapeIndexGenerator},
   226  		{"PointCloud", pointCloudShapeIndexGenerator},
   227  	}
   228  
   229  	benchmarks := []struct {
   230  		benchCase string
   231  		opts      *edgeQueryBenchmarkOptions
   232  	}{
   233  		{
   234  			// Test searching within the general vicinity of the indexed shapes.
   235  			benchCase: "ClosestToPoint",
   236  			opts: &edgeQueryBenchmarkOptions{
   237  				includeInteriors:         false,
   238  				targetType:               queryTypePoint,
   239  				numTargetEdges:           0,
   240  				chooseTargetFromIndex:    false,
   241  				radiusKm:                 1000,
   242  				maxDistanceFraction:      -1,
   243  				maxErrorFraction:         -1,
   244  				targetRadiusFraction:     0.0,
   245  				centerSeparationFraction: -2.0,
   246  			},
   247  		},
   248  		{
   249  			// Test searching within the general vicinity of the
   250  			// indexed shapes including interiors.
   251  			benchCase: "ClosestToPointInterior",
   252  			opts: &edgeQueryBenchmarkOptions{
   253  				includeInteriors:         true,
   254  				targetType:               queryTypePoint,
   255  				numTargetEdges:           0,
   256  				chooseTargetFromIndex:    false,
   257  				radiusKm:                 1000,
   258  				maxDistanceFraction:      -1,
   259  				maxErrorFraction:         -1,
   260  				targetRadiusFraction:     0.0,
   261  				centerSeparationFraction: -2.0,
   262  			},
   263  		},
   264  		{
   265  			// Test searching with an error tolerance. Allowing 1%
   266  			// error makes searches 6x faster in the case of regular
   267  			// loops with a large number of vertices.
   268  			benchCase: "ClosestToPointErrorPoint1Pct",
   269  			opts: &edgeQueryBenchmarkOptions{
   270  				includeInteriors:         false,
   271  				targetType:               queryTypePoint,
   272  				numTargetEdges:           0,
   273  				chooseTargetFromIndex:    false,
   274  				radiusKm:                 1000,
   275  				maxDistanceFraction:      -1,
   276  				maxErrorFraction:         0.1,
   277  				targetRadiusFraction:     0.0,
   278  				centerSeparationFraction: -2.0,
   279  			},
   280  		},
   281  		{
   282  			// Test searching with an error tolerance. Allowing 1%
   283  			// error makes searches 6x faster in the case of regular
   284  			// loops with a large number of vertices.
   285  			benchCase: "ClosestToPointErrorPoint01Pct",
   286  			opts: &edgeQueryBenchmarkOptions{
   287  				includeInteriors:         false,
   288  				targetType:               queryTypePoint,
   289  				numTargetEdges:           0,
   290  				chooseTargetFromIndex:    false,
   291  				radiusKm:                 1000,
   292  				maxDistanceFraction:      -1,
   293  				maxErrorFraction:         0.01,
   294  				targetRadiusFraction:     0.0,
   295  				centerSeparationFraction: -2.0,
   296  			},
   297  		},
   298  		{
   299  			benchCase: "ClosestToEdge",
   300  			opts: &edgeQueryBenchmarkOptions{
   301  				includeInteriors:         false,
   302  				targetType:               queryTypeEdge,
   303  				numTargetEdges:           0,
   304  				chooseTargetFromIndex:    false,
   305  				radiusKm:                 1000,
   306  				maxDistanceFraction:      -1,
   307  				maxErrorFraction:         -1,
   308  				targetRadiusFraction:     -1.0,
   309  				centerSeparationFraction: -2.0,
   310  			},
   311  		},
   312  		{
   313  			benchCase: "ClosestToCell",
   314  			opts: &edgeQueryBenchmarkOptions{
   315  				includeInteriors:         false,
   316  				targetType:               queryTypeCell,
   317  				numTargetEdges:           0,
   318  				chooseTargetFromIndex:    false,
   319  				radiusKm:                 1000,
   320  				maxDistanceFraction:      -1,
   321  				maxErrorFraction:         -1,
   322  				targetRadiusFraction:     -1.0,
   323  				centerSeparationFraction: -2.0,
   324  			},
   325  		},
   326  	}
   327  
   328  	for _, bench := range benchmarks {
   329  		for _, g := range generators {
   330  			bench.opts.indexGenerator = g.gen
   331  			b.Run(fmt.Sprintf("%s/%s", bench.benchCase, g.name), func(b *testing.B) {
   332  				benchmarkEdgeQueryFindClosest(b, bench.opts)
   333  			})
   334  		}
   335  	}
   336  }
   337  
   338  // TODO(roberts): Remaining tests to implement.
   339  //
   340  // TestClosestEdgeQueryTestReuseOfQuery) {
   341  // TestClosestEdgeQueryTargetPointInsideIndexedPolygon) {
   342  // TestClosestEdgeQueryTargetPointOutsideIndexedPolygon) {
   343  // TestClosestEdgeQueryTargetPolygonContainingIndexedPoints) {
   344  // TestClosestEdgeQueryEmptyTargetOptimized) {
   345  // TestClosestEdgeQueryEmptyPolygonTarget) {
   346  // TestClosestEdgeQueryFullLaxPolygonTarget) {
   347  // TestClosestEdgeQueryFullS2PolygonTarget) {
   348  // TestClosestEdgeQueryIsConservativeDistanceLessOrEqual) {
   349  // TestClosestEdgeQueryCircleEdges) {
   350  // TestClosestEdgeQueryFractalEdges) {
   351  // TestClosestEdgeQueryPointCloudEdges) {
   352  // TestClosestEdgeQueryConservativeCellDistanceIsUsed) {
   353  //
   354  // Add the remaining Benchmarking cases for each generator type.
   355  // FindClosestMaxDistPow10
   356  // FindClosestNearVertex
   357  // FindClosestNearVertexMaxDistPow10
   358  // FindClosestToEdgeInterior
   359  // FindClosestToEdgeNearEdge
   360  // FindClosestToCellInterior
   361  // FindClosestToCellInIndex
   362  // FindClosestToSmallAbuttingIndex
   363  // FindClosestFromSmallAbuttingIndex
   364  // FindClosestToSameSizeAbuttingIndex
   365  // FindClosestToSameSizeContainedIndex
   366  // FindClosestToSameSizeContainingIndex
   367  // FindClosestToSameSizeDistantIndex
   368  // IsDistanceLessSameSizeDistantIndexFalse
   369  // IsDistanceLessSameSizeDistantIndexTrue
   370  // FindClosestToSmallIndexEdgeSample
   371
View as plain text