Source file src/github.com/golang/geo/s2/edge_clipping_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  	"fmt"
    19  	"math"
    20  	"testing"
    21  
    22  	"github.com/golang/geo/r1"
    23  	"github.com/golang/geo/r2"
    24  	"github.com/golang/geo/r3"
    25  	"github.com/golang/geo/s1"
    26  )
    27  
    28  func TestEdgeClippingIntersectsFace(t *testing.T) {
    29  	tests := []struct {
    30  		a    pointUVW
    31  		want bool
    32  	}{
    33  		{pointUVW{r3.Vector{2.05335e-06, 3.91604e-22, 2.90553e-06}}, false},
    34  		{pointUVW{r3.Vector{-3.91604e-22, -2.05335e-06, -2.90553e-06}}, false},
    35  		{pointUVW{r3.Vector{0.169258, -0.169258, 0.664013}}, false},
    36  		{pointUVW{r3.Vector{0.169258, -0.169258, -0.664013}}, false},
    37  		{pointUVW{r3.Vector{math.Sqrt(2.0 / 3.0), -math.Sqrt(2.0 / 3.0), 3.88578e-16}}, true},
    38  		{pointUVW{r3.Vector{-3.88578e-16, -math.Sqrt(2.0 / 3.0), math.Sqrt(2.0 / 3.0)}}, true},
    39  	}
    40  
    41  	for _, test := range tests {
    42  		if got := test.a.intersectsFace(); got != test.want {
    43  			t.Errorf("%v.intersectsFace() = %v, want %v", test.a, got, test.want)
    44  		}
    45  	}
    46  }
    47  
    48  func TestEdgeClippingIntersectsOppositeEdges(t *testing.T) {
    49  	tests := []struct {
    50  		a    pointUVW
    51  		want bool
    52  	}{
    53  		{pointUVW{r3.Vector{0.169258, -0.169258, 0.664013}}, false},
    54  		{pointUVW{r3.Vector{0.169258, -0.169258, -0.664013}}, false},
    55  
    56  		{pointUVW{r3.Vector{-math.Sqrt(4.0 / 3.0), 0, -math.Sqrt(4.0 / 3.0)}}, true},
    57  		{pointUVW{r3.Vector{math.Sqrt(4.0 / 3.0), 0, math.Sqrt(4.0 / 3.0)}}, true},
    58  
    59  		{pointUVW{r3.Vector{-math.Sqrt(2.0 / 3.0), -math.Sqrt(2.0 / 3.0), 1.66533453694e-16}}, false},
    60  		{pointUVW{r3.Vector{math.Sqrt(2.0 / 3.0), math.Sqrt(2.0 / 3.0), -1.66533453694e-16}}, false},
    61  	}
    62  	for _, test := range tests {
    63  		if got := test.a.intersectsOppositeEdges(); got != test.want {
    64  			t.Errorf("%v.intersectsOppositeEdges() = %v, want %v", test.a, got, test.want)
    65  		}
    66  	}
    67  }
    68  
    69  func TestEdgeClippingExitAxis(t *testing.T) {
    70  	tests := []struct {
    71  		a    pointUVW
    72  		want axis
    73  	}{
    74  		{pointUVW{r3.Vector{0, -math.Sqrt(2.0 / 3.0), math.Sqrt(2.0 / 3.0)}}, axisU},
    75  		{pointUVW{r3.Vector{0, math.Sqrt(4.0 / 3.0), -math.Sqrt(4.0 / 3.0)}}, axisU},
    76  		{pointUVW{r3.Vector{-math.Sqrt(4.0 / 3.0), -math.Sqrt(4.0 / 3.0), 0}}, axisV},
    77  		{pointUVW{r3.Vector{math.Sqrt(4.0 / 3.0), math.Sqrt(4.0 / 3.0), 0}}, axisV},
    78  		{pointUVW{r3.Vector{math.Sqrt(2.0 / 3.0), -math.Sqrt(2.0 / 3.0), 0}}, axisV},
    79  		{pointUVW{r3.Vector{1.67968702783622, 0, 0.870988820096491}}, axisV},
    80  		{pointUVW{r3.Vector{0, math.Sqrt2, math.Sqrt2}}, axisU},
    81  	}
    82  
    83  	for _, test := range tests {
    84  		if got := test.a.exitAxis(); got != test.want {
    85  			t.Errorf("%v.exitAxis() = %v, want %v", test.a, got, test.want)
    86  		}
    87  	}
    88  }
    89  
    90  func TestEdgeClippingExitPoint(t *testing.T) {
    91  	tests := []struct {
    92  		a        pointUVW
    93  		exitAxis axis
    94  		want     r2.Point
    95  	}{
    96  		{pointUVW{r3.Vector{-3.88578058618805e-16, -math.Sqrt(2.0 / 3.0), math.Sqrt(2.0 / 3.0)}}, axisU, r2.Point{-1, 1}},
    97  		{pointUVW{r3.Vector{math.Sqrt(4.0 / 3.0), -math.Sqrt(4.0 / 3.0), 0}}, axisV, r2.Point{-1, -1}},
    98  		{pointUVW{r3.Vector{-math.Sqrt(4.0 / 3.0), -math.Sqrt(4.0 / 3.0), 0}}, axisV, r2.Point{-1, 1}},
    99  		{pointUVW{r3.Vector{-6.66134e-16, math.Sqrt(4.0 / 3.0), -math.Sqrt(4.0 / 3.0)}}, axisU, r2.Point{1, 1}},
   100  	}
   101  
   102  	for _, test := range tests {
   103  		if got := test.a.exitPoint(test.exitAxis); !r2PointsApproxEqual(got, test.want, epsilon) {
   104  			t.Errorf("%v.exitPoint() = %v, want %v", test.a, got, test.want)
   105  		}
   106  	}
   107  }
   108  
   109  // testClipToPaddedFace performs a comprehensive set of tests across all faces and
   110  // with random padding for the given points.
   111  //
   112  // We do this by defining an (x,y) coordinate system for the plane containing AB,
   113  // and converting points along the great circle AB to angles in the range
   114  // [-Pi, Pi]. We then accumulate the angle intervals spanned by each
   115  // clipped edge; the union over all 6 faces should approximately equal the
   116  // interval covered by the original edge.
   117  func testClipToPaddedFace(t *testing.T, a, b Point) {
   118  	a = Point{a.Normalize()}
   119  	b = Point{b.Normalize()}
   120  	if a.Vector == b.Mul(-1) {
   121  		return
   122  	}
   123  
   124  	// Test FaceSegements for this pair.
   125  	segments := FaceSegments(a, b)
   126  	n := len(segments)
   127  	if n == 0 {
   128  		t.Errorf("FaceSegments(%v, %v) should have generated at least one entry", a, b)
   129  	}
   130  
   131  	biunit := r2.Rect{r1.Interval{-1, 1}, r1.Interval{-1, 1}}
   132  	const errorRadians = faceClipErrorRadians
   133  
   134  	// The first and last vertices should approximately equal A and B.
   135  	if aPrime := faceUVToXYZ(segments[0].face, segments[0].a.X, segments[0].a.Y); a.Angle(aPrime) > errorRadians {
   136  		t.Errorf("%v.Angle(%v) = %v, want < %v", a, aPrime, a.Angle(aPrime), errorRadians)
   137  	}
   138  	if bPrime := faceUVToXYZ(segments[n-1].face, segments[n-1].b.X, segments[n-1].b.Y); b.Angle(bPrime) > errorRadians {
   139  		t.Errorf("%v.Angle(%v) = %v, want < %v", b, bPrime, b.Angle(bPrime), errorRadians)
   140  	}
   141  
   142  	norm := Point{a.PointCross(b).Normalize()}
   143  	aTan := Point{norm.Cross(a.Vector)}
   144  	bTan := Point{b.Cross(norm.Vector)}
   145  
   146  	for i := 0; i < n; i++ {
   147  		// Vertices may not protrude outside the biunit square.
   148  		if !biunit.ContainsPoint(segments[i].a) {
   149  			t.Errorf("biunit.ContainsPoint(%v) = false, want true", segments[i].a)
   150  		}
   151  		if !biunit.ContainsPoint(segments[i].b) {
   152  			t.Errorf("biunit.ContainsPoint(%v) = false, want true", segments[i].b)
   153  		}
   154  		if i == 0 {
   155  			continue
   156  		}
   157  
   158  		// The two representations of each interior vertex (on adjacent faces)
   159  		// must correspond to exactly the same Point.
   160  		if segments[i-1].face == segments[i].face {
   161  			t.Errorf("%v.face != %v.face", segments[i-1], segments[i])
   162  		}
   163  		if got, want := faceUVToXYZ(segments[i-1].face, segments[i-1].b.X, segments[i-1].b.Y),
   164  			faceUVToXYZ(segments[i].face, segments[i].a.X, segments[i].a.Y); !got.ApproxEqual(want) {
   165  			t.Errorf("interior vertices on adjacent faces should be the same point. got %v != %v", got, want)
   166  		}
   167  
   168  		// Interior vertices should be in the plane containing A and B, and should
   169  		// be contained in the wedge of angles between A and B (i.e., the dot
   170  		// products with aTan and bTan should be non-negative).
   171  		p := faceUVToXYZ(segments[i].face, segments[i].a.X, segments[i].a.Y).Normalize()
   172  		if got := math.Abs(p.Dot(norm.Vector)); got > errorRadians {
   173  			t.Errorf("%v.Dot(%v) = %v, want <= %v", p, norm, got, errorRadians)
   174  		}
   175  		if got := p.Dot(aTan.Vector); got < -errorRadians {
   176  			t.Errorf("%v.Dot(%v) = %v, want >= %v", p, aTan, got, -errorRadians)
   177  		}
   178  		if got := p.Dot(bTan.Vector); got < -errorRadians {
   179  			t.Errorf("%v.Dot(%v) = %v, want >= %v", p, bTan, got, -errorRadians)
   180  		}
   181  	}
   182  
   183  	padding := 0.0
   184  	if !oneIn(10) {
   185  		padding = 1e-10 * math.Pow(1e-5, randomFloat64())
   186  	}
   187  
   188  	xAxis := a
   189  	yAxis := aTan
   190  
   191  	// Given the points A and B, we expect all angles generated from the clipping
   192  	// to fall within this range.
   193  	expectedAngles := s1.Interval{0, float64(a.Angle(b.Vector))}
   194  	if expectedAngles.IsInverted() {
   195  		expectedAngles = s1.Interval{expectedAngles.Hi, expectedAngles.Lo}
   196  	}
   197  	maxAngles := expectedAngles.Expanded(faceClipErrorRadians)
   198  	var actualAngles s1.Interval
   199  
   200  	for face := 0; face < 6; face++ {
   201  		aUV, bUV, intersects := ClipToPaddedFace(a, b, face, padding)
   202  		if !intersects {
   203  			continue
   204  		}
   205  
   206  		aClip := Point{faceUVToXYZ(face, aUV.X, aUV.Y).Normalize()}
   207  		bClip := Point{faceUVToXYZ(face, bUV.X, bUV.Y).Normalize()}
   208  
   209  		desc := fmt.Sprintf("on face %d, a=%v, b=%v, aClip=%v, bClip=%v,", face, a, b, aClip, bClip)
   210  
   211  		if got := math.Abs(aClip.Dot(norm.Vector)); got > faceClipErrorRadians {
   212  			t.Errorf("%s abs(%v.Dot(%v)) = %v, want <= %v", desc, aClip, norm, got, faceClipErrorRadians)
   213  		}
   214  		if got := math.Abs(bClip.Dot(norm.Vector)); got > faceClipErrorRadians {
   215  			t.Errorf("%s abs(%v.Dot(%v)) = %v, want <= %v", desc, bClip, norm, got, faceClipErrorRadians)
   216  		}
   217  
   218  		if float64(aClip.Angle(a.Vector)) > faceClipErrorRadians {
   219  			if got := math.Max(math.Abs(aUV.X), math.Abs(aUV.Y)); !float64Eq(got, 1+padding) {
   220  				t.Errorf("%s the largest component of %v = %v, want %v", desc, aUV, got, 1+padding)
   221  			}
   222  		}
   223  		if float64(bClip.Angle(b.Vector)) > faceClipErrorRadians {
   224  			if got := math.Max(math.Abs(bUV.X), math.Abs(bUV.Y)); !float64Eq(got, 1+padding) {
   225  				t.Errorf("%s the largest component of %v = %v, want %v", desc, bUV, got, 1+padding)
   226  			}
   227  		}
   228  
   229  		aAngle := math.Atan2(aClip.Dot(yAxis.Vector), aClip.Dot(xAxis.Vector))
   230  		bAngle := math.Atan2(bClip.Dot(yAxis.Vector), bClip.Dot(xAxis.Vector))
   231  
   232  		// Rounding errors may cause bAngle to be slightly less than aAngle.
   233  		// We handle this by constructing the interval with FromPointPair,
   234  		// which is okay since the interval length is much less than math.Pi.
   235  		faceAngles := s1.IntervalFromEndpoints(aAngle, bAngle)
   236  		if faceAngles.IsInverted() {
   237  			faceAngles = s1.Interval{faceAngles.Hi, faceAngles.Lo}
   238  		}
   239  		if !maxAngles.ContainsInterval(faceAngles) {
   240  			t.Errorf("%s %v.ContainsInterval(%v) = false, but should have contained this interval", desc, maxAngles, faceAngles)
   241  		}
   242  		actualAngles = actualAngles.Union(faceAngles)
   243  	}
   244  	if !actualAngles.Expanded(faceClipErrorRadians).ContainsInterval(expectedAngles) {
   245  		t.Errorf("the union of all angle segments should be larger than the expected angle")
   246  	}
   247  }
   248  
   249  func TestEdgeClippingClipToPaddedFace(t *testing.T) {
   250  	// Start with a few simple cases.
   251  	// An edge that is entirely contained within one cube face:
   252  	testClipToPaddedFace(t, Point{r3.Vector{1, -0.5, -0.5}}, Point{r3.Vector{1, 0.5, 0.5}})
   253  	testClipToPaddedFace(t, Point{r3.Vector{1, 0.5, 0.5}}, Point{r3.Vector{1, -0.5, -0.5}})
   254  	// An edge that crosses one cube edge:
   255  	testClipToPaddedFace(t, Point{r3.Vector{1, 0, 0}}, Point{r3.Vector{0, 1, 0}})
   256  	testClipToPaddedFace(t, Point{r3.Vector{0, 1, 0}}, Point{r3.Vector{1, 0, 0}})
   257  	// An edge that crosses two opposite edges of face 0:
   258  	testClipToPaddedFace(t, Point{r3.Vector{0.75, 0, -1}}, Point{r3.Vector{0.75, 0, 1}})
   259  	testClipToPaddedFace(t, Point{r3.Vector{0.75, 0, 1}}, Point{r3.Vector{0.75, 0, -1}})
   260  	// An edge that crosses two adjacent edges of face 2:
   261  	testClipToPaddedFace(t, Point{r3.Vector{1, 0, 0.75}}, Point{r3.Vector{0, 1, 0.75}})
   262  	testClipToPaddedFace(t, Point{r3.Vector{0, 1, 0.75}}, Point{r3.Vector{1, 0, 0.75}})
   263  	// An edges that crosses three cube edges (four faces):
   264  	testClipToPaddedFace(t, Point{r3.Vector{1, 0.9, 0.95}}, Point{r3.Vector{-1, 0.95, 0.9}})
   265  	testClipToPaddedFace(t, Point{r3.Vector{-1, 0.95, 0.9}}, Point{r3.Vector{1, 0.9, 0.95}})
   266  
   267  	// Comprehensively test edges that are difficult to handle, especially those
   268  	// that nearly follow one of the 12 cube edges.
   269  	biunit := r2.Rect{r1.Interval{-1, 1}, r1.Interval{-1, 1}}
   270  
   271  	for i := 0; i < 1000; i++ {
   272  		// Choose two adjacent cube corners P and Q.
   273  		face := randomUniformInt(6)
   274  		i := randomUniformInt(4)
   275  		j := (i + 1) & 3
   276  		p := Point{faceUVToXYZ(face, biunit.Vertices()[i].X, biunit.Vertices()[i].Y)}
   277  		q := Point{faceUVToXYZ(face, biunit.Vertices()[j].X, biunit.Vertices()[j].Y)}
   278  
   279  		// Now choose two points that are nearly in the plane of PQ, preferring
   280  		// points that are near cube corners, face midpoints, or edge midpoints.
   281  		a := perturbedCornerOrMidpoint(p, q)
   282  		b := perturbedCornerOrMidpoint(p, q)
   283  		testClipToPaddedFace(t, a, b)
   284  	}
   285  }
   286  
   287  // getFraction returns the fraction t of the given point X on the line AB such that
   288  // x = (1-t)*a + t*b. Returns 0 if A = B.
   289  func getFraction(t *testing.T, x, a, b r2.Point) float64 {
   290  	// A bound for the error in edge clipping plus the error in the calculation
   291  	// (which is similar to EdgeIntersectsRect).
   292  	errorDist := (edgeClipErrorUVDist + intersectsRectErrorUVDist)
   293  	if a == b {
   294  		return 0.0
   295  	}
   296  	dir := b.Sub(a).Normalize()
   297  	if got := math.Abs(x.Sub(a).Dot(dir.Ortho())); got > errorDist {
   298  		t.Errorf("getFraction(%v, %v, %v) = %v, which exceeds errorDist %v", x, a, b, got, errorDist)
   299  	}
   300  	return x.Sub(a).Dot(dir)
   301  }
   302  
   303  // randomPointFromInterval returns a randomly selected point from the given interval
   304  // with one of three possible choices. All cases have reasonable probability for any
   305  // interval. The choices are: randomly choose a value inside the interval, choose a
   306  // value outside the interval, or select one of the two endpoints.
   307  func randomPointFromInterval(clip r1.Interval) float64 {
   308  	if oneIn(5) {
   309  		if oneIn(2) {
   310  			return clip.Lo
   311  		}
   312  		return clip.Hi
   313  	}
   314  
   315  	switch randomUniformInt(3) {
   316  	case 0:
   317  		return clip.Lo - randomFloat64()
   318  	case 1:
   319  		return clip.Hi + randomFloat64()
   320  	default:
   321  		return clip.Lo + randomFloat64()*clip.Length()
   322  	}
   323  }
   324  
   325  // Given a rectangle "clip", choose a point that may lie in the rectangle interior, along an extended edge, exactly at a vertex, or in one of the eight regions exterior to "clip" that are separated by its extended edges.  Also sometimes return points that are exactly on one of the extended diagonals of "clip". All cases are reasonably likely to occur for any given rectangle "clip".
   326  func chooseRectEndpoint(clip r2.Rect) r2.Point {
   327  	if oneIn(10) {
   328  		// Return a point on one of the two extended diagonals.
   329  		diag := randomUniformInt(2)
   330  		t := randomUniformFloat64(-1, 2)
   331  		return clip.Vertices()[diag].Mul(1 - t).Add(clip.Vertices()[diag+2].Mul(t))
   332  	}
   333  	return r2.Point{randomPointFromInterval(clip.X), randomPointFromInterval(clip.Y)}
   334  }
   335  
   336  // Choose a random point in the rectangle defined by points A and B, sometimes
   337  // returning a point on the edge AB or the points A and B themselves.
   338  func choosePointInRect(a, b r2.Point) r2.Point {
   339  	if oneIn(5) {
   340  		if oneIn(2) {
   341  			return a
   342  		}
   343  		return b
   344  	}
   345  
   346  	if oneIn(3) {
   347  		return a.Add(b.Sub(a).Mul(randomFloat64()))
   348  	}
   349  	return r2.Point{randomUniformFloat64(a.X, b.X), randomUniformFloat64(a.Y, b.Y)}
   350  }
   351  
   352  // Given a point P representing a possibly clipped endpoint A of an edge AB,
   353  // verify that clip contains P, and that if clipping occurred (i.e., P != A)
   354  // then P is on the boundary of clip.
   355  func checkPointOnBoundary(t *testing.T, p, a r2.Point, clip r2.Rect) {
   356  	if got := clip.ContainsPoint(p); !got {
   357  		t.Errorf("%v.ContainsPoint(%v) = %v, want true", clip, p, got)
   358  	}
   359  	if p != a {
   360  		p1 := r2.Point{math.Nextafter(p.X, a.X), math.Nextafter(p.Y, a.Y)}
   361  		if got := clip.ContainsPoint(p1); got {
   362  			t.Errorf("%v.ContainsPoint(%v) = %v, want false", clip, p1, got)
   363  		}
   364  	}
   365  }
   366  
   367  func TestEdgeClippingClipEdge(t *testing.T) {
   368  	// A bound for the error in edge clipping plus the error in the
   369  	// EdgeIntersectsRect calculation below.
   370  	errorDist := (edgeClipErrorUVDist + intersectsRectErrorUVDist)
   371  	testRects := []r2.Rect{
   372  		// Test clipping against random rectangles.
   373  		r2.RectFromPoints(
   374  			r2.Point{randomUniformFloat64(-1, 1), randomUniformFloat64(-1, 1)},
   375  			r2.Point{randomUniformFloat64(-1, 1), randomUniformFloat64(-1, 1)}),
   376  		r2.RectFromPoints(
   377  			r2.Point{randomUniformFloat64(-1, 1), randomUniformFloat64(-1, 1)},
   378  			r2.Point{randomUniformFloat64(-1, 1), randomUniformFloat64(-1, 1)}),
   379  		r2.RectFromPoints(
   380  			r2.Point{randomUniformFloat64(-1, 1), randomUniformFloat64(-1, 1)},
   381  			r2.Point{randomUniformFloat64(-1, 1), randomUniformFloat64(-1, 1)}),
   382  		r2.RectFromPoints(
   383  			r2.Point{randomUniformFloat64(-1, 1), randomUniformFloat64(-1, 1)},
   384  			r2.Point{randomUniformFloat64(-1, 1), randomUniformFloat64(-1, 1)}),
   385  		r2.RectFromPoints(
   386  			r2.Point{randomUniformFloat64(-1, 1), randomUniformFloat64(-1, 1)},
   387  			r2.Point{randomUniformFloat64(-1, 1), randomUniformFloat64(-1, 1)}),
   388  
   389  		// Also clip against one-dimensional, singleton, and empty rectangles.
   390  		{r1.Interval{-0.7, -0.7}, r1.Interval{0.3, 0.35}},
   391  		{r1.Interval{0.2, 0.5}, r1.Interval{0.3, 0.3}},
   392  		{r1.Interval{-0.7, 0.3}, r1.Interval{0, 0}},
   393  		r2.RectFromPoints(r2.Point{0.3, 0.8}),
   394  		r2.EmptyRect(),
   395  	}
   396  
   397  	for _, r := range testRects {
   398  		for i := 0; i < 1000; i++ {
   399  			a := chooseRectEndpoint(r)
   400  			b := chooseRectEndpoint(r)
   401  
   402  			aClip, bClip, intersects := ClipEdge(a, b, r)
   403  			if !intersects {
   404  				if edgeIntersectsRect(a, b, r.ExpandedByMargin(-errorDist)) {
   405  					t.Errorf("edgeIntersectsRect(%v, %v, %v.ExpandedByMargin(%v) = true, want false", a, b, r, -errorDist)
   406  				}
   407  			} else {
   408  				if !edgeIntersectsRect(a, b, r.ExpandedByMargin(errorDist)) {
   409  					t.Errorf("edgeIntersectsRect(%v, %v, %v.ExpandedByMargin(%v) = false, want true", a, b, r, errorDist)
   410  				}
   411  
   412  				// Check that the clipped points lie on the edge AB, and
   413  				// that the points have the expected order along the segment AB.
   414  				if gotA, gotB := getFraction(t, aClip, a, b), getFraction(t, bClip, a, b); gotA > gotB {
   415  					t.Errorf("getFraction(%v,%v,%v) = %v, getFraction(%v, %v, %v) = %v; %v < %v = false, want true", aClip, a, b, gotA, bClip, a, b, gotB, gotA, gotB)
   416  				}
   417  
   418  				// Check that the clipped portion of AB is as large as possible.
   419  				checkPointOnBoundary(t, aClip, a, r)
   420  				checkPointOnBoundary(t, bClip, b, r)
   421  			}
   422  
   423  			// Choose an random initial bound to pass to clipEdgeBound.
   424  			initialClip := r2.RectFromPoints(choosePointInRect(a, b), choosePointInRect(a, b))
   425  			bound := clippedEdgeBound(a, b, initialClip)
   426  			if bound.IsEmpty() {
   427  				// Precondition of clipEdgeBound not met
   428  				continue
   429  			}
   430  			maxBound := bound.Intersection(r)
   431  			if bound, intersects := clipEdgeBound(a, b, r, bound); !intersects {
   432  				if edgeIntersectsRect(a, b, maxBound.ExpandedByMargin(-errorDist)) {
   433  					t.Errorf("edgeIntersectsRect(%v, %v, %v.ExpandedByMargin(%v) = true, want false", a, b, maxBound.ExpandedByMargin(-errorDist), -errorDist)
   434  				}
   435  			} else {
   436  				if !edgeIntersectsRect(a, b, maxBound.ExpandedByMargin(errorDist)) {
   437  					t.Errorf("edgeIntersectsRect(%v, %v, %v.ExpandedByMargin(%v) = false, want true", a, b, maxBound.ExpandedByMargin(errorDist), errorDist)
   438  				}
   439  				// check that the bound is as large as possible.
   440  				ai := 0
   441  				if a.X > b.X {
   442  					ai = 1
   443  				}
   444  				aj := 0
   445  				if a.Y > b.Y {
   446  					aj = 1
   447  				}
   448  				checkPointOnBoundary(t, bound.VertexIJ(ai, aj), a, maxBound)
   449  				checkPointOnBoundary(t, bound.VertexIJ(1-ai, 1-aj), b, maxBound)
   450  			}
   451  		}
   452  	}
   453  }
   454  

View as plain text