Source file src/github.com/golang/geo/s1/interval_test.go

Documentation: github.com/golang/geo/s1

     1  // Copyright 2014 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 s1
    16  
    17  import (
    18  	"math"
    19  	"testing"
    20  )
    21  
    22  // Some standard intervals for use throughout the tests.
    23  // These include the intervals spanning one or more "quadrants" which are
    24  // numbered as follows:
    25  //
    26  //	quad1 == [0, π/2]
    27  //	quad2 == [π/2, π]
    28  //	quad3 == [-π, -π/2]
    29  //	quad4 == [-π/2, 0]
    30  var (
    31  	empty = EmptyInterval()
    32  	full  = FullInterval()
    33  	// Single-point intervals:
    34  	zero  = IntervalFromEndpoints(0, 0)
    35  	pi2   = IntervalFromEndpoints(math.Pi/2, math.Pi/2)
    36  	pi    = IntervalFromEndpoints(math.Pi, math.Pi)
    37  	mipi  = IntervalFromEndpoints(-math.Pi, -math.Pi) // same as pi after normalization
    38  	mipi2 = IntervalFromEndpoints(-math.Pi/2, -math.Pi/2)
    39  	// Single quadrants:
    40  	quad1 = IntervalFromEndpoints(0, math.Pi/2)
    41  	quad2 = IntervalFromEndpoints(math.Pi/2, -math.Pi) // equivalent to (pi/2, pi)
    42  	quad3 = IntervalFromEndpoints(math.Pi, -math.Pi/2)
    43  	quad4 = IntervalFromEndpoints(-math.Pi/2, 0)
    44  	// Quadrant pairs:
    45  	quad12 = IntervalFromEndpoints(0, -math.Pi)
    46  	quad23 = IntervalFromEndpoints(math.Pi/2, -math.Pi/2)
    47  	quad34 = IntervalFromEndpoints(-math.Pi, 0)
    48  	quad41 = IntervalFromEndpoints(-math.Pi/2, math.Pi/2)
    49  	// Quadrant triples:
    50  	quad123 = IntervalFromEndpoints(0, -math.Pi/2)
    51  	quad234 = IntervalFromEndpoints(math.Pi/2, 0)
    52  	quad341 = IntervalFromEndpoints(math.Pi, math.Pi/2)
    53  	quad412 = IntervalFromEndpoints(-math.Pi/2, -math.Pi)
    54  	// Small intervals around the midpoints between quadrants,
    55  	// such that the center of each interval is offset slightly CCW from the midpoint.
    56  	mid12 = IntervalFromEndpoints(math.Pi/2-0.01, math.Pi/2+0.02)
    57  	mid23 = IntervalFromEndpoints(math.Pi-0.01, -math.Pi+0.02)
    58  	mid34 = IntervalFromEndpoints(-math.Pi/2-0.01, -math.Pi/2+0.02)
    59  	mid41 = IntervalFromEndpoints(-0.01, 0.02)
    60  )
    61  
    62  func TestConstructors(t *testing.T) {
    63  	// Check that [-π,-π] is normalized to [π,π].
    64  	if mipi.Lo != math.Pi {
    65  		t.Errorf("mipi.Lo = %v, want π", mipi.Lo)
    66  	}
    67  	if mipi.Hi != math.Pi {
    68  		t.Errorf("mipi.Hi = %v, want π", mipi.Lo)
    69  	}
    70  
    71  	var i Interval
    72  	if !i.IsValid() {
    73  		t.Errorf("Zero value Interval is not valid")
    74  	}
    75  }
    76  
    77  func TestIntervalFromPointPair(t *testing.T) {
    78  	tests := []struct {
    79  		a, b float64
    80  		want Interval
    81  	}{
    82  		{-math.Pi, math.Pi, pi},
    83  		{math.Pi, -math.Pi, pi},
    84  		{mid34.Hi, mid34.Lo, mid34},
    85  		{mid23.Lo, mid23.Hi, mid23},
    86  	}
    87  	for _, test := range tests {
    88  		got := IntervalFromPointPair(test.a, test.b)
    89  		if got != test.want {
    90  			t.Errorf("IntervalFromPointPair(%f, %f) = %v, want %v", test.a, test.b, got, test.want)
    91  		}
    92  	}
    93  }
    94  
    95  func TestSimplePredicates(t *testing.T) {
    96  	if !zero.IsValid() || zero.IsEmpty() || zero.IsFull() {
    97  		t.Errorf("Zero interval is invalid or empty or full")
    98  	}
    99  	if !empty.IsValid() || !empty.IsEmpty() || empty.IsFull() {
   100  		t.Errorf("Empty interval is invalid or not empty or full")
   101  	}
   102  	if !empty.IsInverted() {
   103  		t.Errorf("Empty interval is not inverted")
   104  	}
   105  	if !full.IsValid() || full.IsEmpty() || !full.IsFull() {
   106  		t.Errorf("Full interval is invalid or empty or not full")
   107  	}
   108  	if !pi.IsValid() || pi.IsEmpty() || pi.IsInverted() {
   109  		t.Errorf("pi is invalid or empty or inverted")
   110  	}
   111  	if !mipi.IsValid() || mipi.IsEmpty() || mipi.IsInverted() {
   112  		t.Errorf("mipi is invalid or empty or inverted")
   113  	}
   114  }
   115  
   116  func TestAlmostFullOrEmpty(t *testing.T) {
   117  	// Test that rounding errors don't cause intervals that are almost empty or
   118  	// full to be considered empty or full.  The following value is the greatest
   119  	// representable value less than Pi.
   120  	almostPi := math.Pi - 2*dblEpsilon
   121  
   122  	i := Interval{-almostPi, math.Pi}
   123  	if i.IsFull() {
   124  		t.Errorf("%v.IsFull should not be true", i)
   125  	}
   126  
   127  	i = Interval{-math.Pi, almostPi}
   128  	if i.IsFull() {
   129  		t.Errorf("%v.IsFull should not be true", i)
   130  	}
   131  
   132  	i = Interval{math.Pi, -almostPi}
   133  	if i.IsEmpty() {
   134  		t.Errorf("%v.IsEmpty should not be true", i)
   135  	}
   136  
   137  	i = Interval{almostPi, -math.Pi}
   138  	if i.IsEmpty() {
   139  		t.Errorf("%v.IsEmpty should not be true", i)
   140  	}
   141  }
   142  
   143  func TestCenter(t *testing.T) {
   144  	tests := []struct {
   145  		interval Interval
   146  		want     float64
   147  	}{
   148  		{quad12, math.Pi / 2},
   149  		{IntervalFromEndpoints(3.1, 2.9), 3 - math.Pi},
   150  		{IntervalFromEndpoints(-2.9, -3.1), math.Pi - 3},
   151  		{IntervalFromEndpoints(2.1, -2.1), math.Pi},
   152  		{pi, math.Pi},
   153  		{mipi, math.Pi},
   154  		// TODO(dsymonds): The C++ test for quad23 uses fabs. Why?
   155  		{quad23, math.Pi},
   156  		// TODO(dsymonds): The C++ test for quad123 uses EXPECT_DOUBLE_EQ. Why?
   157  		{quad123, 0.75 * math.Pi},
   158  	}
   159  	for _, test := range tests {
   160  		got := test.interval.Center()
   161  		// TODO(dsymonds): Some are inaccurate in the 16th decimal place. Track it down.
   162  		if math.Abs(got-test.want) > 1e-15 {
   163  			t.Errorf("%v.Center() = %v, want %v", test.interval, got, test.want)
   164  		}
   165  	}
   166  }
   167  
   168  func TestLength(t *testing.T) {
   169  	tests := []struct {
   170  		interval Interval
   171  		want     float64
   172  	}{
   173  		{quad12, math.Pi},
   174  		{pi, 0},
   175  		{mipi, 0},
   176  		// TODO(dsymonds): The C++ test for quad123 uses DOUBLE_EQ. Why?
   177  		{quad123, 1.5 * math.Pi},
   178  		// TODO(dsymonds): The C++ test for quad23 uses fabs. Why?
   179  		{quad23, math.Pi},
   180  		{full, 2 * math.Pi},
   181  	}
   182  	for _, test := range tests {
   183  		if l := test.interval.Length(); l != test.want {
   184  			t.Errorf("%v.Length() got %v, want %v", test.interval, l, test.want)
   185  		}
   186  	}
   187  	if l := empty.Length(); l >= 0 {
   188  		t.Errorf("empty interval has non-negative length %v", l)
   189  	}
   190  }
   191  
   192  func TestContains(t *testing.T) {
   193  	tests := []struct {
   194  		interval  Interval
   195  		in, out   []float64 // points that should be inside/outside the interval
   196  		iIn, iOut []float64 // points that should be inside/outside the interior
   197  	}{
   198  		{empty, nil, []float64{0, math.Pi, -math.Pi}, nil, []float64{math.Pi, -math.Pi}},
   199  		{full, []float64{0, math.Pi, -math.Pi}, nil, []float64{math.Pi, -math.Pi}, nil},
   200  		{quad12, []float64{0, math.Pi, -math.Pi}, nil,
   201  			[]float64{math.Pi / 2}, []float64{0, math.Pi, -math.Pi}},
   202  		{quad23, []float64{math.Pi / 2, -math.Pi / 2, math.Pi, -math.Pi}, []float64{0},
   203  			[]float64{math.Pi, -math.Pi}, []float64{math.Pi / 2, -math.Pi / 2, 0}},
   204  		{pi, []float64{math.Pi, -math.Pi}, []float64{0}, nil, []float64{math.Pi, -math.Pi}},
   205  		{mipi, []float64{math.Pi, -math.Pi}, []float64{0}, nil, []float64{math.Pi, -math.Pi}},
   206  		{zero, []float64{0}, nil, nil, []float64{0}},
   207  	}
   208  	for _, test := range tests {
   209  		for _, p := range test.in {
   210  			if !test.interval.Contains(p) {
   211  				t.Errorf("%v should contain %v", test.interval, p)
   212  			}
   213  		}
   214  		for _, p := range test.out {
   215  			if test.interval.Contains(p) {
   216  				t.Errorf("%v should not contain %v", test.interval, p)
   217  			}
   218  		}
   219  		for _, p := range test.iIn {
   220  			if !test.interval.InteriorContains(p) {
   221  				t.Errorf("interior of %v should contain %v", test.interval, p)
   222  			}
   223  		}
   224  		for _, p := range test.iOut {
   225  			if test.interval.InteriorContains(p) {
   226  				t.Errorf("interior %v should not contain %v", test.interval, p)
   227  			}
   228  		}
   229  	}
   230  }
   231  
   232  func TestIntervalOperations(t *testing.T) {
   233  	quad12eps := IntervalFromEndpoints(quad12.Lo, mid23.Hi)
   234  	quad2hi := IntervalFromEndpoints(mid23.Lo, quad12.Hi)
   235  	quad412eps := IntervalFromEndpoints(mid34.Lo, quad12.Hi)
   236  	quadeps12 := IntervalFromEndpoints(mid41.Lo, quad12.Hi)
   237  	quad1lo := IntervalFromEndpoints(quad12.Lo, mid41.Hi)
   238  	quad2lo := IntervalFromEndpoints(quad23.Lo, mid12.Hi)
   239  	quad3hi := IntervalFromEndpoints(mid34.Lo, quad23.Hi)
   240  	quadeps23 := IntervalFromEndpoints(mid12.Lo, quad23.Hi)
   241  	quad23eps := IntervalFromEndpoints(quad23.Lo, mid34.Hi)
   242  	quadeps123 := IntervalFromEndpoints(mid41.Lo, quad23.Hi)
   243  
   244  	// This massive list of test cases is ported directly from the C++ test case.
   245  	tests := []struct {
   246  		x, y                               Interval
   247  		xContainsY, xInteriorContainsY     bool
   248  		xIntersectsY, xInteriorIntersectsY bool
   249  		wantUnion, wantIntersection        Interval
   250  	}{
   251  		// 0
   252  		{empty, empty, true, true, false, false, empty, empty},
   253  		{empty, full, false, false, false, false, full, empty},
   254  		{empty, zero, false, false, false, false, zero, empty},
   255  		{empty, pi, false, false, false, false, pi, empty},
   256  		{empty, mipi, false, false, false, false, mipi, empty},
   257  
   258  		// 5
   259  		{full, empty, true, true, false, false, full, empty},
   260  		{full, full, true, true, true, true, full, full},
   261  		{full, zero, true, true, true, true, full, zero},
   262  		{full, pi, true, true, true, true, full, pi},
   263  		{full, mipi, true, true, true, true, full, mipi},
   264  		{full, quad12, true, true, true, true, full, quad12},
   265  		{full, quad23, true, true, true, true, full, quad23},
   266  
   267  		// 12
   268  		{zero, empty, true, true, false, false, zero, empty},
   269  		{zero, full, false, false, true, false, full, zero},
   270  		{zero, zero, true, false, true, false, zero, zero},
   271  		{zero, pi, false, false, false, false, IntervalFromEndpoints(0, math.Pi), empty},
   272  		{zero, pi2, false, false, false, false, quad1, empty},
   273  		{zero, mipi, false, false, false, false, quad12, empty},
   274  		{zero, mipi2, false, false, false, false, quad4, empty},
   275  		{zero, quad12, false, false, true, false, quad12, zero},
   276  		{zero, quad23, false, false, false, false, quad123, empty},
   277  
   278  		// 21
   279  		{pi2, empty, true, true, false, false, pi2, empty},
   280  		{pi2, full, false, false, true, false, full, pi2},
   281  		{pi2, zero, false, false, false, false, quad1, empty},
   282  		{pi2, pi, false, false, false, false, IntervalFromEndpoints(math.Pi/2, math.Pi), empty},
   283  		{pi2, pi2, true, false, true, false, pi2, pi2},
   284  		{pi2, mipi, false, false, false, false, quad2, empty},
   285  		{pi2, mipi2, false, false, false, false, quad23, empty},
   286  		{pi2, quad12, false, false, true, false, quad12, pi2},
   287  		{pi2, quad23, false, false, true, false, quad23, pi2},
   288  
   289  		// 30
   290  		{pi, empty, true, true, false, false, pi, empty},
   291  		{pi, full, false, false, true, false, full, pi},
   292  		{pi, zero, false, false, false, false, IntervalFromEndpoints(math.Pi, 0), empty},
   293  		{pi, pi, true, false, true, false, pi, pi},
   294  		{pi, pi2, false, false, false, false, IntervalFromEndpoints(math.Pi/2, math.Pi), empty},
   295  		{pi, mipi, true, false, true, false, pi, pi},
   296  		{pi, mipi2, false, false, false, false, quad3, empty},
   297  		{pi, quad12, false, false, true, false, IntervalFromEndpoints(0, math.Pi), pi},
   298  		{pi, quad23, false, false, true, false, quad23, pi},
   299  
   300  		// 39
   301  		{mipi, empty, true, true, false, false, mipi, empty},
   302  		{mipi, full, false, false, true, false, full, mipi},
   303  		{mipi, zero, false, false, false, false, quad34, empty},
   304  		{mipi, pi, true, false, true, false, mipi, mipi},
   305  		{mipi, pi2, false, false, false, false, quad2, empty},
   306  		{mipi, mipi, true, false, true, false, mipi, mipi},
   307  		{mipi, mipi2, false, false, false, false, IntervalFromEndpoints(-math.Pi, -math.Pi/2), empty},
   308  		{mipi, quad12, false, false, true, false, quad12, mipi},
   309  		{mipi, quad23, false, false, true, false, quad23, mipi},
   310  
   311  		// 48
   312  		{quad12, empty, true, true, false, false, quad12, empty},
   313  		{quad12, full, false, false, true, true, full, quad12},
   314  		{quad12, zero, true, false, true, false, quad12, zero},
   315  		{quad12, pi, true, false, true, false, quad12, pi},
   316  		{quad12, mipi, true, false, true, false, quad12, mipi},
   317  		{quad12, quad12, true, false, true, true, quad12, quad12},
   318  		{quad12, quad23, false, false, true, true, quad123, quad2},
   319  		{quad12, quad34, false, false, true, false, full, quad12},
   320  
   321  		// 56
   322  		{quad23, empty, true, true, false, false, quad23, empty},
   323  		{quad23, full, false, false, true, true, full, quad23},
   324  		{quad23, zero, false, false, false, false, quad234, empty},
   325  		{quad23, pi, true, true, true, true, quad23, pi},
   326  		{quad23, mipi, true, true, true, true, quad23, mipi},
   327  		{quad23, quad12, false, false, true, true, quad123, quad2},
   328  		{quad23, quad23, true, false, true, true, quad23, quad23},
   329  		{quad23, quad34, false, false, true, true, quad234, IntervalFromEndpoints(-math.Pi, -math.Pi/2)},
   330  
   331  		// 64
   332  		{quad1, quad23, false, false, true, false, quad123, IntervalFromEndpoints(math.Pi/2, math.Pi/2)},
   333  		{quad2, quad3, false, false, true, false, quad23, mipi},
   334  		{quad3, quad2, false, false, true, false, quad23, pi},
   335  		{quad2, pi, true, false, true, false, quad2, pi},
   336  		{quad2, mipi, true, false, true, false, quad2, mipi},
   337  		{quad3, pi, true, false, true, false, quad3, pi},
   338  		{quad3, mipi, true, false, true, false, quad3, mipi},
   339  
   340  		// 71
   341  		{quad12, mid12, true, true, true, true, quad12, mid12},
   342  		{mid12, quad12, false, false, true, true, quad12, mid12},
   343  
   344  		// 73
   345  		{quad12, mid23, false, false, true, true, quad12eps, quad2hi},
   346  		{mid23, quad12, false, false, true, true, quad12eps, quad2hi},
   347  
   348  		// This test checks that the union of two disjoint intervals is the smallest
   349  		// interval that contains both of them.  Note that the center of "mid34"
   350  		// slightly CCW of -Pi/2 so that there is no ambiguity about the result.
   351  		// 75
   352  		{quad12, mid34, false, false, false, false, quad412eps, empty},
   353  		{mid34, quad12, false, false, false, false, quad412eps, empty},
   354  
   355  		// 77
   356  		{quad12, mid41, false, false, true, true, quadeps12, quad1lo},
   357  		{mid41, quad12, false, false, true, true, quadeps12, quad1lo},
   358  
   359  		// 79
   360  		{quad23, mid12, false, false, true, true, quadeps23, quad2lo},
   361  		{mid12, quad23, false, false, true, true, quadeps23, quad2lo},
   362  		{quad23, mid23, true, true, true, true, quad23, mid23},
   363  		{mid23, quad23, false, false, true, true, quad23, mid23},
   364  		{quad23, mid34, false, false, true, true, quad23eps, quad3hi},
   365  		{mid34, quad23, false, false, true, true, quad23eps, quad3hi},
   366  		{quad23, mid41, false, false, false, false, quadeps123, empty},
   367  		{mid41, quad23, false, false, false, false, quadeps123, empty},
   368  	}
   369  	should := func(b bool) string {
   370  		if b {
   371  			return "should"
   372  		}
   373  		return "should not"
   374  	}
   375  	for _, test := range tests {
   376  		if test.x.ContainsInterval(test.y) != test.xContainsY {
   377  			t.Errorf("%v %s contain %v", test.x, should(test.xContainsY), test.y)
   378  		}
   379  		if test.x.InteriorContainsInterval(test.y) != test.xInteriorContainsY {
   380  			t.Errorf("interior of %v %s contain %v", test.x, should(test.xInteriorContainsY), test.y)
   381  		}
   382  		if test.x.Intersects(test.y) != test.xIntersectsY {
   383  			t.Errorf("%v %s intersect %v", test.x, should(test.xIntersectsY), test.y)
   384  		}
   385  		if test.x.InteriorIntersects(test.y) != test.xInteriorIntersectsY {
   386  			t.Errorf("interior of %v %s intersect %v", test.x, should(test.xInteriorIntersectsY), test.y)
   387  		}
   388  		if u := test.x.Union(test.y); u != test.wantUnion {
   389  			t.Errorf("%v ∪ %v was %v, want %v", test.x, test.y, u, test.wantUnion)
   390  		}
   391  		if u := test.x.Intersection(test.y); u != test.wantIntersection {
   392  			t.Errorf("%v ∩ %v was %v, want %v", test.x, test.y, u, test.wantIntersection)
   393  		}
   394  	}
   395  }
   396  
   397  func TestAddPoint(t *testing.T) {
   398  	tests := []struct {
   399  		interval Interval
   400  		points   []float64
   401  		want     Interval
   402  	}{
   403  		{empty, []float64{0}, zero},
   404  		{empty, []float64{math.Pi}, pi},
   405  		{empty, []float64{-math.Pi}, mipi},
   406  		{empty, []float64{math.Pi, -math.Pi}, pi},
   407  		{empty, []float64{-math.Pi, math.Pi}, mipi},
   408  		{empty, []float64{mid12.Lo, mid12.Hi}, mid12},
   409  		{empty, []float64{mid23.Lo, mid23.Hi}, mid23},
   410  
   411  		{quad1, []float64{-0.9 * math.Pi, -math.Pi / 2}, quad123},
   412  		{full, []float64{0}, full},
   413  		{full, []float64{math.Pi}, full},
   414  		{full, []float64{-math.Pi}, full},
   415  	}
   416  	for _, test := range tests {
   417  		got := test.interval
   418  		for _, point := range test.points {
   419  			got = got.AddPoint(point)
   420  		}
   421  		want := test.want
   422  		if math.Abs(got.Lo-want.Lo) > 1e-15 || math.Abs(got.Hi-want.Hi) > 1e-15 {
   423  			t.Errorf("%v.AddPoint(%v) = %v, want %v", test.interval, test.points, got, want)
   424  		}
   425  	}
   426  }
   427  
   428  func TestExpanded(t *testing.T) {
   429  	tests := []struct {
   430  		interval Interval
   431  		margin   float64
   432  		want     Interval
   433  	}{
   434  		{empty, 1, empty},
   435  		{full, 1, full},
   436  		{zero, 1, Interval{-1, 1}},
   437  		{mipi, 0.01, Interval{math.Pi - 0.01, -math.Pi + 0.01}},
   438  		{pi, 27, full},
   439  		{pi, math.Pi / 2, quad23},
   440  		{pi2, math.Pi / 2, quad12},
   441  		{mipi2, math.Pi / 2, quad34},
   442  
   443  		{empty, -1, empty},
   444  		{full, -1, full},
   445  		{quad123, -27, empty},
   446  		{quad234, -27, empty},
   447  		{quad123, -math.Pi / 2, quad2},
   448  		{quad341, -math.Pi / 2, quad4},
   449  		{quad412, -math.Pi / 2, quad1},
   450  	}
   451  	for _, test := range tests {
   452  		if got, want := test.interval.Expanded(test.margin), test.want; math.Abs(got.Lo-want.Lo) > 1e-15 || math.Abs(got.Hi-want.Hi) > 1e-15 {
   453  			t.Errorf("%v.Expanded(%v) = %v, want %v", test.interval, test.margin, got, want)
   454  		}
   455  	}
   456  }
   457  
   458  func TestIntervalString(t *testing.T) {
   459  	if s, exp := pi.String(), "[3.1415927, 3.1415927]"; s != exp {
   460  		t.Errorf("pi.String() = %q, want %q", s, exp)
   461  	}
   462  }
   463  
   464  func TestIntervalApproxEqual(t *testing.T) {
   465  	// Choose two values lo and hi such that it's okay to shift an endpoint by
   466  	// lo (i.e., the resulting interval is equivalent) but not by hi.
   467  	lo := 4 * dblEpsilon // < epsilon default
   468  	hi := 6 * dblEpsilon // > epsilon default
   469  
   470  	tests := []struct {
   471  		a, b Interval
   472  		want bool
   473  	}{
   474  		// Empty intervals.
   475  		{a: empty, b: empty, want: true},
   476  		{a: zero, b: empty, want: true},
   477  		{a: empty, b: zero, want: true},
   478  		{a: pi, b: empty, want: true},
   479  		{a: empty, b: pi, want: true},
   480  		{a: mipi, b: empty, want: true},
   481  		{a: empty, b: mipi, want: true},
   482  		{a: empty, b: full, want: false},
   483  		{a: empty, b: Interval{1, 1 + 2*lo}, want: true},
   484  		{a: empty, b: Interval{1, 1 + 2*hi}, want: false},
   485  		{a: Interval{math.Pi - lo, -math.Pi + lo}, b: empty, want: true},
   486  
   487  		// Full intervals.
   488  		{a: full, b: full, want: true},
   489  		{a: full, b: empty, want: false},
   490  		{a: full, b: zero, want: false},
   491  		{a: full, b: pi, want: false},
   492  		{a: full, b: Interval{lo, -lo}, want: true},
   493  		{a: full, b: Interval{2 * hi, 0}, want: false},
   494  		{a: Interval{-math.Pi + lo, math.Pi - lo}, b: full, want: true},
   495  		{a: Interval{-math.Pi, math.Pi - 2*hi}, b: full, want: false},
   496  
   497  		// Singleton intervals.
   498  		{a: pi, b: pi, want: true},
   499  		{a: mipi, b: pi, want: true},
   500  		{a: pi, b: Interval{math.Pi - lo, math.Pi - lo}, want: true},
   501  		{a: pi, b: Interval{math.Pi - hi, math.Pi - hi}, want: false},
   502  		{a: pi, b: Interval{math.Pi - lo, -math.Pi + lo}, want: true},
   503  		{a: pi, b: Interval{math.Pi - hi, -math.Pi}, want: false},
   504  		{a: zero, b: pi, want: false},
   505  		{a: pi.Union(mid12).Union(zero), b: quad12, want: true},
   506  		{a: quad2.Intersection(quad3), b: pi, want: true},
   507  		{a: quad3.Intersection(quad2), b: pi, want: true},
   508  
   509  		// Intervals whose corresponding endpoints are nearly the same but where the
   510  		// endpoints are in opposite order (i.e., inverted intervals).
   511  		{a: Interval{0, lo}, b: Interval{lo, 0}, want: false},
   512  		{a: Interval{math.Pi - 0.5*lo, -math.Pi + 0.5*lo}, b: Interval{-math.Pi + 0.5*lo, math.Pi - 0.5*lo}, want: false},
   513  
   514  		// Other intervals.
   515  		{a: Interval{1 - lo, 2 + lo}, b: Interval{1, 2}, want: true},
   516  		{a: Interval{1 + lo, 2 - lo}, b: Interval{1, 2}, want: true},
   517  		{a: Interval{2 - lo, 1 + lo}, b: Interval{2, 1}, want: true},
   518  		{a: Interval{2 + lo, 1 - lo}, b: Interval{2, 1}, want: true},
   519  		{a: Interval{1 - hi, 2 + lo}, b: Interval{1, 2}, want: false},
   520  		{a: Interval{1 + hi, 2 - lo}, b: Interval{1, 2}, want: false},
   521  		{a: Interval{2 - hi, 1 + lo}, b: Interval{2, 1}, want: false},
   522  		{a: Interval{2 + hi, 1 - lo}, b: Interval{2, 1}, want: false},
   523  		{a: Interval{1 - lo, 2 + hi}, b: Interval{1, 2}, want: false},
   524  		{a: Interval{1 + lo, 2 - hi}, b: Interval{1, 2}, want: false},
   525  		{a: Interval{2 - lo, 1 + hi}, b: Interval{2, 1}, want: false},
   526  		{a: Interval{2 + lo, 1 - hi}, b: Interval{2, 1}, want: false},
   527  	}
   528  
   529  	for _, test := range tests {
   530  		if got := test.a.ApproxEqual(test.b); got != test.want {
   531  			t.Errorf("%v.ApproxEqual(%v) = %t, want %t", test.a, test.b, got, test.want)
   532  		}
   533  	}
   534  }
   535  
   536  func TestIntervalComplement(t *testing.T) {
   537  	if !EmptyInterval().Complement().IsFull() {
   538  		t.Error("empty interval's complement is not full, but should be")
   539  	}
   540  	if !FullInterval().Complement().IsEmpty() {
   541  		t.Error("full interval's complement is not empty, but should be")
   542  	}
   543  	if !pi.Complement().IsFull() {
   544  		t.Errorf("pi's (%v) complement is not full, but should be", pi)
   545  	}
   546  	if !mipi.Complement().IsFull() {
   547  		t.Errorf("mipi's (%v) complement is not full, but should be", mipi)
   548  	}
   549  	if !zero.Complement().IsFull() {
   550  		t.Errorf("zero's (%v) complement is not full, but should be", zero)
   551  	}
   552  
   553  	if got := quad12.Complement(); !got.ApproxEqual(quad34) {
   554  		t.Errorf("%v.Complement = %v, want %v", quad12, got, quad34)
   555  	}
   556  	if got := quad34.Complement(); !got.ApproxEqual(quad12) {
   557  		t.Errorf("%v.Complement = %v, want %v", quad34, got, quad12)
   558  	}
   559  	if got := quad123.Complement(); !got.ApproxEqual(quad4) {
   560  		t.Errorf("%v.Complement = %v, want %v", quad123, got, quad4)
   561  	}
   562  }
   563  
   564  func TestIntervalDirectedHausdorff(t *testing.T) {
   565  	in := Interval{3.0, -3.0}
   566  	tests := []struct {
   567  		i, y Interval
   568  		want Angle
   569  	}{
   570  		{Interval{-0.139626, 0.349066}, Interval{0.139626, 0.139626}, 0.279252 * Radian},
   571  		{Interval{0.2, 0.4}, Interval{0.1, 0.5}, 0 * Radian},
   572  		{Interval{0, 0}, EmptyInterval(), math.Pi * Radian},
   573  		{empty, empty, 0.0},
   574  		{empty, mid12, 0.0},
   575  		{mid12, empty, math.Pi},
   576  		{quad12, quad123, 0.0},
   577  		{Interval{-0.1, 0.2}, in, 3.0},
   578  		{Interval{0.1, 0.2}, in, 3.0 - 0.1},
   579  		{Interval{-0.2, -0.1}, in, 3.0 - 0.1},
   580  	}
   581  
   582  	for _, test := range tests {
   583  		got := test.i.DirectedHausdorffDistance(test.y)
   584  		if math.Abs(float64(got-test.want)) > 1e-15 {
   585  			t.Errorf("%v.DirectedHausdorffDistance(%v) = %v, want %v", test.i, test.y, got.Radians(), test.want.Radians())
   586  		}
   587  	}
   588  }
   589  
   590  func TestIntervalProject(t *testing.T) {
   591  	r := IntervalFromEndpoints(-math.Pi, -math.Pi)
   592  	r1 := IntervalFromEndpoints(0, math.Pi)
   593  	r2 := IntervalFromEndpoints(math.Pi-0.1, -math.Pi+0.1)
   594  	tests := []struct {
   595  		interval Interval
   596  		have     float64
   597  		want     float64
   598  	}{
   599  		{r, -math.Pi, math.Pi},
   600  		{r, 0, math.Pi},
   601  
   602  		{r1, 0.1, 0.1},
   603  		{r1, -math.Pi/2 + 1e-15, 0},
   604  		{r1, -math.Pi/2 - 1e-15, math.Pi},
   605  		{r2, math.Pi, math.Pi},
   606  		{r2, 1e-15, math.Pi - 0.1},
   607  		{r2, -1e-15, -math.Pi + 0.1},
   608  		{full, 0, 0},
   609  		{full, math.Pi, math.Pi},
   610  		{full, -math.Pi, math.Pi},
   611  	}
   612  
   613  	for _, test := range tests {
   614  		if got := test.interval.Project(test.have); !float64Eq(got, test.want) {
   615  			t.Errorf("%v.Project(%v) = %v, want %v", test.interval, test.have, got, test.want)
   616  		}
   617  	}
   618  }
   619  

View as plain text