s1

package
v0.0.0-...-6adc566 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Apr 21, 2023 License: Apache-2.0 Imports: 2 Imported by: 184

Documentation

Overview

Package s1 implements types and functions for working with geometry in S¹ (circular geometry).

See ../s2 for a more detailed overview.

Index

Examples

Constants

View Source 
const (
	Radian Angle = 1
	Degree       = (math.Pi / 180) * Radian

	E5 = 1e-5 * Degree
	E6 = 1e-6 * Degree
	E7 = 1e-7 * Degree
)

Angle units.

View Source 
const (
	// NegativeChordAngle represents a chord angle smaller than the zero angle.
	// The only valid operations on a NegativeChordAngle are comparisons,
	// Angle conversions, and Successor/Predecessor.
	NegativeChordAngle = ChordAngle(-1)

	// RightChordAngle represents a chord angle of 90 degrees (a "right angle").
	RightChordAngle = ChordAngle(2)

	// StraightChordAngle represents a chord angle of 180 degrees (a "straight angle").
	// This is the maximum finite chord angle.
	StraightChordAngle = ChordAngle(4)
)

Variables

This section is empty.

Functions

This section is empty.

Types

type Angle 

type Angle float64

Angle represents a 1D angle. The internal representation is a double precision value in radians, so conversion to and from radians is exact. Conversions between E5, E6, E7, and Degrees are not always exact. For example, Degrees(3.1) is different from E6(3100000) or E7(31000000).

The following conversions between degrees and radians are exact: 

    Degree*180 == Radian*math.Pi
Degree*(180/n) == Radian*(math.Pi/n)     for n == 0..8

These identities hold when the arguments are scaled up or down by any power of 2. Some similar identities are also true, for example, 

Degree*60 == Radian*(math.Pi/3)

But be aware that this type of identity does not hold in general. For example, 

Degree*3 != Radian*(math.Pi/60)

Similarly, the conversion to radians means that (Angle(x)*Degree).Degrees() does not always equal x. For example, 

(Angle(45*n)*Degree).Degrees() == 45*n     for n == 0..8

but 

(60*Degree).Degrees() != 60

When testing for equality, you should allow for numerical errors (ApproxEqual) or convert to discrete E5/E6/E7 values first.

func InfAngle 

func InfAngle() Angle

InfAngle returns an angle larger than any finite angle.

func (Angle) Abs 

func (a Angle) Abs() Angle

Abs returns the absolute value of the angle.

func (Angle) ApproxEqual 

func (a Angle) ApproxEqual(other Angle) bool

ApproxEqual reports whether the two angles are the same up to a small tolerance.

func (Angle) Degrees 

func (a Angle) Degrees() float64

Degrees returns the angle in degrees.

func (Angle) E5 

func (a Angle) E5() int32

E5 returns the angle in hundred thousandths of degrees.

func (Angle) E6 

func (a Angle) E6() int32

E6 returns the angle in millionths of degrees.

func (Angle) E7 

func (a Angle) E7() int32

E7 returns the angle in ten millionths of degrees.

func (Angle) Normalized 

func (a Angle) Normalized() Angle

Normalized returns an equivalent angle in (-π, π].

func (Angle) Radians 

func (a Angle) Radians() float64

Radians returns the angle in radians.

func (Angle) String 

func (a Angle) String() string

type ChordAngle 

type ChordAngle float64

ChordAngle represents the angle subtended by a chord (i.e., the straight line segment connecting two points on the sphere). Its representation makes it very efficient for computing and comparing distances, but unlike Angle it is only capable of representing angles between 0 and π radians. Generally, ChordAngle should only be used in loops where many angles need to be calculated and compared. Otherwise it is simpler to use Angle.

ChordAngle loses some accuracy as the angle approaches π radians. There are several different ways to measure this error, including the representational error (i.e., how accurately ChordAngle can represent angles near π radians), the conversion error (i.e., how much precision is lost when an Angle is converted to an ChordAngle), and the measurement error (i.e., how accurate the ChordAngle(a, b) constructor is when the points A and B are separated by angles close to π radians). All of these errors differ by a small constant factor.

For the measurement error (which is the largest of these errors and also the most important in practice), let the angle between A and B be (π - x) radians, i.e. A and B are within "x" radians of being antipodal. The corresponding chord length is 

r = 2 * sin((π - x) / 2) = 2 * cos(x / 2)

For values of x not close to π the relative error in the squared chord length is at most 4.5 * dblEpsilon (see MaxPointError below). The relative error in "r" is thus at most 2.25 * dblEpsilon ~= 5e-16. To convert this error into an equivalent angle, we have 

