3 files changed, 401 insertions, 0 deletions
diff --git a/vendor/github.com/golang/geo/r3/doc.go b/vendor/github.com/golang/geo/r3/doc.go
new file mode 100644
index 000000000..1eb4710c8
--- /dev/null
+++ b/vendor/github.com/golang/geo/r3/doc.go
@@ -0,0 +1,20 @@
+// Copyright 2014 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+/*
+Package r3 implements types and functions for working with geometry in ℝ³.
+
+See ../s2 for a more detailed overview.
+*/
+package r3
diff --git a/vendor/github.com/golang/geo/r3/precisevector.go b/vendor/github.com/golang/geo/r3/precisevector.go
new file mode 100644
index 000000000..b13393dbc
--- /dev/null
+++ b/vendor/github.com/golang/geo/r3/precisevector.go
@@ -0,0 +1,198 @@
+// Copyright 2016 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package r3
+
+import (
+	"fmt"
+	"math/big"
+)
+
+const (
+	// prec is the number of bits of precision to use for the Float values.
+	// To keep things simple, we use the maximum allowable precision on big
+	// values. This allows us to handle all values we expect in the s2 library.
+	prec = big.MaxPrec
+)
+
+// define some commonly referenced values.
+var (
+	precise0 = precInt(0)
+	precise1 = precInt(1)
+)
+
+// precStr wraps the conversion from a string into a big.Float. For results that
+// actually can be represented exactly, this should only be used on values that
+// are integer multiples of integer powers of 2.
+func precStr(s string) *big.Float {
+	// Explicitly ignoring the bool return for this usage.
+	f, _ := new(big.Float).SetPrec(prec).SetString(s)
+	return f
+}
+
+func precInt(i int64) *big.Float {
+	return new(big.Float).SetPrec(prec).SetInt64(i)
+}
+
+func precFloat(f float64) *big.Float {
+	return new(big.Float).SetPrec(prec).SetFloat64(f)
+}
+
+func precAdd(a, b *big.Float) *big.Float {
+	return new(big.Float).SetPrec(prec).Add(a, b)
+}
+
+func precSub(a, b *big.Float) *big.Float {
+	return new(big.Float).SetPrec(prec).Sub(a, b)
+}
+
+func precMul(a, b *big.Float) *big.Float {
+	return new(big.Float).SetPrec(prec).Mul(a, b)
+}
+
+// PreciseVector represents a point in ℝ³ using high-precision values.
+// Note that this is NOT a complete implementation because there are some
+// operations that Vector supports that are not feasible with arbitrary precision
+// math. (e.g., methods that need division like Normalize, or methods needing a
+// square root operation such as Norm)
+type PreciseVector struct {
+	X, Y, Z *big.Float
+}
+
+// PreciseVectorFromVector creates a high precision vector from the given Vector.
+func PreciseVectorFromVector(v Vector) PreciseVector {
+	return NewPreciseVector(v.X, v.Y, v.Z)
+}
+
+// NewPreciseVector creates a high precision vector from the given floating point values.
+func NewPreciseVector(x, y, z float64) PreciseVector {
+	return PreciseVector{
+		X: precFloat(x),
+		Y: precFloat(y),
+		Z: precFloat(z),
+	}
+}
+
+// Vector returns this precise vector converted to a Vector.
+func (v PreciseVector) Vector() Vector {
+	// The accuracy flag is ignored on these conversions back to float64.
+	x, _ := v.X.Float64()
+	y, _ := v.Y.Float64()
+	z, _ := v.Z.Float64()
+	return Vector{x, y, z}.Normalize()
+}
+
+// Equal reports whether v and ov are equal.
+func (v PreciseVector) Equal(ov PreciseVector) bool {
+	return v.X.Cmp(ov.X) == 0 && v.Y.Cmp(ov.Y) == 0 && v.Z.Cmp(ov.Z) == 0
+}
+
+func (v PreciseVector) String() string {
+	return fmt.Sprintf("(%10g, %10g, %10g)", v.X, v.Y, v.Z)
+}
+
+// Norm2 returns the square of the norm.
+func (v PreciseVector) Norm2() *big.Float { return v.Dot(v) }
+
+// IsUnit reports whether this vector is of unit length.
+func (v PreciseVector) IsUnit() bool {
+	return v.Norm2().Cmp(precise1) == 0
+}
+
+// Abs returns the vector with nonnegative components.
+func (v PreciseVector) Abs() PreciseVector {
+	return PreciseVector{
+		X: new(big.Float).Abs(v.X),
+		Y: new(big.Float).Abs(v.Y),
+		Z: new(big.Float).Abs(v.Z),
+	}
+}
+
+// Add returns the standard vector sum of v and ov.
+func (v PreciseVector) Add(ov PreciseVector) PreciseVector {
+	return PreciseVector{
+		X: precAdd(v.X, ov.X),
+		Y: precAdd(v.Y, ov.Y),
+		Z: precAdd(v.Z, ov.Z),
+	}
+}
+
+// Sub returns the standard vector difference of v and ov.
+func (v PreciseVector) Sub(ov PreciseVector) PreciseVector {
+	return PreciseVector{
+		X: precSub(v.X, ov.X),
+		Y: precSub(v.Y, ov.Y),
+		Z: precSub(v.Z, ov.Z),
+	}
+}
+
+// Mul returns the standard scalar product of v and f.
+func (v PreciseVector) Mul(f *big.Float) PreciseVector {
+	return PreciseVector{
+		X: precMul(v.X, f),
+		Y: precMul(v.Y, f),
+		Z: precMul(v.Z, f),
+	}
+}
+
+// MulByFloat64 returns the standard scalar product of v and f.
+func (v PreciseVector) MulByFloat64(f float64) PreciseVector {
+	return v.Mul(precFloat(f))
+}
+
+// Dot returns the standard dot product of v and ov.
+func (v PreciseVector) Dot(ov PreciseVector) *big.Float {
+	return precAdd(precMul(v.X, ov.X), precAdd(precMul(v.Y, ov.Y), precMul(v.Z, ov.Z)))
+}
+
+// Cross returns the standard cross product of v and ov.
+func (v PreciseVector) Cross(ov PreciseVector) PreciseVector {
+	return PreciseVector{
+		X: precSub(precMul(v.Y, ov.Z), precMul(v.Z, ov.Y)),
+		Y: precSub(precMul(v.Z, ov.X), precMul(v.X, ov.Z)),
+		Z: precSub(precMul(v.X, ov.Y), precMul(v.Y, ov.X)),
+	}
+}
+
+// LargestComponent returns the axis that represents the largest component in this vector.
+func (v PreciseVector) LargestComponent() Axis {
+	t := v.Abs()
+
+	if t.X.Cmp(t.Y) > 0 {
+		if t.X.Cmp(t.Z) > 0 {
+			return XAxis
+		}
+		return ZAxis
+	}
+	if t.Y.Cmp(t.Z) > 0 {
+		return YAxis
+	}
+	return ZAxis
+}
+
+// SmallestComponent returns the axis that represents the smallest component in this vector.
+func (v PreciseVector) SmallestComponent() Axis {
+	t := v.Abs()
+
+	if t.X.Cmp(t.Y) < 0 {
+		if t.X.Cmp(t.Z) < 0 {
+			return XAxis
+		}
+		return ZAxis
+	}
+	if t.Y.Cmp(t.Z) < 0 {
+		return YAxis
+	}
+	return ZAxis
+}
diff --git a/vendor/github.com/golang/geo/r3/vector.go b/vendor/github.com/golang/geo/r3/vector.go
new file mode 100644
index 000000000..ccda622f4
--- /dev/null
+++ b/vendor/github.com/golang/geo/r3/vector.go
@@ -0,0 +1,183 @@
+// Copyright 2014 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package r3
+
+import (
+	"fmt"
+	"math"
+
+	"github.com/golang/geo/s1"
+)
+
+// Vector represents a point in ℝ³.
+type Vector struct {
+	X, Y, Z float64
+}
+
+// ApproxEqual reports whether v and ov are equal within a small epsilon.
+func (v Vector) ApproxEqual(ov Vector) bool {
+	const epsilon = 1e-16
+	return math.Abs(v.X-ov.X) < epsilon && math.Abs(v.Y-ov.Y) < epsilon && math.Abs(v.Z-ov.Z) < epsilon
+}
+
+func (v Vector) String() string { return fmt.Sprintf("(%0.24f, %0.24f, %0.24f)", v.X, v.Y, v.Z) }
+
+// Norm returns the vector's norm.
+func (v Vector) Norm() float64 { return math.Sqrt(v.Dot(v)) }
+
+// Norm2 returns the square of the norm.
+func (v Vector) Norm2() float64 { return v.Dot(v) }
+
+// Normalize returns a unit vector in the same direction as v.
+func (v Vector) Normalize() Vector {
+	n2 := v.Norm2()
+	if n2 == 0 {
+		return Vector{0, 0, 0}
+	}
+	return v.Mul(1 / math.Sqrt(n2))
+}
+
+// IsUnit returns whether this vector is of approximately unit length.
+func (v Vector) IsUnit() bool {
+	const epsilon = 5e-14
+	return math.Abs(v.Norm2()-1) <= epsilon
+}
+
+// Abs returns the vector with nonnegative components.
+func (v Vector) Abs() Vector { return Vector{math.Abs(v.X), math.Abs(v.Y), math.Abs(v.Z)} }
+
+// Add returns the standard vector sum of v and ov.
+func (v Vector) Add(ov Vector) Vector { return Vector{v.X + ov.X, v.Y + ov.Y, v.Z + ov.Z} }
+
+// Sub returns the standard vector difference of v and ov.
+func (v Vector) Sub(ov Vector) Vector { return Vector{v.X - ov.X, v.Y - ov.Y, v.Z - ov.Z} }
+
+// Mul returns the standard scalar product of v and m.
+func (v Vector) Mul(m float64) Vector { return Vector{m * v.X, m * v.Y, m * v.Z} }
+
+// Dot returns the standard dot product of v and ov.
+func (v Vector) Dot(ov Vector) float64 { return v.X*ov.X + v.Y*ov.Y + v.Z*ov.Z }
+
+// Cross returns the standard cross product of v and ov.
+func (v Vector) Cross(ov Vector) Vector {
+	return Vector{
+		v.Y*ov.Z - v.Z*ov.Y,
+		v.Z*ov.X - v.X*ov.Z,
+		v.X*ov.Y - v.Y*ov.X,
+	}
+}
+
+// Distance returns the Euclidean distance between v and ov.
+func (v Vector) Distance(ov Vector) float64 { return v.Sub(ov).Norm() }
+
+// Angle returns the angle between v and ov.
+func (v Vector) Angle(ov Vector) s1.Angle {
+	return s1.Angle(math.Atan2(v.Cross(ov).Norm(), v.Dot(ov))) * s1.Radian
+}
+
+// Axis enumerates the 3 axes of ℝ³.
+type Axis int
+
+// The three axes of ℝ³.
+const (
+	XAxis Axis = iota
+	YAxis
+	ZAxis
+)
+
+// Ortho returns a unit vector that is orthogonal to v.
+// Ortho(-v) = -Ortho(v) for all v.
+func (v Vector) Ortho() Vector {
+	ov := Vector{0.012, 0.0053, 0.00457}
+	switch v.LargestComponent() {
+	case XAxis:
+		ov.Z = 1
+	case YAxis:
+		ov.X = 1
+	default:
+		ov.Y = 1
+	}
+	return v.Cross(ov).Normalize()
+}
+
+// LargestComponent returns the axis that represents the largest component in this vector.
+func (v Vector) LargestComponent() Axis {
+	t := v.Abs()
+
+	if t.X > t.Y {
+		if t.X > t.Z {
+			return XAxis
+		}
+		return ZAxis
+	}
+	if t.Y > t.Z {
+		return YAxis
+	}
+	return ZAxis
+}
+
+// SmallestComponent returns the axis that represents the smallest component in this vector.
+func (v Vector) SmallestComponent() Axis {
+	t := v.Abs()
+
+	if t.X < t.Y {
+		if t.X < t.Z {
+			return XAxis
+		}
+		return ZAxis
+	}
+	if t.Y < t.Z {
+		return YAxis
+	}
+	return ZAxis
+}
+
+// Cmp compares v and ov lexicographically and returns:
+//
+//   -1 if v <  ov
+//    0 if v == ov
+//   +1 if v >  ov
+//
+// This method is based on C++'s std::lexicographical_compare. Two entities
+// are compared element by element with the given operator. The first mismatch
+// defines which is less (or greater) than the other. If both have equivalent
+// values they are lexicographically equal.
+func (v Vector) Cmp(ov Vector) int {
+	if v.X < ov.X {
+		return -1
+	}
+	if v.X > ov.X {
+		return 1
+	}
+
+	// First elements were the same, try the next.
+	if v.Y < ov.Y {
+		return -1
+	}
+	if v.Y > ov.Y {
+		return 1
+	}
+
+	// Second elements were the same return the final compare.
+	if v.Z < ov.Z {
+		return -1
+	}
+	if v.Z > ov.Z {
+		return 1
+	}
+
+	// Both are equal
+	return 0
+}