convex_hull_query_test.go

Documentation: github.com/golang/geo/s2

     1  // Copyright 2018 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  func TestConvexHullQueryNoPoints(t *testing.T) {
    25  	query := NewConvexHullQuery()
    26  	result := query.ConvexHull()
    27  	if !result.IsEmpty() {
    28  		t.Errorf("ConvexHullQuery with no geometry should return an empty hull")
    29  	}
    30  }
    31  
    32  func TestConvexHullQueryOnePoint(t *testing.T) {
    33  	query := NewConvexHullQuery()
    34  	p := PointFromCoords(0, 0, 1)
    35  	query.AddPoint(p)
    36  	result := query.ConvexHull()
    37  	if got, want := len(result.vertices), 3; got != want {
    38  		t.Errorf("len(query.ConvexHull()) = %d, want %d", got, want)
    39  	}
    40  	if !result.IsNormalized() {
    41  		t.Errorf("ConvexHull should be normalized but wasn't")
    42  	}
    43  
    44  	if !loopHasVertex(result, p) {
    45  		t.Errorf("ConvexHull doesn't have vertex %v, but should", p)
    46  	}
    47  
    48  	// Add some duplicate points and check that the result is the same.
    49  	query.AddPoint(p)
    50  	query.AddPoint(p)
    51  	result2 := query.ConvexHull()
    52  	if !result2.Equal(result) {
    53  		t.Errorf("adding duplicate points to the ConvexHull should not change the result.")
    54  	}
    55  }
    56  
    57  func TestConvexHullQueryTwoPoints(t *testing.T) {
    58  	query := NewConvexHullQuery()
    59  	p := PointFromCoords(0, 0, 1)
    60  	q := PointFromCoords(0, 1, 0)
    61  	query.AddPoint(p)
    62  	query.AddPoint(q)
    63  	result := query.ConvexHull()
    64  	if got, want := len(result.vertices), 3; got != want {
    65  		t.Errorf("len(query.ConvexHull()) = %d, want %d", got, want)
    66  	}
    67  	if !result.IsNormalized() {
    68  		t.Errorf("ConvexHull should be normalized but wasn't")
    69  	}
    70  
    71  	if !loopHasVertex(result, p) {
    72  		t.Errorf("ConvexHull doesn't have vertex %v, but should", p)
    73  	}
    74  	if !loopHasVertex(result, q) {
    75  		t.Errorf("ConvexHull doesn't have vertex %v, but should", q)
    76  	}
    77  	// Add some duplicate points and check that the result is the same.
    78  	query.AddPoint(q)
    79  	query.AddPoint(p)
    80  	query.AddPoint(p)
    81  	result2 := query.ConvexHull()
    82  	if !result2.Equal(result) {
    83  		t.Errorf("adding duplicate points to the ConvexHull should not change the result.")
    84  	}
    85  }
    86  
    87  func TestConvexHullAntipodalPoints(t *testing.T) {
    88  	query := NewConvexHullQuery()
    89  	query.AddPoint(PointFromCoords(0, 0, 1))
    90  	query.AddPoint(PointFromCoords(0, 0, -1))
    91  	result := query.ConvexHull()
    92  	if !result.IsFull() {
    93  		t.Errorf("antipodal points should return a Full Polygon, got: %v", result)
    94  	}
    95  }
    96  
    97  func loopHasVertex(l *Loop, p Point) bool {
    98  	for _, v := range l.vertices {
    99  		if v == p {
   100  			return true
   101  		}
   102  	}
   103  	return false
   104  }
   105  
   106  func TestConvexHullQueryEmptyLoop(t *testing.T) {
   107  	query := NewConvexHullQuery()
   108  	query.AddLoop(EmptyLoop())
   109  	result := query.ConvexHull()
   110  	if !result.IsEmpty() {
   111  		t.Errorf("ConvexHull of Empty Loop should be the Empty Loop")
   112  	}
   113  }
   114  
   115  func TestConvexHullQueryFullLoop(t *testing.T) {
   116  	query := NewConvexHullQuery()
   117  	query.AddLoop(FullLoop())
   118  	result := query.ConvexHull()
   119  	if !result.IsFull() {
   120  		t.Errorf("ConvexHull of Full Loop should be the Full Loop")
   121  	}
   122  }
   123  
   124  func TestConvexHullQueryEmptyPolygon(t *testing.T) {
   125  	query := NewConvexHullQuery()
   126  	query.AddPolygon(PolygonFromLoops([]*Loop{}))
   127  	result := query.ConvexHull()
   128  	if !result.IsEmpty() {
   129  		t.Errorf("ConvexHull of an empty Polygon should be the Empty Loop")
   130  	}
   131  }
   132  
   133  func TestConvexHullQueryNonConvexPoints(t *testing.T) {
   134  	// Generate a point set such that the only convex region containing them is
   135  	// the entire sphere. In other words, you can generate any point on the
   136  	// sphere by repeatedly linearly interpolating between the points. (The
   137  	// four points of a tetrahedron would also work, but this is easier.)
   138  	query := NewConvexHullQuery()
   139  	for face := 0; face < 6; face++ {
   140  		query.AddPoint(CellIDFromFace(face).Point())
   141  	}
   142  	result := query.ConvexHull()
   143  	if !result.IsFull() {
   144  		t.Errorf("ConvexHull of all faces should be the Full Loop, got %v", result)
   145  	}
   146  }
   147  
   148  func TestConvexHullQuerySimplePolyline(t *testing.T) {
   149  	// A polyline is handled identically to a point set, so there is no need
   150  	// for special testing other than code coverage.
   151  	polyline := makePolyline("0:1, 0:9, 1:6, 2:6, 3:10, 4:10, 5:5, 4:0, 3:0, 2:5, 1:5")
   152  	query := NewConvexHullQuery()
   153  	query.AddPolyline(polyline)
   154  	result := query.ConvexHull()
   155  	want := makeLoop("0:1, 0:9, 3:10, 4:10, 5:5, 4:0, 3:0")
   156  	if !result.BoundaryEqual(want) {
   157  		t.Errorf("ConvexHull from %v = %v, want %v", polyline, result, want)
   158  	}
   159  }
   160  
   161  func TestConvexHullQueryLoopsAroundNorthPole(t *testing.T) {
   162  	tests := []struct {
   163  		radius   s1.Angle
   164  		numVerts int
   165  	}{
   166  		// Test loops of various sizes around the north pole.
   167  		{radius: 1 * s1.Degree, numVerts: 3},
   168  		{radius: 89 * s1.Degree, numVerts: 3},
   169  		// The following two loops should yield the full loop.
   170  		{radius: 91 * s1.Degree, numVerts: 3},
   171  		{radius: 179 * s1.Degree, numVerts: 3},
   172  
   173  		{radius: 10 * s1.Degree, numVerts: 100},
   174  		{radius: 89 * s1.Degree, numVerts: 1000},
   175  	}
   176  
   177  	for _, test := range tests {
   178  		query := NewConvexHullQuery()
   179  		loop := RegularLoop(PointFromCoords(0, 0, 1), test.radius, test.numVerts)
   180  		query.AddLoop(loop)
   181  		result := query.ConvexHull()
   182  
   183  		if test.radius > s1.Angle(math.Pi/2) {
   184  			if !result.IsFull() {
   185  				t.Errorf("ConvexHull of a Loop with radius > 90 should be the Full Loop")
   186  			}
   187  		} else {
   188  			if !result.BoundaryEqual(loop) {
   189  				t.Errorf("ConvexHull of a north pole loop = %v, want %v", result, loop)
   190  			}
   191  		}
   192  	}
   193  }
   194  
   195  func TestConvexHullQueryPointsInsideHull(t *testing.T) {
   196  	// Repeatedly build the convex hull of a set of points, then add more points
   197  	// inside that loop and build the convex hull again. The result should
   198  	// always be the same.
   199  	const iters = 1000
   200  	for iter := 0; iter < iters; iter++ {
   201  		// Choose points from within a cap of random size, up to but not including
   202  		// an entire hemisphere.
   203  		c := randomCap(1e-15, 1.999*math.Pi)
   204  		numPoints1 := randomUniformInt(100) + 3
   205  
   206  		query := NewConvexHullQuery()
   207  		for i := 0; i < numPoints1; i++ {
   208  			query.AddPoint(samplePointFromCap(c))
   209  		}
   210  		hull := query.ConvexHull()
   211  
   212  		// When the convex hull is nearly a hemisphere, the algorithm sometimes
   213  		// returns a full cap instead. This is because it first computes a
   214  		// bounding rectangle for all the input points/edges and then converts it
   215  		// to a bounding cap, which sometimes yields a non-convex cap (radius
   216  		// larger than 90 degrees). This should not be a problem in practice
   217  		// (since most convex hulls are not hemispheres), but in order make this
   218  		// test pass reliably it means that we need to reject convex hulls whose
   219  		// bounding cap (when computed from a bounding rectangle) is not convex.
   220  		//
   221  		// TODO(roberts): This test can still fail (about 1 iteration in 500,000)
   222  		// because the Rect.CapBound implementation does not guarantee
   223  		// that A.Contains(B) implies A.CapBound().Contains(B.CapBound()).
   224  		if hull.CapBound().Height() >= 1 {
   225  			continue
   226  		}
   227  
   228  		// Otherwise, add more points inside the convex hull.
   229  		const numPoints2 = 1000
   230  		for i := 0; i < numPoints2; i++ {
   231  			p := samplePointFromCap(c)
   232  			if hull.ContainsPoint(p) {
   233  				query.AddPoint(p)
   234  			}
   235  		}
   236  		// Finally, build a new convex hull and check that it hasn't changed.
   237  		hull2 := query.ConvexHull()
   238  		if !hull2.BoundaryEqual(hull) {
   239  			t.Errorf("%v.BoundaryEqual(%v) = false, but should be true", hull2, hull)
   240  		}
   241  	}
   242  }
   243
View as plain text