|dr / dx| = sin(x / 2)

and therefore 

|dx| = dr / sin(x / 2)
     = 5e-16 * (2 * cos(x / 2)) / sin(x / 2)
     = 1e-15 / tan(x / 2)

The maximum error is attained when 

x  = |dx|
   = 1e-15 / tan(x / 2)
  ~= 1e-15 / (x / 2)
  ~= sqrt(2e-15)

In summary, the measurement error for an angle (π - x) is at most 

dx  = min(1e-15 / tan(x / 2), sqrt(2e-15))
  (~= min(2e-15 / x, sqrt(2e-15)) when x is small)

On the Earth's surface (assuming a radius of 6371km), this corresponds to the following worst-case measurement errors: 

Accuracy:             Unless antipodal to within:
---------             ---------------------------
6.4 nanometers        10,000 km (90 degrees)
1 micrometer          81.2 kilometers
1 millimeter          81.2 meters
1 centimeter          8.12 meters
28.5 centimeters      28.5 centimeters

The representational and conversion errors referred to earlier are somewhat smaller than this. For example, maximum distance between adjacent representable ChordAngle values is only 13.5 cm rather than 28.5 cm. To see this, observe that the closest representable value to r^2 = 4 is r^2 = 4 * (1 - dblEpsilon / 2). Thus r = 2 * (1 - dblEpsilon / 4) and the angle between these two representable values is 

