edge_crossings_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  	"math"
    19  	"testing"
    20  
    21  	"github.com/golang/geo/s1"
    22  )
    23  
    24  // The various Crossing methods are tested via s2edge_crosser_test
    25  
    26  // testIntersectionExact is a helper for the tests to return a positively
    27  // oriented intersection Point of the two line segments (a0,a1) and (b0,b1).
    28  func testIntersectionExact(a0, a1, b0, b1 Point) Point {
    29  	x := intersectionExact(a0, a1, b0, b1)
    30  	if x.Dot((a0.Add(a1.Vector)).Add(b0.Add(b1.Vector))) < 0 {
    31  		x = Point{x.Mul(-1)}
    32  	}
    33  	return x
    34  }
    35  
    36  var distanceAbsError = s1.Angle(3 * dblEpsilon)
    37  
    38  func TestEdgeutilIntersectionError(t *testing.T) {
    39  	// We repeatedly construct two edges that cross near a random point "p", and
    40  	// measure the distance from the actual intersection point "x" to the
    41  	// exact intersection point and also to the edges.
    42  
    43  	var maxPointDist, maxEdgeDist s1.Angle
    44  	for iter := 0; iter < 5000; iter++ {
    45  		// We construct two edges AB and CD that intersect near "p".  The angle
    46  		// between AB and CD (expressed as a slope) is chosen randomly between
    47  		// 1e-15 and 1e15 such that its logarithm is uniformly distributed.
    48  		// Similarly, two edge lengths approximately between 1e-15 and 1 are
    49  		// chosen.  The edge endpoints are chosen such that they are often very
    50  		// close to the other edge (i.e., barely crossing).  Taken together this
    51  		// ensures that we test both long and very short edges that intersect at
    52  		// both large and very small angles.
    53  		//
    54  		// Sometimes the edges we generate will not actually cross, in which case
    55  		// we simply try again.
    56  		f := randomFrame()
    57  		p := f.col(0)
    58  		d1 := f.col(1)
    59  		d2 := f.col(2)
    60  
    61  		slope := 1e-15 * math.Pow(1e30, randomFloat64())
    62  		d2 = Point{d1.Add(d2.Mul(slope)).Normalize()}
    63  		var a, b, c, d Point
    64  
    65  		// Find a pair of segments that cross.
    66  		for {
    67  			abLen := math.Pow(1e-15, randomFloat64())
    68  			cdLen := math.Pow(1e-15, randomFloat64())
    69  			aFraction := math.Pow(1e-5, randomFloat64())
    70  			if oneIn(2) {
    71  				aFraction = 1 - aFraction
    72  			}
    73  			cFraction := math.Pow(1e-5, randomFloat64())
    74  			if oneIn(2) {
    75  				cFraction = 1 - cFraction
    76  			}
    77  			a = Point{p.Sub(d1.Mul(aFraction * abLen)).Normalize()}
    78  			b = Point{p.Add(d1.Mul((1 - aFraction) * abLen)).Normalize()}
    79  			c = Point{p.Sub(d2.Mul(cFraction * cdLen)).Normalize()}
    80  			d = Point{p.Add(d2.Mul((1 - cFraction) * cdLen)).Normalize()}
    81  			if NewEdgeCrosser(a, b).CrossingSign(c, d) == Cross {
    82  				break
    83  			}
    84  		}
    85  
    86  		// Each constructed edge should be at most 1.5 * dblEpsilon away from the
    87  		// original point P.
    88  		if got, want := DistanceFromSegment(p, a, b), s1.Angle(1.5*dblEpsilon)+distanceAbsError; got > want {
    89  			t.Errorf("DistanceFromSegment(%v, %v, %v) = %v, want %v", p, a, b, got, want)
    90  		}
    91  		if got, want := DistanceFromSegment(p, c, d), s1.Angle(1.5*dblEpsilon)+distanceAbsError; got > want {
    92  			t.Errorf("DistanceFromSegment(%v, %v, %v) = %v, want %v", p, c, d, got, want)
    93  		}
    94  
    95  		// Verify that the expected intersection point is close to both edges and
    96  		// also close to the original point P. (It might not be very close to P
    97  		// if the angle between the edges is very small.)
    98  		expected := testIntersectionExact(a, b, c, d)
    99  		if got, want := DistanceFromSegment(expected, a, b), s1.Angle(3*dblEpsilon)+distanceAbsError; got > want {
   100  			t.Errorf("DistanceFromSegment(%v, %v, %v) = %v, want %v", expected, a, b, got, want)
   101  		}
   102  		if got, want := DistanceFromSegment(expected, c, d), s1.Angle(3*dblEpsilon)+distanceAbsError; got > want {
   103  			t.Errorf("DistanceFromSegment(%v, %v, %v) = %v, want %v", expected, c, d, got, want)
   104  		}
   105  		if got, want := expected.Distance(p), s1.Angle(3*dblEpsilon/slope)+intersectionError; got > want {
   106  			t.Errorf("%v.Distance(%v) = %v, want %v", expected, p, got, want)
   107  		}
   108  
   109  		// Now we actually test the Intersection() method.
   110  		actual := Intersection(a, b, c, d)
   111  		distAB := DistanceFromSegment(actual, a, b)
   112  		distCD := DistanceFromSegment(actual, c, d)
   113  		pointDist := expected.Distance(actual)
   114  		if got, want := distAB, intersectionError+distanceAbsError; got > want {
   115  			t.Errorf("DistanceFromSegment(%v, %v, %v) = %v want <= %v", actual, a, b, got, want)
   116  		}
   117  		if got, want := distCD, intersectionError+distanceAbsError; got > want {
   118  			t.Errorf("DistanceFromSegment(%v, %v, %v) = %v want <= %v", actual, c, d, got, want)
   119  		}
   120  		if got, want := pointDist, intersectionError; got > want {
   121  			t.Errorf("%v.Distance(%v) = %v want <= %v", expected, actual, got, want)
   122  		}
   123  		maxEdgeDist = maxAngle(maxEdgeDist, maxAngle(distAB, distCD))
   124  		maxPointDist = maxAngle(maxPointDist, pointDist)
   125  	}
   126  }
   127  
   128  func TestAngleContainsVertex(t *testing.T) {
   129  	a := PointFromCoords(1, 0, 0)
   130  	b := PointFromCoords(0, 1, 0)
   131  	refB := b.referenceDir()
   132  
   133  	// Degenerate angle ABA.
   134  	if AngleContainsVertex(a, b, a) {
   135  		t.Errorf("AngleContainsVertex(%v, %v, %v = true, want false", a, b, a)
   136  	}
   137  
   138  	// An angle where A == referenceDir(B).
   139  	if !AngleContainsVertex(refB, b, a) {
   140  		t.Errorf("AngleContainsVertex(%v, %v, %v = false, want true", refB, b, a)
   141  	}
   142  
   143  	// An angle where C == referenceDir(B).
   144  	if AngleContainsVertex(a, b, refB) {
   145  		t.Errorf("AngleContainsVertex(%v, %v, %v = true, want false", a, b, refB)
   146  	}
   147  
   148  	// Verify that when a set of polygons tile the region around the vertex,
   149  	// exactly one of those polygons contains the vertex.
   150  	loop := RegularLoop(b, s1.Angle(10)*s1.Degree, 10)
   151  	count := 0
   152  	for i, v := range loop.Vertices() {
   153  		if AngleContainsVertex(loop.Vertex(i+1), b, v) {
   154  			count++
   155  		}
   156  	}
   157  	if count != 1 {
   158  		t.Errorf("with a set of polygons tiled around a vertex, only one should contain the vertex, got %d", count)
   159  	}
   160  }
   161  
   162  // TODO(roberts): Differences from C++:
   163  // func TestEdgeCrossingsRobustCrossProdCoverage(t* testing.T)
   164  // func TestEdgeCrossingsSymbolicCrossProdConsistentWithSign(t* testing.T)
   165  // func TestEdgeCrossingsRobustCrossProdMagnitude(t* testing.T)
   166  // func TestEdgeCrossingsRobustCrossProdError(t* testing.T)
   167  // func TestEdgeCrossingsIntersectionError(t* testing.T)
   168  // func TestEdgeCrossingsGrazingIntersections(t* testing.T)
   169  // func TestEdgeCrossingsExactIntersectionUnderflow(t* testing.T)
   170  // func TestEdgeCrossingsExactIntersectionSign(t* testing.T)
   171  // func TestEdgeCrossingsIntersectionInvariants(t* testing.T)
   172
View as plain text