centroids_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/r3"
    22  )
    23  
    24  func TestCentroidsPlanarCentroid(t *testing.T) {
    25  	tests := []struct {
    26  		name             string
    27  		p0, p1, p2, want Point
    28  	}{
    29  		{
    30  			name: "xyz axis",
    31  			p0:   Point{r3.Vector{0, 0, 1}},
    32  			p1:   Point{r3.Vector{0, 1, 0}},
    33  			p2:   Point{r3.Vector{1, 0, 0}},
    34  			want: Point{r3.Vector{1. / 3, 1. / 3, 1. / 3}},
    35  		},
    36  		{
    37  			name: "Same point",
    38  			p0:   Point{r3.Vector{1, 0, 0}},
    39  			p1:   Point{r3.Vector{1, 0, 0}},
    40  			p2:   Point{r3.Vector{1, 0, 0}},
    41  			want: Point{r3.Vector{1, 0, 0}},
    42  		},
    43  	}
    44  
    45  	for _, test := range tests {
    46  		got := PlanarCentroid(test.p0, test.p1, test.p2)
    47  		if !got.ApproxEqual(test.want) {
    48  			t.Errorf("%s: PlanarCentroid(%v, %v, %v) = %v, want %v", test.name, test.p0, test.p1, test.p2, got, test.want)
    49  		}
    50  	}
    51  }
    52  
    53  func TestCentroidsTrueCentroid(t *testing.T) {
    54  	// Test TrueCentroid with very small triangles. This test assumes that
    55  	// the triangle is small enough so that it is nearly planar.
    56  	for i := 0; i < 100; i++ {
    57  		f := randomFrame()
    58  		p := f.col(0)
    59  		x := f.col(1)
    60  		y := f.col(2)
    61  		d := 1e-4 * math.Pow(1e-4, randomFloat64())
    62  
    63  		// Make a triangle with two equal sides.
    64  		p0 := Point{p.Sub(x.Mul(d)).Normalize()}
    65  		p1 := Point{p.Add(x.Mul(d)).Normalize()}
    66  		p2 := Point{p.Add(y.Mul(d * 3)).Normalize()}
    67  		want := Point{p.Add(y.Mul(d)).Normalize()}
    68  
    69  		// The centroid of a planar triangle is at the intersection of its
    70  		// medians, which is two-thirds of the way along each median.
    71  		got := TrueCentroid(p0, p1, p2).Normalize()
    72  		if got.Distance(want.Vector) >= 2e-8 {
    73  			t.Errorf("TrueCentroid(%v, %v, %v).Normalize() = %v, want %v", p0, p1, p2, got, want)
    74  		}
    75  
    76  		// Make a triangle with a right angle.
    77  		p0 = p
    78  		p1 = Point{p.Add(x.Mul(d * 3)).Normalize()}
    79  		p2 = Point{p.Add(y.Mul(d * 6)).Normalize()}
    80  		want = Point{p.Add(x.Add(y.Mul(2)).Mul(d)).Normalize()}
    81  
    82  		got = TrueCentroid(p0, p1, p2).Normalize()
    83  		if got.Distance(want.Vector) >= 2e-8 {
    84  			t.Errorf("TrueCentroid(%v, %v, %v).Normalize() = %v, want %v", p0, p1, p2, got, want)
    85  		}
    86  	}
    87  }
    88  
    89  func TestCentroidsEdgeTrueCentroidSemiCircles(t *testing.T) {
    90  	// Test the centroid of polyline ABC that follows the equator and consists
    91  	// of two 90 degree edges (i.e., C = -A).  The centroid (multiplied by
    92  	// length) should point toward B and have a norm of 2.0.  (The centroid
    93  	// itself has a norm of 2/Pi, and the total edge length is Pi.)
    94  	a := PointFromCoords(0, -1, 0)
    95  	b := PointFromCoords(1, 0, 0)
    96  	c := PointFromCoords(0, 1, 0)
    97  	centroid := Point{EdgeTrueCentroid(a, b).Add(EdgeTrueCentroid(b, c).Vector)}
    98  
    99  	if !b.ApproxEqual(Point{centroid.Normalize()}) {
   100  		t.Errorf("EdgeTrueCentroid(%v, %v) + EdgeTrueCentroid(%v, %v) = %v, want %v", a, b, b, c, centroid, b)
   101  	}
   102  	if got, want := centroid.Norm(), 2.0; !float64Eq(got, want) {
   103  		t.Errorf("%v.Norm() = %v, want %v", centroid, got, want)
   104  	}
   105  }
   106  
   107  func TestCentroidsEdgeTrueCentroidGreatCircles(t *testing.T) {
   108  	// Construct random great circles and divide them randomly into segments.
   109  	// Then make sure that the centroid is approximately at the center of the
   110  	// sphere.  Note that because of the way the centroid is computed, it does
   111  	// not matter how we split the great circle into segments.
   112  	//
   113  	// Note that this is a direct test of the properties that the centroid
   114  	// should have, rather than a test that it matches a particular formula.
   115  	for iter := 0; iter < 100; iter++ {
   116  		f := randomFrameAtPoint(randomPoint())
   117  		x := f.col(0)
   118  		y := f.col(1)
   119  
   120  		var centroid Point
   121  
   122  		v0 := x
   123  		for theta := 0.0; theta < 2*math.Pi; theta += math.Pow(randomFloat64(), 10) {
   124  			v1 := Point{x.Mul(math.Cos(theta)).Add(y.Mul(math.Sin(theta)))}
   125  			centroid = Point{centroid.Add(EdgeTrueCentroid(v0, v1).Vector)}
   126  			v0 = v1
   127  		}
   128  		// Close the circle.
   129  		centroid = Point{centroid.Add(EdgeTrueCentroid(v0, x).Vector)}
   130  		if got, want := centroid.Norm(), 2e-14; got > want {
   131  			t.Errorf("%v.Norm() = %v, want <= %v", centroid, got, want)
   132  		}
   133  	}
   134  }
   135
View as plain text