x  = 2 * acos(r / 2)
   = 2 * acos(1 - dblEpsilon / 4)
  ~= 2 * asin(sqrt(dblEpsilon / 2)
  ~= sqrt(2 * dblEpsilon)
  ~= 2.1e-8

which is 13.5 cm on the Earth's surface.

The worst case rounding error occurs when the value halfway between these two representable values is rounded up to 4. This halfway value is r^2 = (4 * (1 - dblEpsilon / 4)), thus r = 2 * (1 - dblEpsilon / 8) and the worst case rounding error is 

x  = 2 * acos(r / 2)
   = 2 * acos(1 - dblEpsilon / 8)
  ~= 2 * asin(sqrt(dblEpsilon / 4)
  ~= sqrt(dblEpsilon)
  ~= 1.5e-8

which is 9.5 cm on the Earth's surface.

func ChordAngleFromAngle 

func ChordAngleFromAngle(a Angle) ChordAngle

ChordAngleFromAngle returns a ChordAngle from the given Angle.

func ChordAngleFromSquaredLength 

func ChordAngleFromSquaredLength(length2 float64) ChordAngle

ChordAngleFromSquaredLength returns a ChordAngle from the squared chord length. Note that the argument is automatically clamped to a maximum of 4 to handle possible roundoff errors. The argument must be non-negative.

func InfChordAngle 

func InfChordAngle() ChordAngle

InfChordAngle returns a chord angle larger than any finite chord angle. The only valid operations on an InfChordAngle are comparisons, Angle conversions, and Successor/Predecessor.

func (ChordAngle) Add 

func (c ChordAngle) Add(other ChordAngle) ChordAngle

Add adds the other ChordAngle to this one and returns the resulting value. This method assumes the ChordAngles are not special.

func (ChordAngle) Angle 

func (c ChordAngle) Angle() Angle

Angle converts this ChordAngle to an Angle.

func (ChordAngle) Cos 

func (c ChordAngle) Cos() float64

Cos returns the cosine of this chord angle. This method is more efficient than converting to Angle and performing the computation.

func (ChordAngle) Expanded 

func (c ChordAngle) Expanded(e float64) ChordAngle

Expanded returns a new ChordAngle that has been adjusted by the given error bound (which can be positive or negative). Error should be the value returned by either MaxPointError or MaxAngleError. For example: 

a := ChordAngleFromPoints(x, y)
a1 := a.Expanded(a.MaxPointError())

func (ChordAngle) IsInfinity 

func (c ChordAngle) IsInfinity() bool

IsInfinity reports whether this ChordAngle is infinite.

func (ChordAngle) MaxAngleError 

func (c ChordAngle) MaxAngleError() float64

MaxAngleError returns the maximum error for a ChordAngle constructed as an Angle distance.

func (ChordAngle) MaxPointError 

func (c ChordAngle) MaxPointError() float64

MaxPointError returns the maximum error size for a ChordAngle constructed from 2 Points x and y, assuming that x and y are normalized to within the bounds guaranteed by s2.Point.Normalize. The error is defined with respect to the true distance after the points are projected to lie exactly on the sphere.

func (ChordAngle) Predecessor 

func (c ChordAngle) Predecessor() ChordAngle

Predecessor returns the largest representable ChordAngle less than this one.

Note the following special cases: 

InfChordAngle.Predecessor == StraightChordAngle
ChordAngle(0).Predecessor == NegativeChordAngle
NegativeChordAngle.Predecessor == NegativeChordAngle

func (ChordAngle) Sin 

func (c ChordAngle) Sin() float64

Sin returns the sine of this chord angle. This method is more efficient than converting to Angle and performing the computation.

func (ChordAngle) Sin2 

func (c ChordAngle) Sin2() float64

Sin2 returns the square of the sine of this chord angle. It is more efficient than Sin.

func (ChordAngle) Sub 

func (c ChordAngle) Sub(other ChordAngle) ChordAngle

Sub subtracts the other ChordAngle from this one and returns the resulting value. This method assumes the ChordAngles are not special.

func (ChordAngle) Successor 

func (c ChordAngle) Successor() ChordAngle

Successor returns the smallest representable ChordAngle larger than this one. This can be used to convert a "<" comparison to a "<=" comparison.

Note the following special cases: 

NegativeChordAngle.Successor == 0
StraightChordAngle.Successor == InfChordAngle
InfChordAngle.Successor == InfChordAngle

func (ChordAngle) Tan 

func (c ChordAngle) Tan() float64

Tan returns the tangent of this chord angle.

type Interval 

type Interval struct {
	Lo, Hi float64
}

An Interval represents a closed interval on a unit circle (also known as a 1-dimensional sphere). It is capable of representing the empty interval (containing no points), the full interval (containing all points), and zero-length intervals (containing a single point).

Points are represented by the angle they make with the positive x-axis in the range [-π, π]. An interval is represented by its lower and upper bounds (both inclusive, since the interval is closed). The lower bound may be greater than the upper bound, in which case the interval is "inverted" (i.e. it passes through the point (-1, 0)).

The point (-1, 0) has two valid representations, π and -π. The normalized representation of this point is π, so that endpoints of normal intervals are in the range (-π, π]. We normalize the latter to the former in IntervalFromEndpoints. However, we take advantage of the point -π to construct two special intervals: 

The full interval is [-π, π]
The empty interval is [π, -π].

Treat the exported fields as read-only.

func EmptyInterval 

func EmptyInterval() Interval

EmptyInterval returns an empty interval.

func FullInterval 

func FullInterval() Interval

FullInterval returns a full interval.

func IntervalFromEndpoints 

func IntervalFromEndpoints(lo, hi float64) Interval

IntervalFromEndpoints constructs a new interval from endpoints. Both arguments must be in the range [-π,π]. This function allows inverted intervals to be created.

func IntervalFromPointPair 

func IntervalFromPointPair(a, b float64) Interval

IntervalFromPointPair returns the minimal interval containing the two given points. Both arguments must be in [-π,π].

func (Interval) AddPoint 

func (i Interval) AddPoint(p float64) Interval

AddPoint returns the interval expanded by the minimum amount necessary such that it contains the given point "p" (an angle in the range [-π, π]).

func (Interval) ApproxEqual 

func (i Interval) ApproxEqual(other Interval) bool

ApproxEqual reports whether this interval can be transformed into the given interval by moving each endpoint by at most ε, without the endpoints crossing (which would invert the interval). Empty and full intervals are considered to start at an arbitrary point on the unit circle, so any interval with (length <= 2*ε) matches the empty interval, and any interval with (length >= 2*π - 2*ε) matches the full interval.

func (Interval) Center 

func (i Interval) Center() float64

Center returns the midpoint of the interval. It is undefined for full and empty intervals.

func (Interval) Complement 

func (i Interval) Complement() Interval

Complement returns the complement of the interior of the interval. An interval and its complement have the same boundary but do not share any interior values. The complement operator is not a bijection, since the complement of a singleton interval (containing a single value) is the same as the complement of an empty interval.

func (Interval) ComplementCenter 

func (i Interval) ComplementCenter() float64

ComplementCenter returns the midpoint of the complement of the interval. For full and empty intervals, the result is arbitrary. For a singleton interval (containing a single point), the result is its antipodal point on S1.

func (Interval) Contains 

func (i Interval) Contains(p float64) bool

Contains returns true iff the interval contains p. Assumes p ∈ [-π,π].

func (Interval) ContainsInterval 

func (i Interval) ContainsInterval(oi Interval) bool

ContainsInterval returns true iff the interval contains oi.

func (Interval) DirectedHausdorffDistance 

func (i Interval) DirectedHausdorffDistance(y Interval) Angle

DirectedHausdorffDistance returns the Hausdorff distance to the given interval. For two intervals i and y, this distance is defined by 

h(i, y) = max_{p in i} min_{q in y} d(p, q),

where d(.,.) is measured along S1.

Example 
package main

import (
	"fmt"
	"math"

	"github.com/golang/geo/s1"
)

func main() {
	// Small interval around the midpoints between quadrants, such that
	// the center of each interval is offset slightly CCW from the midpoint.
	mid := s1.IntervalFromEndpoints(math.Pi/2-0.01, math.Pi/2+0.02)
	fmt.Println("empty to empty: ", s1.EmptyInterval().DirectedHausdorffDistance(s1.EmptyInterval()))
	fmt.Println("empty to mid12: ", s1.EmptyInterval().DirectedHausdorffDistance(mid))
	fmt.Println("mid12 to empty: ", mid.DirectedHausdorffDistance(s1.EmptyInterval()))

	// Quadrant pair.
	quad2 := s1.IntervalFromEndpoints(0, -math.Pi)
	// Quadrant triple.
	quad3 := s1.IntervalFromEndpoints(0, -math.Pi/2)
	fmt.Println("quad12 to quad123 ", quad2.DirectedHausdorffDistance(quad3))

	// An interval whose complement center is 0.
	in := s1.IntervalFromEndpoints(3, -3)

	ivs := []s1.Interval{s1.IntervalFromEndpoints(-0.1, 0.2), s1.IntervalFromEndpoints(0.1, 0.2), s1.IntervalFromEndpoints(-0.2, -0.1)}
	for _, iv := range ivs {
		fmt.Printf("dist from %v to in: %f\n", iv, iv.DirectedHausdorffDistance(in))
	}
}

Output:

empty to empty:  0.0000000
empty to mid12:  0.0000000
mid12 to empty:  180.0000000
quad12 to quad123  0.0000000
dist from [-0.1000000, 0.2000000] to in: 3.000000
dist from [0.1000000, 0.2000000] to in: 2.900000
dist from [-0.2000000, -0.1000000] to in: 2.900000

func (Interval) Expanded 

func (i Interval) Expanded(margin float64) Interval

Expanded returns an interval that has been expanded on each side by margin. If margin is negative, then the function shrinks the interval on each side by margin instead. The resulting interval may be empty or full. Any expansion (positive or negative) of a full interval remains full, and any expansion of an empty interval remains empty.

func (Interval) InteriorContains 

func (i Interval) InteriorContains(p float64) bool

InteriorContains returns true iff the interior of the interval contains p. Assumes p ∈ [-π,π].

func (Interval) InteriorContainsInterval 

func (i Interval) InteriorContainsInterval(oi Interval) bool

InteriorContainsInterval returns true iff the interior of the interval contains oi.

func (Interval) InteriorIntersects 

func (i Interval) InteriorIntersects(oi Interval) bool

InteriorIntersects returns true iff the interior of the interval contains any points in common with oi, including the latter's boundary.

func (Interval) Intersection 

func (i Interval) Intersection(oi Interval) Interval

Intersection returns the smallest interval that contains the intersection of the interval and oi.

func (Interval) Intersects 

func (i Interval) Intersects(oi Interval) bool

Intersects returns true iff the interval contains any points in common with oi.

func (Interval) Invert 

func (i Interval) Invert() Interval

Invert returns the interval with endpoints swapped.

func (Interval) IsEmpty 

func (i Interval) IsEmpty() bool

IsEmpty reports whether the interval is empty.

func (Interval) IsFull 

func (i Interval) IsFull() bool

IsFull reports whether the interval is full.

func (Interval) IsInverted 

func (i Interval) IsInverted() bool

IsInverted reports whether the interval is inverted; that is, whether Lo > Hi.

func (Interval) IsValid 

func (i Interval) IsValid() bool

IsValid reports whether the interval is valid.

func (Interval) Length 

func (i Interval) Length() float64

Length returns the length of the interval. The length of an empty interval is negative.

func (Interval) Project 

func (i Interval) Project(p float64) float64

Project returns the closest point in the interval to the given point p. The interval must be non-empty.

func (Interval) String 

func (i Interval) String() string

func (Interval) Union 

func (i Interval) Union(oi Interval) Interval

Union returns the smallest interval that contains both the interval and oi.

Notes

Bugs

  • The major differences from the C++ version are:

    • no unsigned E5/E6/E7 methods

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.