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

Documentation: github.com/golang/geo/s2

     1  // Copyright 2016 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/r3"
    23  	"github.com/golang/geo/s1"
    24  )
    25  
    26  func TestPolylineBasics(t *testing.T) {
    27  	empty := Polyline{}
    28  	if empty.RectBound() != EmptyRect() {
    29  		t.Errorf("empty.RectBound() = %v, want %v", empty.RectBound(), EmptyRect())
    30  	}
    31  	if len(empty) != 0 {
    32  		t.Errorf("empty Polyline should have no vertices")
    33  	}
    34  	empty.Reverse()
    35  	if len(empty) != 0 {
    36  		t.Errorf("reveresed empty Polyline should have no vertices")
    37  	}
    38  
    39  	latlngs := []LatLng{
    40  		LatLngFromDegrees(0, 0),
    41  		LatLngFromDegrees(0, 90),
    42  		LatLngFromDegrees(0, 180),
    43  	}
    44  
    45  	semiEquator := PolylineFromLatLngs(latlngs)
    46  	want := PointFromCoords(0, 1, 0)
    47  	if got, _ := semiEquator.Interpolate(0.5); !got.ApproxEqual(want) {
    48  		t.Errorf("semiEquator.Interpolate(0.5) = %v, want %v", got, want)
    49  	}
    50  	semiEquator.Reverse()
    51  	if got, want := (*semiEquator)[2], (Point{r3.Vector{1, 0, 0}}); !got.ApproxEqual(want) {
    52  		t.Errorf("semiEquator[2] = %v, want %v", got, want)
    53  	}
    54  }
    55  
    56  func TestPolylineShape(t *testing.T) {
    57  	var shape Shape = makePolyline("0:0, 1:0, 1:1, 2:1")
    58  	if got, want := shape.NumEdges(), 3; got != want {
    59  		t.Errorf("%v.NumEdges() = %v, want %d", shape, got, want)
    60  	}
    61  	if got, want := shape.NumChains(), 1; got != want {
    62  		t.Errorf("%v.NumChains() = %d, want %d", shape, got, want)
    63  	}
    64  	if got, want := shape.Chain(0).Start, 0; got != want {
    65  		t.Errorf("%v.Chain(0).Start = %d, want %d", shape, got, want)
    66  	}
    67  	if got, want := shape.Chain(0).Length, 3; got != want {
    68  		t.Errorf("%v.Chain(0).Length = %d, want %d", shape, got, want)
    69  	}
    70  
    71  	e := shape.Edge(2)
    72  	if want := PointFromLatLng(LatLngFromDegrees(1, 1)); !e.V0.ApproxEqual(want) {
    73  		t.Errorf("%v.Edge(%d) point A = %v  want %v", shape, 2, e.V0, want)
    74  	}
    75  	if want := PointFromLatLng(LatLngFromDegrees(2, 1)); !e.V1.ApproxEqual(want) {
    76  		t.Errorf("%v.Edge(%d) point B = %v  want %v", shape, 2, e.V1, want)
    77  	}
    78  	if shape.ReferencePoint().Contained {
    79  		t.Errorf("polylines should not contain their reference points")
    80  	}
    81  	if got, want := shape.Dimension(), 1; got != want {
    82  		t.Errorf("shape.Dimension() = %v, want %v", got, want)
    83  	}
    84  }
    85  
    86  func TestPolylineEmpty(t *testing.T) {
    87  	shape := &Polyline{}
    88  	if got, want := shape.NumEdges(), 0; got != want {
    89  		t.Errorf("%v.NumEdges() = %d, want %d", shape, got, want)
    90  	}
    91  	if got, want := shape.NumChains(), 0; got != want {
    92  		t.Errorf("%v.NumChains() = %d, want %d", shape, got, want)
    93  	}
    94  	if !shape.IsEmpty() {
    95  		t.Errorf("shape.IsEmpty() = false, want true")
    96  	}
    97  	if shape.IsFull() {
    98  		t.Errorf("shape.IsFull() = true, want false")
    99  	}
   100  	if shape.ReferencePoint().Contained {
   101  		t.Errorf("polylines should not contain their reference points")
   102  	}
   103  }
   104  
   105  func TestPolylineLengthAndCentroid(t *testing.T) {
   106  	// Construct random great circles and divide them randomly into segments.
   107  	// Then make sure that the length and centroid are correct.  Note that
   108  	// because of the way the centroid is computed, it does not matter how
   109  	// we split the great circle into segments.
   110  
   111  	for i := 0; i < 100; i++ {
   112  		// Choose a coordinate frame for the great circle.
   113  		f := randomFrame()
   114  
   115  		var line Polyline
   116  		for theta := 0.0; theta < 2*math.Pi; theta += math.Pow(randomFloat64(), 10) {
   117  			p := Point{f.row(0).Mul(math.Cos(theta)).Add(f.row(1).Mul(math.Sin(theta)))}
   118  			if len(line) == 0 || !p.ApproxEqual(line[len(line)-1]) {
   119  				line = append(line, p)
   120  			}
   121  		}
   122  
   123  		// Close the circle.
   124  		line = append(line, line[0])
   125  
   126  		length := line.Length()
   127  		if got, want := math.Abs(length.Radians()-2*math.Pi), 2e-14; got > want {
   128  			t.Errorf("%v.Length() = %v, want < %v", line, got, want)
   129  		}
   130  
   131  		centroid := line.Centroid()
   132  		if got, want := centroid.Norm(), 2e-14; got > want {
   133  			t.Errorf("%v.Norm() = %v, want < %v", centroid, got, want)
   134  		}
   135  	}
   136  }
   137  
   138  func TestPolylineIntersectsCell(t *testing.T) {
   139  	pline := Polyline{
   140  		Point{r3.Vector{1, -1.1, 0.8}.Normalize()},
   141  		Point{r3.Vector{1, -0.8, 1.1}.Normalize()},
   142  	}
   143  
   144  	for face := 0; face < 6; face++ {
   145  		cell := CellFromCellID(CellIDFromFace(face))
   146  		if got, want := pline.IntersectsCell(cell), face&1 == 0; got != want {
   147  			t.Errorf("%v.IntersectsCell(%v) = %v, want %v", pline, cell, got, want)
   148  		}
   149  	}
   150  }
   151  
   152  func TestPolylineSubsample(t *testing.T) {
   153  	const polyStr = "0:0, 0:1, -1:2, 0:3, 0:4, 1:4, 2:4.5, 3:4, 3.5:4, 4:4"
   154  
   155  	tests := []struct {
   156  		have      string
   157  		tolerance float64
   158  		want      []int
   159  	}{
   160  		{
   161  			// No vertices.
   162  			tolerance: 1.0,
   163  		},
   164  		{
   165  			// One vertex.
   166  			have:      "0:1",
   167  			tolerance: 1.0,
   168  			want:      []int{0},
   169  		},
   170  		{
   171  			// Two vertices.
   172  			have:      "10:10, 11:11",
   173  			tolerance: 5.0,
   174  			want:      []int{0, 1},
   175  		},
   176  		{
   177  			// Three points on a straight line. In theory, zero tolerance
   178  			// should work, but in practice there are floating point errors.
   179  			have:      "-1:0, 0:0, 1:0",
   180  			tolerance: 1e-15,
   181  			want:      []int{0, 2},
   182  		},
   183  		{
   184  			// Zero tolerance on a non-straight line.
   185  			have:      "-1:0, 0:0, 1:1",
   186  			tolerance: 0.0,
   187  			want:      []int{0, 1, 2},
   188  		},
   189  		{
   190  			// Negative tolerance should return all vertices.
   191  			have:      "-1:0, 0:0, 1:1",
   192  			tolerance: -1.0,
   193  			want:      []int{0, 1, 2},
   194  		},
   195  		{
   196  			// Non-zero tolerance with a straight line.
   197  			have:      "0:1, 0:2, 0:3, 0:4, 0:5",
   198  			tolerance: 1.0,
   199  			want:      []int{0, 4},
   200  		},
   201  		{
   202  			// And finally, verify that we still do something
   203  			// reasonable if the client passes in an invalid polyline
   204  			// with two or more adjacent vertices.
   205  			have:      "0:1, 0:1, 0:1, 0:2",
   206  			tolerance: 0.0,
   207  			want:      []int{0, 3},
   208  		},
   209  
   210  		// Simple examples
   211  		{
   212  			have:      polyStr,
   213  			tolerance: 3.0,
   214  			want:      []int{0, 9},
   215  		},
   216  		{
   217  			have:      polyStr,
   218  			tolerance: 2.0,
   219  			want:      []int{0, 6, 9},
   220  		},
   221  		{
   222  			have:      polyStr,
   223  			tolerance: 0.9,
   224  			want:      []int{0, 2, 6, 9},
   225  		},
   226  		{
   227  			have:      polyStr,
   228  			tolerance: 0.4,
   229  			want:      []int{0, 1, 2, 3, 4, 6, 9},
   230  		},
   231  		{
   232  			have:      polyStr,
   233  			tolerance: 0,
   234  			want:      []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
   235  		},
   236  
   237  		// Check that duplicate vertices are never generated.
   238  		{
   239  			have:      "10:10, 12:12, 10:10",
   240  			tolerance: 5.0,
   241  			want:      []int{0},
   242  		},
   243  		{
   244  			have:      "0:0, 1:1, 0:0, 0:120, 0:130",
   245  			tolerance: 5.0,
   246  			want:      []int{0, 3, 4},
   247  		},
   248  
   249  		// Check that points are not collapsed if they would create a line segment
   250  		// longer than 90 degrees, and also that the code handles original polyline
   251  		// segments longer than 90 degrees.
   252  		{
   253  			have:      "90:0, 50:180, 20:180, -20:180, -50:180, -90:0, 30:0, 90:0",
   254  			tolerance: 5.0,
   255  			want:      []int{0, 2, 4, 5, 6, 7},
   256  		},
   257  
   258  		// Check that the output polyline is parametrically equivalent and not just
   259  		// geometrically equivalent, i.e. that backtracking is preserved.  The
   260  		// algorithm achieves this by requiring that the points must be encountered
   261  		// in increasing order of distance along each output segment, except for
   262  		// points that are within "tolerance" of the first vertex of each segment.
   263  		{
   264  			have:      "10:10, 10:20, 10:30, 10:15, 10:40",
   265  			tolerance: 5.0,
   266  			want:      []int{0, 2, 3, 4},
   267  		},
   268  		{
   269  			have:      "10:10, 10:20, 10:30, 10:10, 10:30, 10:40",
   270  			tolerance: 5.0,
   271  			want:      []int{0, 2, 3, 5},
   272  		},
   273  		{
   274  			have:      "10:10, 12:12, 9:9, 10:20, 10:30",
   275  			tolerance: 5.0,
   276  			want:      []int{0, 4},
   277  		},
   278  	}
   279  
   280  	for _, test := range tests {
   281  		p := makePolyline(test.have)
   282  		got := p.SubsampleVertices(s1.Angle(test.tolerance) * s1.Degree)
   283  		if !reflect.DeepEqual(got, test.want) {
   284  			t.Errorf("%q.SubsampleVertices(%v°) = %v, want %v", test.have, test.tolerance, got, test.want)
   285  		}
   286  	}
   287  }
   288  
   289  func TestProject(t *testing.T) {
   290  	latlngs := []LatLng{
   291  		LatLngFromDegrees(0, 0),
   292  		LatLngFromDegrees(0, 1),
   293  		LatLngFromDegrees(0, 2),
   294  		LatLngFromDegrees(1, 2),
   295  	}
   296  	line := PolylineFromLatLngs(latlngs)
   297  	tests := []struct {
   298  		haveLatLng     LatLng
   299  		wantProjection LatLng
   300  		wantNext       int
   301  	}{
   302  		{LatLngFromDegrees(0.5, -0.5), LatLngFromDegrees(0, 0), 1},
   303  		{LatLngFromDegrees(0.5, 0.5), LatLngFromDegrees(0, 0.5), 1},
   304  		{LatLngFromDegrees(0.5, 1), LatLngFromDegrees(0, 1), 2},
   305  		{LatLngFromDegrees(-0.5, 2.5), LatLngFromDegrees(0, 2), 3},
   306  		{LatLngFromDegrees(2, 2), LatLngFromDegrees(1, 2), 4},
   307  		{LatLngFromDegrees(-50, 0.5), LatLngFromDegrees(0, 0.5), 1},
   308  	}
   309  	for _, test := range tests {
   310  		projection, next := line.Project(PointFromLatLng(test.haveLatLng))
   311  		if !PointFromLatLng(test.wantProjection).ApproxEqual(projection) {
   312  			t.Errorf("line.Project(%v) = %v, want %v", test.haveLatLng, projection, test.wantProjection)
   313  		}
   314  		if next != test.wantNext {
   315  			t.Errorf("line.Project(%v) = %v, want %v", test.haveLatLng, next, test.wantNext)
   316  		}
   317  	}
   318  }
   319  
   320  func TestIsOnRight(t *testing.T) {
   321  	latlngs := []LatLng{
   322  		LatLngFromDegrees(0, 0),
   323  		LatLngFromDegrees(0, 1),
   324  		LatLngFromDegrees(0, 2),
   325  		LatLngFromDegrees(1, 2),
   326  	}
   327  	line1 := PolylineFromLatLngs(latlngs)
   328  	latlngs = []LatLng{
   329  		LatLngFromDegrees(0, 0),
   330  		LatLngFromDegrees(0, 1),
   331  		LatLngFromDegrees(-1, 0),
   332  	}
   333  	line2 := PolylineFromLatLngs(latlngs)
   334  	tests := []struct {
   335  		line        *Polyline
   336  		haveLatLng  LatLng
   337  		wantOnRight bool
   338  	}{
   339  		{line1, LatLngFromDegrees(-0.5, 0.5), true},
   340  		{line1, LatLngFromDegrees(0.5, -0.5), false},
   341  		{line1, LatLngFromDegrees(0.5, 0.5), false},
   342  		{line1, LatLngFromDegrees(0.5, 1.0), false},
   343  		{line1, LatLngFromDegrees(-0.5, 2.5), true},
   344  		{line1, LatLngFromDegrees(1.5, 2.5), true},
   345  		// Explicitly test the case where the closest point is an interior vertex.
   346  		// The points are chosen such that they are on different sides of the two
   347  		// edges that the interior vertex is on.
   348  		{line2, LatLngFromDegrees(-0.5, 5.0), false},
   349  		{line2, LatLngFromDegrees(5.5, 5.0), false},
   350  	}
   351  	for _, test := range tests {
   352  		onRight := test.line.IsOnRight(PointFromLatLng(test.haveLatLng))
   353  		if onRight != test.wantOnRight {
   354  			t.Errorf("line.IsOnRight(%v) = %v, want %v", test.haveLatLng, onRight, test.wantOnRight)
   355  		}
   356  	}
   357  }
   358  
   359  func TestPolylineValidate(t *testing.T) {
   360  	p := makePolyline("0:0, 2:1, 0:2, 2:3, 0:4, 2:5, 0:6")
   361  	if p.Validate() != nil {
   362  		t.Errorf("valid polygon should Validate")
   363  	}
   364  
   365  	p1 := Polyline([]Point{
   366  		PointFromCoords(0, 1, 0),
   367  		{r3.Vector{10, 3, 7}},
   368  		PointFromCoords(0, 0, 1),
   369  	})
   370  
   371  	if err := p1.Validate(); err == nil {
   372  		t.Errorf("polyline with non-normalized points shouldn't validate")
   373  	}
   374  
   375  	// adjacent equal vertices
   376  	p2 := Polyline([]Point{
   377  		PointFromCoords(0, 1, 0),
   378  		PointFromCoords(0, 0, 1),
   379  		PointFromCoords(0, 0, 1),
   380  		PointFromCoords(1, 0, 0),
   381  	})
   382  
   383  	if err := p2.Validate(); err == nil {
   384  		t.Errorf("polyline with repeated vertices shouldn't validate")
   385  	}
   386  
   387  	pt := PointFromCoords(1, 1, 0)
   388  	antiPt := Point{pt.Mul(-1)}
   389  
   390  	// non-adjacent antipodal points.
   391  	p3 := Polyline([]Point{
   392  		PointFromCoords(0, 1, 0),
   393  		pt,
   394  		PointFromCoords(0, 0, 1),
   395  		antiPt,
   396  	})
   397  
   398  	if err := p3.Validate(); err != nil {
   399  		t.Errorf("polyline with non-adjacent antipodal points should validate")
   400  	}
   401  
   402  	// non-adjacent antipodal points.
   403  	p4 := Polyline([]Point{
   404  		PointFromCoords(0, 1, 0),
   405  		PointFromCoords(0, 0, 1),
   406  		pt,
   407  		antiPt,
   408  	})
   409  
   410  	if err := p4.Validate(); err == nil {
   411  		t.Errorf("polyline with antipodal adjacent points shouldn't validate")
   412  	}
   413  }
   414  
   415  func TestPolylineIntersects(t *testing.T) {
   416  	// PolylineInterectsEmpty
   417  	empty := Polyline{}
   418  	line := makePolyline("1:1, 4:4")
   419  	if empty.Intersects(line) {
   420  		t.Errorf("%v.Intersects(%v) = true, want false", empty, line)
   421  	}
   422  
   423  	// PolylineIntersectsOnePointPolyline
   424  	line1 := makePolyline("1:1, 4:4")
   425  	line2 := makePolyline("1:1")
   426  	if line1.Intersects(line2) {
   427  		t.Errorf("%v.Intersects(%v) = true, want false", line1, line2)
   428  	}
   429  
   430  	// PolylineIntersects
   431  	line3 := makePolyline("1:1, 4:4")
   432  	smallCrossing := makePolyline("1:2, 2:1")
   433  	smallNoncrossing := makePolyline("1:2, 2:3")
   434  	bigCrossing := makePolyline("1:2, 2:3, 4:3")
   435  	if !line3.Intersects(smallCrossing) {
   436  		t.Errorf("%v.Intersects(%v) = false, want true", line3, smallCrossing)
   437  	}
   438  	if line3.Intersects(smallNoncrossing) {
   439  		t.Errorf("%v.Intersects(%v) = true, want false", line3, smallNoncrossing)
   440  	}
   441  	if !line3.Intersects(bigCrossing) {
   442  		t.Errorf("%v.Intersects(%v) = false, want true", line3, bigCrossing)
   443  	}
   444  
   445  	// PolylineIntersectsAtVertex
   446  	line4 := makePolyline("1:1, 4:4, 4:6")
   447  	line5 := makePolyline("1:1, 1:2")
   448  	line6 := makePolyline("5:1, 4:4, 2:2")
   449  	if !line4.Intersects(line5) {
   450  		t.Errorf("%v.Intersects(%v) = false, want true", line4, line5)
   451  	}
   452  	if !line4.Intersects(line6) {
   453  		t.Errorf("%v.Intersects(%v) = false, want true", line4, line6)
   454  	}
   455  
   456  	// TestPolylineIntersectsVertexOnEdge
   457  	horizontalLeftToRight := makePolyline("0:1, 0:3")
   458  	verticalBottomToTop := makePolyline("-1:2, 0:2, 1:2")
   459  	horizontalRightToLeft := makePolyline("0:3, 0:1")
   460  	verticalTopToBottom := makePolyline("1:2, 0:2, -1:2")
   461  	if !horizontalLeftToRight.Intersects(verticalBottomToTop) {
   462  		t.Errorf("%v.Intersects(%v) = false, want true", horizontalLeftToRight, verticalBottomToTop)
   463  	}
   464  	if !horizontalLeftToRight.Intersects(verticalTopToBottom) {
   465  		t.Errorf("%v.Intersects(%v) = false, want true", horizontalLeftToRight, verticalTopToBottom)
   466  	}
   467  	if !horizontalRightToLeft.Intersects(verticalBottomToTop) {
   468  		t.Errorf("%v.Intersects(%v) = false, want true", horizontalRightToLeft, verticalBottomToTop)
   469  	}
   470  	if !horizontalRightToLeft.Intersects(verticalTopToBottom) {
   471  		t.Errorf("%v.Intersects(%v) = false, want true", horizontalRightToLeft, verticalTopToBottom)
   472  	}
   473  }
   474  
   475  func TestPolylineApproxEqual(t *testing.T) {
   476  	degree := s1.Angle(1) * s1.Degree
   477  
   478  	tests := []struct {
   479  		a, b     string
   480  		maxError s1.Angle
   481  		want     bool
   482  	}{
   483  		{
   484  			// Close lines, differences within maxError.
   485  			a:        "0:0, 0:10, 5:5",
   486  			b:        "0:0.1, -0.1:9.9, 5:5.2",
   487  			maxError: 0.5 * degree,
   488  			want:     true,
   489  		},
   490  		{
   491  			// Close lines, differences outside maxError.
   492  			a:        "0:0, 0:10, 5:5",
   493  			b:        "0:0.1, -0.1:9.9, 5:5.2",
   494  			maxError: 0.01 * degree,
   495  			want:     false,
   496  		},
   497  		{
   498  			// Same line, but different number of vertices.
   499  			a:        "0:0, 0:10, 0:20",
   500  			b:        "0:0, 0:20",
   501  			maxError: 0.1 * degree,
   502  			want:     false,
   503  		},
   504  		{
   505  			// Same vertices, in different order.
   506  			a:        "0:0, 5:5, 0:10",
   507  			b:        "5:5, 0:10, 0:0",
   508  			maxError: 0.1 * degree,
   509  			want:     false,
   510  		},
   511  	}
   512  	for _, test := range tests {
   513  		a := makePolyline(test.a)
   514  		b := makePolyline(test.b)
   515  		if got := a.approxEqual(b, test.maxError); got != test.want {
   516  			t.Errorf("%v.approxEqual(%v, %v) = %v, want %v", a, b, test.maxError, got, test.want)
   517  		}
   518  	}
   519  }
   520  
   521  func TestPolylineInterpolate(t *testing.T) {
   522  	vertices := []Point{PointFromCoords(1, 0, 0),
   523  		PointFromCoords(0, 1, 0),
   524  		PointFromCoords(0, 1, 1),
   525  		PointFromCoords(0, 0, 1),
   526  	}
   527  	line := Polyline(vertices)
   528  
   529  	want := vertices[0]
   530  	point, next := line.Interpolate(-0.1)
   531  	if point != vertices[0] {
   532  		t.Errorf("%v.Interpolate(%v) = %v, want %v", line, -0.1, point, vertices[0])
   533  	}
   534  	if next != 1 {
   535  		t.Errorf("%v.Interpolate(%v) = %v, want %v", line, -0.1, next, 1)
   536  	}
   537  
   538  	want = PointFromCoords(1, math.Tan(0.2*math.Pi/2.0), 0)
   539  	if got, _ := line.Interpolate(0.1); !got.ApproxEqual(want) {
   540  		t.Errorf("%v.Interpolate(%v) = %v, want %v", line, 0.1, got, want)
   541  	}
   542  
   543  	want = PointFromCoords(1, 1, 0)
   544  	if got, _ := line.Interpolate(0.25); !got.ApproxEqual(want) {
   545  		t.Errorf("%v.Interpolate(%v) = %v, want %v", line, 0.25, got, want)
   546  	}
   547  
   548  	want = vertices[1]
   549  	if got, _ := line.Interpolate(0.5); got != want {
   550  		t.Errorf("%v.Interpolate(%v) = %v, want %v", line, 0.5, got, want)
   551  	}
   552  
   553  	want = vertices[2]
   554  	point, next = line.Interpolate(0.75)
   555  	if !point.ApproxEqual(want) {
   556  		t.Errorf("%v.Interpolate(%v) = %v, want %v", line, 0.75, point, want)
   557  	}
   558  	if next != 3 {
   559  		t.Errorf("%v.Interpolate(%v) = %v, want %v", line, 0.75, next, 3)
   560  	}
   561  
   562  	point, next = line.Interpolate(1.1)
   563  	if point != vertices[3] {
   564  		t.Errorf("%v.Interpolate(%v) = %v, want %v", line, 1.1, point, vertices[3])
   565  	}
   566  	if next != 4 {
   567  		t.Errorf("%v.Interpolate(%v) = %v, want %v", line, 1.1, next, 4)
   568  	}
   569  
   570  	// Check the case where the interpolation fraction is so close to 1 that
   571  	// the interpolated point is identical to the last vertex.
   572  	vertices2 := []Point{PointFromCoords(1, 1, 1),
   573  		PointFromCoords(1, 1, 1+1e-15),
   574  		PointFromCoords(1, 1, 1+2e-15),
   575  	}
   576  	shortLine := Polyline(vertices2)
   577  
   578  	point, next = shortLine.Interpolate(1.0 - 2e-16)
   579  	if point != vertices2[2] {
   580  		t.Errorf("%v.Interpolate(%v) = %v, want %v", shortLine, 1.0-2e-16, point, vertices2[2])
   581  	}
   582  	if next != 3 {
   583  		t.Errorf("%v.Interpolate(%v) = %v, want %v", shortLine, 1.0-2e-16, next, 3)
   584  	}
   585  }
   586  
   587  func TestPolylineUninterpolate(t *testing.T) {
   588  	vertices := []Point{PointFromCoords(1, 0, 0)}
   589  	line := Polyline(vertices)
   590  	if got, want := line.Uninterpolate(PointFromCoords(0, 1, 0), 1), 0.0; !float64Eq(got, want) {
   591  		t.Errorf("Uninterpolate on a polyline with 2 or fewer vertices should return 0, got %v", got)
   592  	}
   593  
   594  	vertices = append(vertices,
   595  		PointFromCoords(0, 1, 0),
   596  		PointFromCoords(0, 1, 1),
   597  		PointFromCoords(0, 0, 1),
   598  	)
   599  	line = Polyline(vertices)
   600  
   601  	interpolated, nextVertex := line.Interpolate(-0.1)
   602  	if got, want := line.Uninterpolate(interpolated, nextVertex), 0.0; !float64Eq(got, want) {
   603  		t.Errorf("line.Uninterpolate(%v, %d) = %v, want %v", interpolated, nextVertex, got, want)
   604  	}
   605  	interpolated, nextVertex = line.Interpolate(0.0)
   606  	if got, want := line.Uninterpolate(interpolated, nextVertex), 0.0; !float64Eq(got, want) {
   607  		t.Errorf("line.Uninterpolate(%v, %d) = %v, want %v", interpolated, nextVertex, got, want)
   608  	}
   609  	interpolated, nextVertex = line.Interpolate(0.5)
   610  	if got, want := line.Uninterpolate(interpolated, nextVertex), 0.5; !float64Eq(got, want) {
   611  		t.Errorf("line.Uninterpolate(%v, %d) = %v, want %v", interpolated, nextVertex, got, want)
   612  	}
   613  	interpolated, nextVertex = line.Interpolate(0.75)
   614  	if got, want := line.Uninterpolate(interpolated, nextVertex), 0.75; !float64Eq(got, want) {
   615  		t.Errorf("line.Uninterpolate(%v, %d) = %v, want %v", interpolated, nextVertex, got, want)
   616  	}
   617  	interpolated, nextVertex = line.Interpolate(1.1)
   618  	if got, want := line.Uninterpolate(interpolated, nextVertex), 1.0; !float64Eq(got, want) {
   619  		t.Errorf("line.Uninterpolate(%v, %d) = %v, want %v", interpolated, nextVertex, got, want)
   620  	}
   621  
   622  	// Check that the return value is clamped to 1.0.
   623  	if got, want := line.Uninterpolate(PointFromCoords(0, 1, 0), len(line)), 1.0; !float64Eq(got, want) {
   624  		t.Errorf("line.Uninterpolate(%v, %d) = %v, want %v", PointFromCoords(0, 1, 0), len(line), got, want)
   625  	}
   626  }
   627  
   628  // TODO(roberts): Test differences from C++:
   629  // InitToSnapped
   630  // InitToSimplified
   631  //
   632  // PolylineCoveringTest
   633  //    PolylineOverlapsSelf
   634  //    PolylineDoesNotOverlapReverse
   635  //    PolylineOverlapsEquivalent
   636  //    ShortCoveredByLong
   637  //    PartialOverlapOnly
   638  //    ShortBacktracking
   639  //    LongBacktracking
   640  //    IsResilientToDuplicatePoints
   641  //    CanChooseBetweenTwoPotentialStartingPoints
   642  //    StraightAndWigglyPolylinesCoverEachOther
   643  //    MatchStartsAtLastVertex
   644  //    MatchStartsAtDuplicatedLastVertex
   645  //    EmptyPolylines
   646  

View as plain text