diff options
Diffstat (limited to 'vendor/github.com/golang/geo/s2/point.go')
| -rw-r--r-- | vendor/github.com/golang/geo/s2/point.go | 258 |
1 files changed, 0 insertions, 258 deletions
diff --git a/vendor/github.com/golang/geo/s2/point.go b/vendor/github.com/golang/geo/s2/point.go deleted file mode 100644 index 89e7ae0ed..000000000 --- a/vendor/github.com/golang/geo/s2/point.go +++ /dev/null @@ -1,258 +0,0 @@ -// 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 s2 - -import ( - "fmt" - "io" - "math" - "sort" - - "github.com/golang/geo/r3" - "github.com/golang/geo/s1" -) - -// Point represents a point on the unit sphere as a normalized 3D vector. -// Fields should be treated as read-only. Use one of the factory methods for creation. -type Point struct { - r3.Vector -} - -// sortPoints sorts the slice of Points in place. -func sortPoints(e []Point) { - sort.Sort(points(e)) -} - -// points implements the Sort interface for slices of Point. -type points []Point - -func (p points) Len() int { return len(p) } -func (p points) Swap(i, j int) { p[i], p[j] = p[j], p[i] } -func (p points) Less(i, j int) bool { return p[i].Cmp(p[j].Vector) == -1 } - -// PointFromCoords creates a new normalized point from coordinates. -// -// This always returns a valid point. If the given coordinates can not be normalized -// the origin point will be returned. -// -// This behavior is different from the C++ construction of a S2Point from coordinates -// (i.e. S2Point(x, y, z)) in that in C++ they do not Normalize. -func PointFromCoords(x, y, z float64) Point { - if x == 0 && y == 0 && z == 0 { - return OriginPoint() - } - return Point{r3.Vector{x, y, z}.Normalize()} -} - -// OriginPoint returns a unique "origin" on the sphere for operations that need a fixed -// reference point. In particular, this is the "point at infinity" used for -// point-in-polygon testing (by counting the number of edge crossings). -// -// It should *not* be a point that is commonly used in edge tests in order -// to avoid triggering code to handle degenerate cases (this rules out the -// north and south poles). It should also not be on the boundary of any -// low-level S2Cell for the same reason. -func OriginPoint() Point { - return Point{r3.Vector{-0.0099994664350250197, 0.0025924542609324121, 0.99994664350250195}} -} - -// PointCross returns a Point that is orthogonal to both p and op. This is similar to -// p.Cross(op) (the true cross product) except that it does a better job of -// ensuring orthogonality when the Point is nearly parallel to op, it returns -// a non-zero result even when p == op or p == -op and the result is a Point. -// -// It satisfies the following properties (f == PointCross): -// -// (1) f(p, op) != 0 for all p, op -// (2) f(op,p) == -f(p,op) unless p == op or p == -op -// (3) f(-p,op) == -f(p,op) unless p == op or p == -op -// (4) f(p,-op) == -f(p,op) unless p == op or p == -op -func (p Point) PointCross(op Point) Point { - // NOTE(dnadasi): In the C++ API the equivalent method here was known as "RobustCrossProd", - // but PointCross more accurately describes how this method is used. - x := p.Add(op.Vector).Cross(op.Sub(p.Vector)) - - // Compare exactly to the 0 vector. - if x == (r3.Vector{}) { - // The only result that makes sense mathematically is to return zero, but - // we find it more convenient to return an arbitrary orthogonal vector. - return Point{p.Ortho()} - } - - return Point{x} -} - -// OrderedCCW returns true if the edges OA, OB, and OC are encountered in that -// order while sweeping CCW around the point O. -// -// You can think of this as testing whether A <= B <= C with respect to the -// CCW ordering around O that starts at A, or equivalently, whether B is -// contained in the range of angles (inclusive) that starts at A and extends -// CCW to C. Properties: -// -// (1) If OrderedCCW(a,b,c,o) && OrderedCCW(b,a,c,o), then a == b -// (2) If OrderedCCW(a,b,c,o) && OrderedCCW(a,c,b,o), then b == c -// (3) If OrderedCCW(a,b,c,o) && OrderedCCW(c,b,a,o), then a == b == c -// (4) If a == b or b == c, then OrderedCCW(a,b,c,o) is true -// (5) Otherwise if a == c, then OrderedCCW(a,b,c,o) is false -func OrderedCCW(a, b, c, o Point) bool { - sum := 0 - if RobustSign(b, o, a) != Clockwise { - sum++ - } - if RobustSign(c, o, b) != Clockwise { - sum++ - } - if RobustSign(a, o, c) == CounterClockwise { - sum++ - } - return sum >= 2 -} - -// Distance returns the angle between two points. -func (p Point) Distance(b Point) s1.Angle { - return p.Vector.Angle(b.Vector) -} - -// ApproxEqual reports whether the two points are similar enough to be equal. -func (p Point) ApproxEqual(other Point) bool { - return p.approxEqual(other, s1.Angle(epsilon)) -} - -// approxEqual reports whether the two points are within the given epsilon. -func (p Point) approxEqual(other Point, eps s1.Angle) bool { - return p.Vector.Angle(other.Vector) <= eps -} - -// ChordAngleBetweenPoints constructs a ChordAngle corresponding to the distance -// between the two given points. The points must be unit length. -func ChordAngleBetweenPoints(x, y Point) s1.ChordAngle { - return s1.ChordAngle(math.Min(4.0, x.Sub(y.Vector).Norm2())) -} - -// regularPoints generates a slice of points shaped as a regular polygon with -// the numVertices vertices, all located on a circle of the specified angular radius -// around the center. The radius is the actual distance from center to each vertex. -func regularPoints(center Point, radius s1.Angle, numVertices int) []Point { - return regularPointsForFrame(getFrame(center), radius, numVertices) -} - -// regularPointsForFrame generates a slice of points shaped as a regular polygon -// with numVertices vertices, all on a circle of the specified angular radius around -// the center. The radius is the actual distance from the center to each vertex. -func regularPointsForFrame(frame matrix3x3, radius s1.Angle, numVertices int) []Point { - // We construct the loop in the given frame coordinates, with the center at - // (0, 0, 1). For a loop of radius r, the loop vertices have the form - // (x, y, z) where x^2 + y^2 = sin(r) and z = cos(r). The distance on the - // sphere (arc length) from each vertex to the center is acos(cos(r)) = r. - z := math.Cos(radius.Radians()) - r := math.Sin(radius.Radians()) - radianStep := 2 * math.Pi / float64(numVertices) - var vertices []Point - - for i := 0; i < numVertices; i++ { - angle := float64(i) * radianStep - p := Point{r3.Vector{r * math.Cos(angle), r * math.Sin(angle), z}} - vertices = append(vertices, Point{fromFrame(frame, p).Normalize()}) - } - - return vertices -} - -// CapBound returns a bounding cap for this point. -func (p Point) CapBound() Cap { - return CapFromPoint(p) -} - -// RectBound returns a bounding latitude-longitude rectangle from this point. -func (p Point) RectBound() Rect { - return RectFromLatLng(LatLngFromPoint(p)) -} - -// ContainsCell returns false as Points do not contain any other S2 types. -func (p Point) ContainsCell(c Cell) bool { return false } - -// IntersectsCell reports whether this Point intersects the given cell. -func (p Point) IntersectsCell(c Cell) bool { - return c.ContainsPoint(p) -} - -// ContainsPoint reports if this Point contains the other Point. -// (This method is named to satisfy the Region interface.) -func (p Point) ContainsPoint(other Point) bool { - return p.Contains(other) -} - -// CellUnionBound computes a covering of the Point. -func (p Point) CellUnionBound() []CellID { - return p.CapBound().CellUnionBound() -} - -// Contains reports if this Point contains the other Point. -// (This method matches all other s2 types where the reflexive Contains -// method does not contain the type's name.) -func (p Point) Contains(other Point) bool { return p == other } - -// Encode encodes the Point. -func (p Point) Encode(w io.Writer) error { - e := &encoder{w: w} - p.encode(e) - return e.err -} - -func (p Point) encode(e *encoder) { - e.writeInt8(encodingVersion) - e.writeFloat64(p.X) - e.writeFloat64(p.Y) - e.writeFloat64(p.Z) -} - -// Decode decodes the Point. -func (p *Point) Decode(r io.Reader) error { - d := &decoder{r: asByteReader(r)} - p.decode(d) - return d.err -} - -func (p *Point) decode(d *decoder) { - version := d.readInt8() - if d.err != nil { - return - } - if version != encodingVersion { - d.err = fmt.Errorf("only version %d is supported", encodingVersion) - return - } - p.X = d.readFloat64() - p.Y = d.readFloat64() - p.Z = d.readFloat64() -} - -// Rotate the given point about the given axis by the given angle. p and -// axis must be unit length; angle has no restrictions (e.g., it can be -// positive, negative, greater than 360 degrees, etc). -func Rotate(p, axis Point, angle s1.Angle) Point { - // Let M be the plane through P that is perpendicular to axis, and let - // center be the point where M intersects axis. We construct a - // right-handed orthogonal frame (dx, dy, center) such that dx is the - // vector from center to P, and dy has the same length as dx. The - // result can then be expressed as (cos(angle)*dx + sin(angle)*dy + center). - center := axis.Mul(p.Dot(axis.Vector)) - dx := p.Sub(center) - dy := axis.Cross(p.Vector) - // Mathematically the result is unit length, but normalization is necessary - // to ensure that numerical errors don't accumulate. - return Point{dx.Mul(math.Cos(angle.Radians())).Add(dy.Mul(math.Sin(angle.Radians()))).Add(center).Normalize()} -} |