edge_query_furthest_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  	"testing"
    19  
    20  	"github.com/golang/geo/s1"
    21  )
    22  
    23  func TestFurthestEdgeQueryNoEdges(t *testing.T) {
    24  	index := &ShapeIndex{}
    25  	query := NewFurthestEdgeQuery(index, nil)
    26  	target := NewMaxDistanceToPointTarget(PointFromCoords(1, 0, 0))
    27  	edge := query.findEdge(target, query.opts)
    28  
    29  	if edge.shapeID != -1 {
    30  		t.Errorf("shapeID for empty index should be -1, got %v", edge.shapeID)
    31  	}
    32  	if edge.edgeID != -1 {
    33  		t.Errorf("edgeID for empty index should be -1, got %v", edge.edgeID)
    34  	}
    35  	if got, want := edge.Distance(), s1.NegativeChordAngle; got != want {
    36  		t.Errorf("edge.Distance = %+v, want %+v", got, want)
    37  	}
    38  	if got, want := query.Distance(target), s1.NegativeChordAngle; got != want {
    39  		t.Errorf("query.Distance(%v) = %+v, want %+v", target, got, want)
    40  	}
    41  }
    42  
    43  func TestFurthestEdgeQueryBasicTest(t *testing.T) {
    44  	index := makeShapeIndex("0:1 | 0:2 | 0:3 # #")
    45  	query := NewFurthestEdgeQuery(index, NewFurthestEdgeQueryOptions().
    46  		MaxResults(3).
    47  		DistanceLimit(s1.ChordAngleFromAngle(s1.Angle(1)*s1.Degree)).
    48  		MaxError(s1.ChordAngleFromAngle(s1.Angle(0.001)*s1.Degree)))
    49  	target := NewMaxDistanceToPointTarget(parsePoint("0:4"))
    50  
    51  	result := query.findEdge(target, query.opts)
    52  
    53  	if result.edgeID != 0 {
    54  		t.Errorf("query.findEdge(%v).edgeID = %v, want %v", target, result.edgeID, 0)
    55  	}
    56  
    57  	if got, want := query.Distance(target).Angle().Degrees(), 3.0; !float64Near(got, want, epsilon) {
    58  		t.Errorf("query.Distance(%v) = %v, want %v", target, got, want)
    59  	}
    60  	if !query.IsDistanceGreater(target, s1.ChordAngleFromAngle(s1.Angle(1.5)*s1.Degree)) {
    61  		t.Errorf("query.IsDistanceGreater(%v, 1.5) should be true but wasn't", target)
    62  	}
    63  }
    64  
    65  func TestFurthestEdgeQueryAntipodalPointInsideIndexedPolygon(t *testing.T) {
    66  	// Tests a target point antipodal to the interior of an indexed polygon.
    67  	// (The index also includes a polyline loop with no interior.)
    68  	index := makeShapeIndex("# 0:0, 0:5, 5:5, 5:0 # 0:10, 0:15, 5:15, 5:10")
    69  
    70  	// First check that with include_interiors set to true, the distance is 180.
    71  	query := NewFurthestEdgeQuery(index, NewFurthestEdgeQueryOptions().
    72  		IncludeInteriors(true).
    73  		DistanceLimit(s1.ChordAngleFromAngle(s1.Angle(178)*s1.Degree)))
    74  	target := NewMaxDistanceToPointTarget(Point{parsePoint("2:12").Mul(-1)})
    75  
    76  	results := query.FindEdges(target)
    77  
    78  	if len(results) < 1 {
    79  		t.Errorf("aa")
    80  	}
    81  	result := results[0]
    82  	if result.Distance() != s1.StraightChordAngle {
    83  		t.Errorf("result.Distance = %v, want %v", result.Distance(), s1.StraightChordAngle)
    84  	}
    85  	// Should find the polygon shape (id = 1).
    86  	if result.shapeID != 1 {
    87  		t.Errorf("result.shapeID of result should be 1, was %v", result.shapeID)
    88  	}
    89  	// Should find the interior, so no specific edge id.
    90  	if result.edgeID != -1 {
    91  		t.Errorf("result.edgeID = %v, want -1", result.edgeID)
    92  	}
    93  
    94  	// Next check that with include_interiors set to false, the distance is less
    95  	// than 180 for the same target and index.
    96  	query.opts.IncludeInteriors(false)
    97  	results = query.FindEdges(target)
    98  
    99  	if len(results) <= 0 {
   100  		t.Errorf("findEdges returned no results, should have been at least 1")
   101  		return
   102  	}
   103  	result = results[0]
   104  	if result.Distance() > s1.StraightChordAngle {
   105  		t.Errorf("result.Distance = %v, want less than %v", result.Distance(), s1.StraightChordAngle)
   106  	}
   107  	if result.shapeID != 1 {
   108  		t.Errorf("result.shapeID = %v, want 1", result.shapeID)
   109  	}
   110  	// Found a specific edge, so id should be positive.
   111  	if result.edgeID == -1 {
   112  		t.Errorf("result.edgeID = %v, want >= 0", result.edgeID)
   113  	}
   114  }
   115  
   116  func TestFurthestEdgeQueryAntipodalPointOutsideIndexedPolygon(t *testing.T) {
   117  	// Tests a target point antipodal to the interior of a polyline loop with no
   118  	// interior.  The index also includes a polygon almost antipodal to the
   119  	// target, but with all edges closer than the min_distance threshold.
   120  	index := makeShapeIndex("# 0:0, 0:5, 5:5, 5:0 # 0:10, 0:15, 5:15, 5:10")
   121  	query := NewFurthestEdgeQuery(index, NewFurthestEdgeQueryOptions().
   122  		IncludeInteriors(true).
   123  		DistanceLimit(s1.ChordAngleFromAngle(s1.Angle(179)*s1.Degree)))
   124  	target := NewMaxDistanceToPointTarget(Point{parsePoint("2:2").Mul(-1)})
   125  
   126  	results := query.FindEdges(target)
   127  	if len(results) != 0 {
   128  		t.Errorf("len(query.FindEdges(target)) = %d, want 0", len(results))
   129  	}
   130  }
   131  
   132  func TestFurthestEdgeQueryTargetPolygonContainingIndexedPoints(t *testing.T) {
   133  	// Two points are contained within a polyline loop (no interior) and two
   134  	// points are contained within a polygon.
   135  	index := makeShapeIndex("2:2 | 4:4 | 1:11 | 3:12 # #")
   136  	query := NewFurthestEdgeQuery(index, NewFurthestEdgeQueryOptions().UseBruteForce(false))
   137  
   138  	targetIndex := makeShapeIndex("# 0:0, 0:5, 5:5, 5:0 # 0:10, 0:15, 5:15, 5:10")
   139  	target := NewMaxDistanceToShapeIndexTarget(targetIndex)
   140  	target.setIncludeInteriors(true)
   141  	target.setUseBruteForce(true)
   142  	results := query.FindEdges(target)
   143  
   144  	// All points should be returned since we did not specify max_results.
   145  	if len(results) != 4 {
   146  		t.Errorf("All 4 shapes should have matched. Got %d shapes", len(results))
   147  	}
   148  
   149  	r0 := results[0]
   150  	if r0.Distance() == 0 {
   151  		t.Errorf("result[0].Distance = 0, want non-zero")
   152  	}
   153  	if r0.shapeID != 0 {
   154  		t.Errorf("result[0].shapeID = %v, want 0", r0.shapeID)
   155  	}
   156  	if r0.edgeID != 0 {
   157  		t.Errorf("result[0].edgeID = %v, want 0", r0.edgeID) // 2:2 (to 5:15)
   158  	}
   159  
   160  	r1 := results[1]
   161  	if r1.Distance() == 0 {
   162  		t.Errorf("result[1].Distance = 0, want non-zero")
   163  	}
   164  	if r1.shapeID != 0 {
   165  		t.Errorf("result[1].shapeID = %v, want 0", r1.shapeID)
   166  	}
   167  	if r1.edgeID != 3 {
   168  		t.Errorf("result[1].edgeID = %v, want 3", r1.edgeID) // 3:12 (to 0:0)
   169  	}
   170  }
   171  
   172  func TestFurthestEdgeQueryAntipodalPolygonContainingIndexedPoints(t *testing.T) {
   173  	// Two antipodal points are contained within a polyline loop (no interior)
   174  	// and two antipodal points are contained within a polygon.
   175  	index := NewShapeIndex()
   176  	pts := parsePoints("2:2, 3:3, 1:11, 3:13")
   177  	antipodalPts := reflectPoints(pts)
   178  	pv := PointVector(antipodalPts)
   179  	index.Add(&pv)
   180  
   181  	query := NewFurthestEdgeQuery(index, NewFurthestEdgeQueryOptions().
   182  		DistanceLimit(s1.ChordAngleFromAngle(s1.Angle(179)*s1.Degree)),
   183  	)
   184  	targetIndex := makeShapeIndex("# 0:0, 0:5, 5:5, 5:0 # 0:10, 0:15, 5:15, 5:10")
   185  	target := NewMaxDistanceToShapeIndexTarget(targetIndex)
   186  	target.setIncludeInteriors(true)
   187  	results := query.FindEdges(target)
   188  
   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() != s1.StraightChordAngle {
   195  		t.Errorf("result[1].Distance = %v, want %v", r0.Distance(), s1.StraightChordAngle)
   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 2", r0.edgeID) // 1:11
   202  	}
   203  
   204  	r1 := results[1]
   205  	if r1.Distance() != s1.StraightChordAngle {
   206  		t.Errorf("result[1].Distance = %v, want %v", r1.Distance(), s1.StraightChordAngle)
   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  func TestFurthestEdgeQueryEmptyPolygonTarget(t *testing.T) {
   217  	// Verifies that distances are measured correctly to empty polygon targets.
   218  	emptyPolygonIndex := makeShapeIndex("# # empty")
   219  	pointIndex := makeShapeIndex("1:1 # #")
   220  	fullPolygonIndex := makeShapeIndex("# # full")
   221  
   222  	target := NewMaxDistanceToShapeIndexTarget(emptyPolygonIndex)
   223  
   224  	emptyQuery := NewFurthestEdgeQuery(emptyPolygonIndex, NewFurthestEdgeQueryOptions().IncludeInteriors(true))
   225  	if got, want := emptyQuery.Distance(target), s1.NegativeChordAngle; got != want {
   226  		t.Errorf("emptyQuery.Distance(%v) = %v, want %v", target, got, want)
   227  	}
   228  
   229  	pointQuery := NewFurthestEdgeQuery(pointIndex, NewFurthestEdgeQueryOptions().IncludeInteriors(true))
   230  	if got, want := pointQuery.Distance(target), s1.NegativeChordAngle; got != want {
   231  		t.Errorf("pointQuery.Distance(%v) = %v, want %v", target, got, want)
   232  	}
   233  
   234  	fullQuery := NewFurthestEdgeQuery(fullPolygonIndex, NewFurthestEdgeQueryOptions().IncludeInteriors(true))
   235  	if got, want := fullQuery.Distance(target), s1.NegativeChordAngle; got != want {
   236  		t.Errorf("fullQuery.Distance(%v) = %v, want %v", target, got, want)
   237  	}
   238  }
   239  
   240  func TestFurthestEdgeQueryFullPolygonTarget(t *testing.T) {
   241  	// Verifies that distances are measured correctly to full Polygon targets
   242  	// (which use a different representation of "full" than LaxPolygon does).
   243  	emptyPolygonIndex := makeShapeIndex("# # empty")
   244  	pointIndex := makeShapeIndex("1:1 # #")
   245  	fullPolygonIndex := makeShapeIndex("# #")
   246  	fullPolygonIndex.Add(makePolygon("full", true))
   247  
   248  	target := NewMaxDistanceToShapeIndexTarget(fullPolygonIndex)
   249  
   250  	emptyQuery := NewFurthestEdgeQuery(emptyPolygonIndex, NewFurthestEdgeQueryOptions().IncludeInteriors(true))
   251  	if got, want := emptyQuery.Distance(target), s1.NegativeChordAngle; got != want {
   252  		t.Errorf("emptyQuery.Distance(%v) = %v, want %v", target, got, want)
   253  	}
   254  
   255  	pointQuery := NewFurthestEdgeQuery(pointIndex, NewFurthestEdgeQueryOptions().IncludeInteriors(true))
   256  	if got, want := pointQuery.Distance(target), s1.StraightChordAngle; got != want {
   257  		t.Errorf("pointQuery.Distance(%v) = %v, want %v", target, got, want)
   258  	}
   259  
   260  	fullQuery := NewFurthestEdgeQuery(fullPolygonIndex, NewFurthestEdgeQueryOptions().IncludeInteriors(true))
   261  	if got, want := fullQuery.Distance(target), s1.StraightChordAngle; got != want {
   262  		t.Errorf("fullQuery.Distance(%v) = %v, want %v", target, got, want)
   263  	}
   264  }
   265  
   266  /*
   267  func TestFurthestEdgeQueryCircleEdges(t *testing.T) {
   268  	testEdgeQueryWithGenerator(t,
   269  		NewFurthestEdgeQuery,
   270  		NewFurthestEdgeQueryOptions,
   271  		loopShapeIndexGenerator, edgeQueryTestNumIndexes,
   272  		edgeQueryTestNumEdges, edgeQueryTestNumQueries)
   273  }
   274  func TestFurthestEdgeQueryFractalEdges(t *testing.T) {
   275  	testEdgeQueryWithGenerator(t,
   276  		NewFurthestEdgeQuery,
   277  		NewFurthestEdgeQueryOptions,
   278  		fractalLoopShapeIndexGenerator, edgeQueryTestNumIndexes,
   279  		edgeQueryTestNumEdges, edgeQueryTestNumQueries)
   280  }
   281  func TestFurthestEdgeQueryPointCloudEdges(t *testing.T) {
   282  	testEdgeQueryWithGenerator(t,
   283  		NewFurthestEdgeQuery,
   284  		NewFurthestEdgeQueryOptions,
   285  		pointCloudShapeIndexGenerator, edgeQueryTestNumIndexes,
   286  		edgeQueryTestNumEdges, edgeQueryTestNumQueries)
   287  }
   288  */
   289  
   290  // TODO(roberts): Remaining tests to implement.
   291  //
   292  // func TestFurthestEdgeQueryDistanceEqualToLimit(t *testing.T) {}
   293  // func TestFurthestEdgeQueryTrueDistanceGreaterThanChordAngleDistance(t *testing.T) { }
   294  // func TestFurthestEdgeQueryFullLaxPolygonTarget(t *testing.T) {}
   295
View as plain text