geo

package module
v0.0.0-...-516b90f Latest Latest
Warning

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

 Go to latest Published: Mar 30, 2018 License: MIT Imports: 9 Imported by: 0

README

go.geo

Go.geo is a geometry/geography library in Go. The primary use case is GIS geometry manipulation on the server side vs. in the browser using javascript. This may be motivated by memory, computation time or data privacy constraints. All objects are defined in a 2D context.

Imports as package name geo:
import "github.com/paulmach/go.geo"

Build Status Coverage Status Godoc Reference

Exposed objects

  • Point represents a 2D location, x/y or lng/lat. It is up to the programmer to know if the data is a lng/lat location, projection of that point, or a vector. Useful features:

    • Project between WGS84 (EPSG:4326) and Mercator (EPSG:3857) or Scalar Mercator (map tiles). See examples below.
    • GeoHash and Quadkey support.
    • Supports vector functions like add, scale, etc.

  • Line represents the shortest distance between two points in Euclidean space. In many cases the path object is more useful.

  • PointSet represents a set of points with methods such as DistanceFrom() and Centroid().

  • Path is an extention of PointSet with methods for working with a polyline. Functions for converting to/from Google's polyline encoding are included.

  • Bound represents a rectangular 2D area defined by North, South, East, West values. Computable for Line and Path objects, used by the Surface object.

  • Surface is used to assign values to points in a 2D area, such as elevation.

Library conventions

There are two big conventions that developers should be aware of: functions are chainable and operations modify the original object. For example:

p := geo.NewPoint(0, 0)
p.SetX(10).Add(geo.NewPoint(10, 10))
p.Equals(geo.NewPoint(20, 10))  // == true

If you want to create a copy, all objects support the Clone() method.

p1 := geo.NewPoint(10, 10)
p2 := p1.SetY(20)
p1.Equals(p2) // == true, in this case p1 and p2 point to the same memory

p2 := p1.Clone().SetY(30)
p1.Equals(p2) // == false

These conventions put a little extra load on the programmer, but tests showed that making a copy every time was significantly slower. Similar conventions are found in the math/big package of the Golang standard library.

Databases, WKT and WKB

To make it easy to get and set data from spatial databases, all geometries support direct scanning of query results. However, they must be retrieved in WKB format using functions such as PostGIS' ST_AsBinary.

For example, this query from a Postgres/PostGIS database:

row := db.QueryRow("SELECT ST_AsBinary(point_column) FROM postgis_table")

var p *geo.Point
row.Scan(&p)

For MySQL, Geometry data is stored as SRID+WKB and the library detects and works with this prefixed WKB data. So fetching spatial data from a MySQL database is even simpler:

row := db.QueryRow("SELECT point_column FROM mysql_table")

var p *geo.Point
row.Scan(&p)

Inserts and updates can be made using the .ToWKT() methods. For example:

db.Exec("INSERT INTO mysql_table (point_column) VALUES (GeomFromText(?))", p.ToWKT())

This has been tested using MySQL 5.5, MySQL 5.6 and PostGIS 2.0 using the Point, LineString, MultiPoint and Polygon 2d spatial data types.

Reducers

The reducers sub-package includes implementations for Douglas-Peucker, Visvalingam and Radial polyline reduction algorithms. See the reducers godoc for more information.

GeoJSON

All geometries support .ToGeoJSON() that return *geojson.Feature objects with the correct sub-geometry. For example:

feature := path.ToGeoJSON()
feature.SetProperty("type", "road")

encodedJSON, _ := feature.MarshalJSON()

Examples

The GoDoc Documentation provides a very readable list of exported functions. Below are a few usage examples.

Projections
lnglatPoint := geo.NewPoint(-122.4167, 37.7833)

// Mercator, EPSG:3857
mercator := geo.Mercator.Project(latlngPoint)
backToLnglat := geo.Mercator.Inverse(mercator)

// ScalarMercator or Google World Coordinates
tileX, TileY := geo.ScalarMercator.Project(latlngPoint.Lng(), latlngPoint.Lat())
tileZ := geo.ScalarMercator.Level

// level 16 tile the point is in
tileX >>= (geo.ScalarMercator.Level - 16)
tileY >>= (geo.ScalarMercator.Level - 16)
tileZ = 16
Encode/Decode polyline path
// lng/lat data, in this case, is encoded at 6 decimal place precision
path := geo.NewPathFromEncoding("smsqgAtkxvhFwf@{zCeZeYdh@{t@}BiAmu@sSqg@cjE", 1e6)

// reduce using the Douglas Peucker line reducer from the reducers sub-package.
// Note the threshold distance is in the coordinates of the points,
// which in this case is degrees.
reducedPath := reducers.DouglasPeucker(path, 1.0e-5)

// encode with the default/typical 5 decimal place precision
encodedString := reducedPath.Encode() 

// encode as json [[lng1,lat1],[lng2, lat2],...]
// using encoding/json from the standard library.
encodedJSON, err := json.Marshal(reducedPath)
Path, line intersection
path := geo.NewPath()
path.Push(geo.NewPoint(0, 0))
path.Push(geo.NewPoint(1, 1))

line := geo.NewLine(geo.NewPoint(0, 1), geo.NewPoint(1, 0))

// intersects does a simpler check for yes/no
if path.Intersects(line) {
	// intersection will return the actual points and places on intersection
	points, segments := path.Intersection(line)

	for i, _ := range points {
		log.Printf("Intersection %d at %v with path segment %d", i, points[i], segments[i][0])
	}
}

Surface

A surface object is defined by a bound (lng/lat georegion for example) and a width and height defining the number of discrete points in the bound. This allows for access such as:

surface.Grid[x][y]         // the value at a location in the grid
surface.GetPoint(x, y)     // the point, which will be in the space as surface.bound,
                           // corresponding to surface.Grid[x][y]
surface.ValueAt(*Point)    // the bi-linearly interpolated grid value for any point in the bounds
surface.GradientAt(*Point) // the gradient of the surface a any point in the bounds,
                           // returns a point object which should be treated as a vector

A couple things about how the bound area is discretized in the grid:

  • surface.Grid[0][0] corresponds to the surface.Bound.SouthWest() location, or bottom left corner or the bound
  • surface.Grid[0][surface.Height-1] corresponds to the surface.Bound.NorthWest() location, the extreme points in the grid are on the edges of the bound

While these conventions are useful, they are different. If you're using this object, your feedback on these choices would be appreciated.

Performance  

This code is meant to act as a core library to more advanced geo algorithms, like slide for example. Thus, performance is very important. Included are a good set of benchmarks covering the core functions and efforts have been made to optimize them. Recent improvements:

                                      old         new        delta
BenchmarkPointDistanceFrom             8.16        5.91      -27.57%
BenchmarkPointSquaredDistanceFrom      1.63        1.62       -0.61%
BenchmarkPointQuadKey                271         265          -2.21%
BenchmarkPointQuadKeyString         2888         522         -81.93%
BenchmarkPointGeoHash                302         308           1.99%
BenchmarkPointGeoHashInt64           165         158          -4.24%
BenchmarkPointNormalize               22.3        17.6       -21.08%
BenchmarkPointEquals                   1.65        1.29      -21.82%
BenchmarkPointClone                    7.46        0.97      -87.00%

BenchmarkLineDistanceFrom             15.5        13.2       -14.84%
BenchmarkLineSquaredDistanceFrom       9.3         9.24       -0.65%
BenchmarkLineProject                   8.75        8.73       -0.23%
BenchmarkLineMeasure                  21.3        20          -6.10%
BenchmarkLineInterpolate              44.9        44.6        -0.67%
BenchmarkLineMidpoint                 47.2         5.13      -89.13%
BenchmarkLineEquals                    9.38       10.4        10.87%
BenchmarkLineClone                    70.5         3.26      -95.38%

BenchmarkPathDistanceFrom           6190        4662         -24.68%
BenchmarkPathSquaredDistanceFrom    5076        4625          -8.88%
BenchmarkPathMeasure               10080        7626         -24.35%
BenchmarkPathResampleToMorePoints  69380       17255         -75.13%
BenchmarkPathResampleToLessPoints  26093        6780         -74.02%

Units are Nanoseconds per Operation and run using Golang 1.3.1 on a 2012 Macbook Air with a 2GHz Intel Core i7 processor. The old version corresponds to a commit on Sept. 22, 2014 and the new version corresponds to a commit on Sept 24, 2014. These benchmarks can be run using:

go get github.com/paulmach/go.geo
go test github.com/paulmach/go.geo -bench .

Projects making use of this package

Contributing

While this project started as the core of Slide it's now being used in many place. So, if you have features you'd like to add or improvements to make, please submit a pull request. A big thank you to those who have contributed so far:

Documentation

Overview

Package geo is a geometry/geography library in Go. Its purpose is to allow for basic point, line and path operations in the context of online mapping.

Index

Constants

This section is empty.

Variables

View Source 
var (
	// ErrUnsupportedDataType is returned by Scan methods when asked to scan
	// non []byte data from the database. This should never happen
	// if the driver is acting appropriately.
	ErrUnsupportedDataType = errors.New("go.geo: scan value must be []byte")

	// ErrNotWKB is returned when unmarshalling WKB and the data is not valid.
	ErrNotWKB = errors.New("go.geo: invalid WKB data")

	// ErrIncorrectGeometry is returned when unmarshalling WKB data into the wrong type.
	// For example, unmarshaling linestring data into a point.
	ErrIncorrectGeometry = errors.New("go.geo: incorrect geometry")
)
View Source 
var EarthRadius = 6378137.0 // meters

EarthRadius is the radius of the earth in meters. It is used in geo distance calculations. To keep things consistent, this values matches that used in WGS84 Web Mercator (EPSG:3857).

View Source 
var GeoHashPrecision = 12

GeoHashPrecision is the number of characters of a encoded GeoHash.

View Source 
var InfinityPoint = &Point{math.Inf(1), math.Inf(1)}

InfinityPoint is the point at [inf, inf]. Currently returned for the intersection of two collinear overlapping lines.

View Source 
var Mercator = Projection{
	Project: func(p *Point) {
		p.SetX(mercatorPole / 180.0 * p.Lng())

		y := math.Log(math.Tan((90.0+p.Lat())*math.Pi/360.0)) / math.Pi * mercatorPole
		p.SetY(math.Max(-mercatorPole, math.Min(y, mercatorPole)))
	},
	Inverse: func(p *Point) {
		p.SetLng(p.X() * 180.0 / mercatorPole)
		p.SetLat(180.0 / math.Pi * (2*math.Atan(math.Exp((p.Y()/mercatorPole)*math.Pi)) - math.Pi/2.0))
	},
}

Mercator projection, performs EPSG:3857, sometimes also described as EPSG:900913.

View Source 
var ScalarMercator struct {
	Level   uint64
	Project func(lng, lat float64, level ...uint64) (x, y uint64)
	Inverse func(x, y uint64, level ...uint64) (lng, lat float64)
}

ScalarMercator converts from lng/lat float64 to x,y uint64. This is the same as Google's world coordinates.

View Source 
var TransverseMercator = Projection{
	Project: func(p *Point) {
		radLat := deg2rad(p.Lat())
		radLng := deg2rad(p.Lng())

		sincos := math.Sin(radLng) * math.Cos(radLat)
		p.SetX(0.5 * math.Log((1+sincos)/(1-sincos)) * EarthRadius)

		p.SetY(math.Atan(math.Tan(radLat)/math.Cos(radLng)) * EarthRadius)
	},
	Inverse: func(p *Point) {
		x := p.X() / EarthRadius
		y := p.Y() / EarthRadius

		lng := math.Atan(math.Sinh(x) / math.Cos(y))
		lat := math.Asin(math.Sin(y) / math.Cosh(x))

		p.SetLng(rad2deg(lng))
		p.SetLat(rad2deg(lat))
	},
}

TransverseMercator implements a default transverse Mercator projector that will only work well +-10 degrees around longitude 0.

View Source 
var UseHaversineGeoDistanceByDefault = false

UseHaversineGeoDistanceByDefault indicates if the more complicated Haversine formula should be used for geo distances.

Functions

func MercatorScaleFactor 

func MercatorScaleFactor(degreesLatitude float64) float64

MercatorScaleFactor returns the mercator scaling factor for a given degree latitude.

Types

type Bound 

type Bound struct {
	// contains filtered or unexported fields
}

A Bound represents an enclosed "box" in the 2D Euclidean or Cartesian plane. It does not know anything about the anti-meridian.

func NewBound 

func NewBound(west, east, south, north float64) *Bound

NewBound creates a new bound given the parameters.

func NewBoundFromGeoHash 

func NewBoundFromGeoHash(hash string) *Bound

NewBoundFromGeoHash creates a new bound for the region defined by the GeoHash.

func NewBoundFromGeoHashInt64 

func NewBoundFromGeoHashInt64(hash int64, bits int) *Bound

NewBoundFromGeoHashInt64 creates a new bound from the region defined by the GeoHesh. bits indicates the precision of the hash.

func NewBoundFromMapTile 

func NewBoundFromMapTile(x, y, z uint64) *Bound

NewBoundFromMapTile creates a bound given an online map tile index. Panics if x or y is out of range for zoom level.

func NewBoundFromPoints 

func NewBoundFromPoints(corner, oppositeCorner *Point) *Bound

NewBoundFromPoints creates a new bound given two opposite corners. These corners can be either sw/ne or se/nw.

func NewGeoBoundAroundPoint 

func NewGeoBoundAroundPoint(center *Point, distance float64) *Bound

NewGeoBoundAroundPoint creates a new bound given a center point, and a distance from the center point in meters

func (*Bound) Bottom 

func (b *Bound) Bottom() float64

Bottom returns the south side of the bound.

func (*Bound) Center 

func (b *Bound) Center() *Point

Center returns the center of the bound.

func (*Bound) Clone 

func (b *Bound) Clone() *Bound

Clone returns a copy of the bound.

func (*Bound) Contains 

func (b *Bound) Contains(point *Point) bool

Contains determines if the point is within the bound. Points on the boundary are considered within.

func (*Bound) East 

func (b *Bound) East() float64

East returns the right of the bound.

func (*Bound) Empty 

func (b *Bound) Empty() bool

Empty returns true if it contains zero area or if it's in some malformed negative state where the left point is larger than the right. This can be caused by padding too much negative.

func (*Bound) Equals 

func (b *Bound) Equals(c *Bound) bool

Equals returns if two bounds are equal.

func (*Bound) Extend 

func (b *Bound) Extend(point *Point) *Bound

Extend grows the bound to include the new point.

func (*Bound) GeoHeight 

func (b *Bound) GeoHeight() float64

GeoHeight returns the approximate height in meters. Only applies if the data is Lng/Lat degrees (EPSG:4326).

func (*Bound) GeoPad 

func (b *Bound) GeoPad(meters float64) *Bound

GeoPad expands the bound in all directions by the given amount of meters. Only applies if the data is Lng/Lat degrees.

func (*Bound) GeoWidth 

func (b *Bound) GeoWidth(haversine ...bool) float64

GeoWidth returns the approximate width in meters of the center of the bound. Only applies if the data is Lng/Lat degrees.

func (*Bound) Height 

func (b *Bound) Height() float64

Height returns just the difference in the point's Y/Latitude.

func (*Bound) Intersects 

func (b *Bound) Intersects(bound *Bound) bool

Intersects determines if two bounds intersect. Returns true if they are touching.

func (*Bound) Left 

func (b *Bound) Left() float64

Left returns the west side of the bound.

func (*Bound) MarshalJSON 

func (b *Bound) MarshalJSON() ([]byte, error)

MarshalJSON enables bounds to be encoded as JSON using the encoding/json package.

func (*Bound) North 

func (b *Bound) North() float64

North returns the top of the bound.

func (*Bound) NorthEast 

func (b *Bound) NorthEast() *Point

NorthEast returns the upper right corner of the bound.

func (*Bound) NorthWest 

func (b *Bound) NorthWest() *Point

NorthWest returns the upper left corner of the bound.

func (*Bound) Pad 

func (b *Bound) Pad(amount float64) *Bound

Pad expands the bound in all directions by the amount given. The amount must be in the units of the bounds. Technically one can pad with negative value, but no error checking is done.

func (*Bound) Right 

func (b *Bound) Right() float64

Right returns the east side of the bound.

func (*Bound) Set 

func (b *Bound) Set(west, east, south, north float64)

Set allows for the modification of the bound values in place.

func (*Bound) South 

func (b *Bound) South() float64

South returns the bottom of the bound.

func (*Bound) SouthEast 

func (b *Bound) SouthEast() *Point

SouthEast returns the lower right corner of the bound.

func (*Bound) SouthWest 

func (b *Bound) SouthWest() *Point

SouthWest returns the lower left corner of the bound.

func (*Bound) String 

func (b *Bound) String() string

String returns the string respentation of the bound in WKT format. POLYGON(west, south, west, north, east, north, east, south, west, south)

func (*Bound) ToLine 

func (b *Bound) ToLine() *Line

ToLine returns a Line from the southwest corner to the northeast.

func (*Bound) ToMysqlIntersectsCondition 

func (b *Bound) ToMysqlIntersectsCondition(column string) string

ToMysqlIntersectsCondition returns a condition defining the intersection of the column and the bound. To be used in a MySQL query.

func (*Bound) Top 

func (b *Bound) Top() float64

Top returns the north side of the bound.

func (*Bound) Union 

func (b *Bound) Union(other *Bound) *Bound

Union extends this bounds to contain the union of this and the given bounds.

func (*Bound) UnmarshalJSON 

func (b *Bound) UnmarshalJSON(data []byte) error

UnmarshalJSON enables bounds to be decoded as JSON using the encoding/json package.

func (*Bound) West 

func (b *Bound) West() float64

West returns the left of the bound.

func (*Bound) Width 

func (b *Bound) Width() float64

Width returns just the difference in the point's X/Longitude.

type GeoReducer 

type GeoReducer interface {
	GeoReduce(*Path) *Path
}

A GeoReducer reduces a path in EPSG:4326 (lng/lat) using any simplification algorithm. It should return a copy of the path, also in EPSG:4326, and not modify the original.

type Line 

type Line struct {
	// contains filtered or unexported fields
}

Line represents the shortest path between A and B.

func NewLine 

func NewLine(a, b *Point) *Line

NewLine creates a new line by cloning the provided points.

func NewLineFromWKB 

func NewLineFromWKB(wkb []byte) *Line

NewLineFromWKB will take raw WKB and set the data for a new line. The WKB data must of type LineString and only contain 2 points. Will return nil if invalid WKB.

func (*Line) A 

func (l *Line) A() *Point

A returns a pointer to the first point in the line.

func (*Line) B 

func (l *Line) B() *Point

B returns a pointer to the second point in the line.

func (*Line) Bound 

func (l *Line) Bound() *Bound

Bound returns a bound around the line. Simply uses rectangular coordinates.

func (Line) Clone 

func (l Line) Clone() *Line

Clone returns a deep copy of the line.

func (*Line) Direction 

func (l *Line) Direction() float64

Direction computes the direction the line is pointing from A() to B(). The units are radians from the positive x-axis. Range same as math.Atan2, [-Pi, Pi]

func (*Line) Distance 

func (l *Line) Distance() float64

Distance computes the distance of the line, ie. its length, in Euclidian space.

func (*Line) DistanceFrom 

func (l *Line) DistanceFrom(point *Point) float64

DistanceFrom does NOT use spherical geometry. It finds the distance from the line using standard Euclidean geometry, using the units the points are in.

func (*Line) Equals 

func (l *Line) Equals(line *Line) bool

Equals returns the line equality and is irrespective of direction, i.e. true if one is the reverse of the other.

func (*Line) GeoDistance 

func (l *Line) GeoDistance(haversine ...bool) float64

GeoDistance computes the distance of the line, ie. its length, using spherical geometry.

func (*Line) GeoMidpoint 

func (l *Line) GeoMidpoint() *Point

GeoMidpoint returns the half-way point along a great circle path between the two points.

func (*Line) Interpolate 

func (l *Line) Interpolate(percent float64) *Point

Interpolate performs a simple linear interpolation, from A to B. This function is the opposite of Project.

func (*Line) Intersection 

func (l *Line) Intersection(line *Line) *Point

Intersection finds the intersection of the two lines or nil, if the lines are collinear will return NewPoint(math.Inf(1), math.Inf(1)) == InfinityPoint

func (*Line) Intersects 

func (l *Line) Intersects(line *Line) bool

Intersects will return true if the lines are collinear AND intersect. Based on: http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/

func (*Line) MarshalJSON 

func (l *Line) MarshalJSON() ([]byte, error)

MarshalJSON enables lines to be encoded as JSON using the encoding/json package.

func (*Line) Measure 

func (l *Line) Measure(point *Point) float64

Measure returns the distance along the line to the point nearest the given point. Treats the line as a line segment such that if the nearest point is an endpoint of the line, the function will return 0 or 1 as appropriate.

func (*Line) Midpoint 

func (l *Line) Midpoint() *Point

Midpoint returns the Euclidean midpoint of the line.

func (*Line) Project 

func (l *Line) Project(point *Point) float64

Project returns the normalized distance of the point on the line nearest the given point. Returned values may be outside of [0,1]. This function is the opposite of Interpolate.

func (*Line) Reverse 

func (l *Line) Reverse() *Line

Reverse swaps the start and end of the line.

func (*Line) Scan 

func (l *Line) Scan(value interface{}) error

Scan implements the sql.Scanner interface allowing line structs to be passed into rows.Scan(...interface{}) The column must be of type LineString and contain 2 points, or an error will be returned. Data must be fetched in WKB format. Will attempt to parse MySQL's SRID+WKB format if the data is of the right size. If the column is empty (not null) an empty line [(0, 0), (0, 0)] will be returned.

func (*Line) Side 

func (l *Line) Side(p *Point) int

Side returns 1 if the point is on the right side, -1 if on the left side, and 0 if collinear.

func (*Line) SquaredDistance 

func (l *Line) SquaredDistance() float64

SquaredDistance computes the squared distance of the line, ie. its length, in Euclidian space. This can save a sqrt computation.

func (*Line) SquaredDistanceFrom 

func (l *Line) SquaredDistanceFrom(point *Point) float64

SquaredDistanceFrom does NOT use spherical geometry. It finds the squared distance from the line using standard Euclidean geometry, using the units the points are in.

func (*Line) String 

func (l *Line) String() string

String returns a string representation of the line. The format is WKT, e.g. LINESTRING(30 10,10 30)

func (*Line) ToGeoJSON 

func (l *Line) ToGeoJSON() *geojson.Feature

ToGeoJSON creates a new geojson feature with a linestring geometry containing the two points.

func (*Line) ToWKT 

func (l *Line) ToWKT() string

ToWKT returns the line in WKT format, eg. LINESTRING(30 10,10 30)

func (*Line) Transform 

func (l *Line) Transform(projector Projector) *Line

Transform applies a given projection or inverse projection to the current line. Modifies the line.

func (*Line) UnmarshalJSON 

func (l *Line) UnmarshalJSON(data []byte) error

UnmarshalJSON enables lines to be decoded as JSON using the encoding/json package.

type Path 

type Path struct {
	PointSet
}

Path represents a set of points to be thought of as a polyline.

func Decode 

func Decode(encoded string, factor ...int) *Path

Decode is deprecated, use NewPathFromEncoding

func NewPath 

func NewPath() *Path

NewPath creates a new path.

func NewPathFromEncoding 

func NewPathFromEncoding(encoded string, factor ...int) *Path

NewPathFromEncoding is the inverse of path.Encode. It takes a string encoding of a lat/lng path and returns the actual path it represents. Factor defaults to 1.0e5, the same used by Google for polyline encoding.

func NewPathFromFlatXYData 

func NewPathFromFlatXYData(data []float64) *Path

NewPathFromFlatXYData creates a path from a slice of float64 values representing horizontal, vertical type data. Coordinates in even positions correspond to X values. Coordinates in odd positions correspond to Y values

func NewPathFromWKB 

func NewPathFromWKB(wkb []byte) *Path

NewPathFromWKB will take raw WKB and set the data for a new path. The WKB data must be of type LineString, Polygon or MultiPoint. Will return nil if invalid WKB.

func NewPathFromXYData 

func NewPathFromXYData(data [][2]float64) *Path

NewPathFromXYData creates a path from a slice of [2]float64 values representing [horizontal, vertical] type data, for example lng/lat values from geojson.

func NewPathFromXYSlice 

func NewPathFromXYSlice(data [][]float64) *Path

NewPathFromXYSlice creates a path from a slice of []float64 values. The first two elements are taken to be horizontal and vertical components of each point respectively. The rest of the elements of the slice are ignored. Nil slices are skipped.

func NewPathFromYXData 

func NewPathFromYXData(data [][2]float64) *Path

NewPathFromYXData creates a path from a slice of [2]float64 values representing [vertical, horizontal] type data, for example typical lat/lng data.

func NewPathFromYXSlice 

func NewPathFromYXSlice(data [][]float64) *Path

NewPathFromYXSlice creates a path from a slice of []float64 values. The first two elements are taken to be vertical and horizontal components of each point respectively. The rest of the elements of the slice are ignored. Nil slices are skipped.

func NewPathPreallocate 

func NewPathPreallocate(length, capacity int) *Path

NewPathPreallocate creates a new path with points array of the given size.

func (*Path) Bound 

func (p *Path) Bound() *Bound

Bound returns a bound around the path. Uses rectangular coordinates.

func (*Path) Clone 

func (p *Path) Clone() *Path

Clone returns a new copy of the path.

func (*Path) DirectionAt 

func (p *Path) DirectionAt(index int) float64

DirectionAt computes the direction of the path at the given index. Uses the line between the two surrounding points to get the direction, or just the first two, or last two if at the start or end, respectively. Assumes the path is in a conformal projection. The units are radians from the positive x-axis. Range same as math.Atan2, [-Pi, Pi] Returns INF for single point paths.

func (*Path) Distance 

func (p *Path) Distance() float64

Distance computes the total distance in the units of the points.

func (*Path) DistanceFrom 

func (p *Path) DistanceFrom(point *Point) float64

DistanceFrom computes an O(n) distance from the path. Loops over every subline to find the minimum distance.

func (*Path) Encode 

func (p *Path) Encode(factor ...int) string

Encode converts the path to a string using the Google Maps Polyline Encoding method. Factor defaults to 1.0e5, the same used by Google for polyline encoding.

func (*Path) Equals 

func (p *Path) Equals(path *Path) bool

Equals compares two paths. Returns true if lengths are the same and all points are Equal.

func (*Path) GeoDistance 

func (p *Path) GeoDistance(haversine ...bool) float64

GeoDistance computes the total distance using spherical geometry.

func (*Path) GetAt 

func (p *Path) GetAt(i int) *Point

GetAt returns the pointer to the Point in the path. This function is good for modifying values in place. Returns nil if index is out of range.

func (*Path) InsertAt 

func (p *Path) InsertAt(index int, point *Point) *Path

InsertAt inserts a Point at i along the path. Panics if index is out of range.

func (*Path) Interpolate 

func (p *Path) Interpolate(percent float64) *Point

Interpolate performs a linear interpolation along the path

func (*Path) Intersection 

func (p *Path) Intersection(geometry interface{}) ([]*Point, [][2]int)

Intersection calls IntersectionPath or IntersectionLine depending on the type of the provided geometry. TODO: have this receive an Intersectable interface.

func (*Path) IntersectionLine 

func (p *Path) IntersectionLine(line *Line) ([]*Point, [][2]int)

IntersectionLine returns a slice of points and a slice of tuples [i, 0] where i is the segment in path that intersects with the line at the given point. Slices will be empty if there is no intersection.

func (*Path) IntersectionPath 

func (p *Path) IntersectionPath(path *Path) ([]*Point, [][2]int)

IntersectionPath returns a slice of points and a slice of tuples [i, j] where i is the segment in the parent path and j is the segment in the given path that intersect to form the given point. Slices will be empty if there is no intersection.

func (*Path) Intersects 

func (p *Path) Intersects(geometry interface{}) bool

Intersects can take a line or a path to determine if there is an intersection. TODO: I would love this to accept an intersecter interface.

func (*Path) IntersectsLine 

func (p *Path) IntersectsLine(line *Line) bool

IntersectsLine takes a Line and checks if it intersects with the path.

func (*Path) IntersectsPath 

func (p *Path) IntersectsPath(path *Path) bool

IntersectsPath takes a Path and checks if it intersects with the path.

func (*Path) Length 

func (p *Path) Length() int

Length returns the number of points in the path.

func (*Path) MarshalJSON 

func (p *Path) MarshalJSON() ([]byte, error)

MarshalJSON enables paths to be encoded as JSON using the encoding/json package.

func (*Path) Measure 

func (p *Path) Measure(point *Point) float64

Measure computes the distance along this path to the point nearest the given point.

func (*Path) Points 

func (p *Path) Points() []Point

Points returns the raw points storred with the path. Note the output is an array of Points (not pointers to points).

func (*Path) Pop 

func (p *Path) Pop() *Point

Pop removes and returns the last point.

func (*Path) Project 

func (p *Path) Project(point *Point) float64

Project computes the measure along this path closest to the given point, normalized to the length of the path.

func (*Path) Push 

func (p *Path) Push(point *Point) *Path

Push appends a point to the end of the path.

func (*Path) RemoveAt 

func (p *Path) RemoveAt(index int) *Path

RemoveAt removes a Point at i along the path. Panics if index is out of range.

func (*Path) Resample 

func (p *Path) Resample(totalPoints int) *Path

Resample converts the path into totalPoints-1 evenly spaced segments. Assumes euclidean geometry.

func (*Path) ResampleWithGeoInterval 

func (p *Path) ResampleWithGeoInterval(meters float64) *Path

ResampleWithGeoInterval converts the path into about evenly spaced points of about the given distance. The total distance is computed using spherical (lng/lat) geometry and divided by the given distance. The new points are chosen by linearly interpolating between two given points. This may not make sense in some contexts, especially if the path covers a large range of latitude.

func (*Path) ResampleWithInterval 

func (p *Path) ResampleWithInterval(dist float64) *Path

ResampleWithInterval coverts the path into evenly spaced points of about the given distance. The total distance is computed using euclidean geometry and then divided by the given distance to get the number of segments.

func (*Path) Scan 

func (p *Path) Scan(value interface{}) error

Scan implements the sql.Scanner interface allowing line structs to be passed into rows.Scan(...interface{}) The column must be of type LineString, Polygon or MultiPoint or an error will be returned. Data must be fetched in WKB format. Will attempt to parse MySQL's SRID+WKB format if obviously no WKB or parsing as WKB fails. If the column is empty (not null) an empty path will be returned.

func (*Path) SetAt 

func (p *Path) SetAt(index int, point *Point) *Path

SetAt updates a position at i along the path. Panics if index is out of range.

func (*Path) SetPoints 

func (p *Path) SetPoints(points []Point) *Path

SetPoints allows you to set the complete pointset yourself. Note that the input is an array of Points (not pointers to points).

func (*Path) SquaredDistanceFrom 

func (p *Path) SquaredDistanceFrom(point *Point) float64

SquaredDistanceFrom computes an O(n) minimum squared distance from the path. Loops over every subline to find the minimum distance.

func (*Path) String 

func (p *Path) String() string

String returns a string representation of the path. The format is WKT, e.g. LINESTRING(30 10,10 30,40 40) For empty paths the result will be 'EMPTY'.

func (*Path) ToGeoJSON 

func (p *Path) ToGeoJSON() *geojson.Feature

ToGeoJSON creates a new geojson feature with a linestring geometry containing all the points.

func (*Path) ToWKT 

func (p *Path) ToWKT() string

ToWKT returns the path in WKT format, eg. LINESTRING(30 10,10 30,40 40) For empty paths the result will be 'EMPTY'.

func (*Path) Transform 

func (p *Path) Transform(projector Projector) *Path

Transform applies a given projection or inverse projection to all the points in the path.

func (*Path) UnmarshalJSON 

func (p *Path) UnmarshalJSON(data []byte) error

UnmarshalJSON enables paths to be decoded as JSON using the encoding/json package.

func (*Path) WriteOffFile 

func (p *Path) WriteOffFile(w io.Writer, rgb ...[3]int)

WriteOffFile writes an Object File Format representation of the points of the path to the writer provided. This is for viewing in MeshLab or something like that. You should close the writer yourself after this function returns. http://segeval.cs.princeton.edu/public/off_format.html

type Point 

type Point [2]float64

A Point is a simple X/Y or Lng/Lat 2d point. [X, Y] or [Lng, Lat]

func NewPoint 

func NewPoint(x, y float64) *Point

NewPoint creates a new point

func NewPointFromGeoHash 

func NewPointFromGeoHash(hash string) *Point

NewPointFromGeoHash creates a new point at the center of the geohash range.

func NewPointFromGeoHashInt64 

func NewPointFromGeoHashInt64(hash int64, bits int) *Point

NewPointFromGeoHashInt64 creates a new point at the center of the integer version of a geohash range. bits indicates the precision of the hash.

func NewPointFromLatLng 

func NewPointFromLatLng(lat, lng float64) *Point

NewPointFromLatLng creates a new point from latlng

func NewPointFromQuadkey 

func NewPointFromQuadkey(key int64, level int) *Point

NewPointFromQuadkey creates a new point from a quadkey. See http://msdn.microsoft.com/en-us/library/bb259689.aspx for more information about this coordinate system.

func NewPointFromQuadkeyString 

func NewPointFromQuadkeyString(key string) *Point

NewPointFromQuadkeyString creates a new point from a quadkey string.

func NewPointFromWKB 

func NewPointFromWKB(wkb []byte) *Point

NewPointFromWKB will take raw WKB and set the data for a new point. The WKB data must be of type Point. Will return nil if invalid WKB point.

func (*Point) Add 

func (p *Point) Add(point *Point) *Point

Add a point to the given point.

func (*Point) BearingTo 

func (p *Point) BearingTo(point *Point) float64

BearingTo computes the direction one must start traveling on earth to be heading to the given point.

func (Point) Clone 

func (p Point) Clone() *Point

Clone creates a duplicate of the point.

func (*Point) DistanceFrom 

func (p *Point) DistanceFrom(point *Point) float64

DistanceFrom returns the Euclidean distance between the points.

func (*Point) Dot 

func (p *Point) Dot(v *Point) float64

Dot is just x1*x2 + y1*y2

func (*Point) Equals 

func (p *Point) Equals(point *Point) bool

Equals checks if the point represents the same point or vector.

func (*Point) GeoDistanceFrom 

func (p *Point) GeoDistanceFrom(point *Point, haversine ...bool) float64

GeoDistanceFrom returns the geodesic distance in meters.

func (*Point) GeoHash 

func (p *Point) GeoHash(chars ...int) string

GeoHash returns the geohash string of a point representing a lng/lat location. The resulting hash will be `GeoHashPrecision` characters long, default is 12. Optionally one can include their required number of chars precision.

func (*Point) GeoHashInt64 

func (p *Point) GeoHashInt64(bits int) (hash int64)

GeoHashInt64 returns the integer version of the geohash down to the given number of bits. The main usecase for this function is to be able to do integer based ordering of points. In that case the number of bits should be the same for all encodings.

func (*Point) Lat 

func (p *Point) Lat() float64

Lat returns the latitude/vertical component of the point.

func (*Point) Lng 

func (p *Point) Lng() float64

Lng returns the longitude/horizontal component of the point.

func (*Point) Normalize 

func (p *Point) Normalize() *Point

Normalize treats the point as a vector and scales it such that its distance from [0,0] is 1.

func (*Point) Point 

func (p *Point) Point() *Point

Point returns itself, so it implements the pointer interface.

func (*Point) Quadkey 

func (p *Point) Quadkey(level int) int64

Quadkey returns the quad key for the given point at the provided level. See http://msdn.microsoft.com/en-us/library/bb259689.aspx for more information about this coordinate system.

func (*Point) QuadkeyString 

func (p *Point) QuadkeyString(level int) string

QuadkeyString returns the quad key for the given point at the provided level in string form See http://msdn.microsoft.com/en-us/library/bb259689.aspx for more information about this coordinate system.

func (*Point) Scale 

func (p *Point) Scale(factor float64) *Point

Scale each component of the point.

func (*Point) Scan 

func (p *Point) Scan(value interface{}) error

Scan implements the sql.Scanner interface allowing point structs to be passed into rows.Scan(...interface{}) The column must be of type Point and must be fetched in WKB format. Will attempt to parse MySQL's SRID+WKB format if the data is of the right size. If the column is empty (not null) an empty point (0, 0) will be returned.

func (*Point) SetLat 

func (p *Point) SetLat(lat float64) *Point

SetLat sets the latitude/vertical component of the point.

func (*Point) SetLng 

func (p *Point) SetLng(lng float64) *Point

SetLng sets the longitude/horizontal component of the point.

func (*Point) SetX 

func (p *Point) SetX(x float64) *Point

SetX sets the x/horizontal component of the point.

func (*Point) SetY 

func (p *Point) SetY(y float64) *Point

SetY sets the y/vertical component of the point.

func (*Point) SquaredDistanceFrom 

func (p *Point) SquaredDistanceFrom(point *Point) float64

SquaredDistanceFrom returns the squared Euclidean distance between the points. This avoids a sqrt computation.

func (Point) String 

func (p Point) String() string

String returns a string representation of the point. The format is WKT, e.g. POINT(30.5 10.5)

func (*Point) Subtract 

func (p *Point) Subtract(point *Point) *Point

Subtract a point from the given point.

func (Point) ToArray 

func (p Point) ToArray() [2]float64

ToArray casts the data to a [2]float64.

func (Point) ToGeoJSON 

func (p Point) ToGeoJSON() *geojson.Feature

ToGeoJSON creates a new geojson feature with a point geometry.

func (Point) ToWKT 

func (p Point) ToWKT() string

ToWKT returns the point in WKT format, eg. POINT(30.5 10.5)

func (*Point) Transform 

func (p *Point) Transform(projector Projector) *Point

Transform applies a given projection or inverse projection to the current point.

func (*Point) X 

func (p *Point) X() float64

X returns the x/horizontal component of the point.

func (*Point) Y 

func (p *Point) Y() float64

Y returns the y/vertical component of the point.

type PointSet 

type PointSet []Point

A PointSet represents a set of points in the 2D Eucledian or Cartesian plane.

func NewPointSet 

func NewPointSet() *PointSet

NewPointSet simply creates a new point set with points array of the given size.

func NewPointSetFromWKB 

func NewPointSetFromWKB(wkb []byte) *PointSet

NewPointSetFromWKB will take raw WKB and set the data for a new point set. The WKB data must be of type LineString, Polygon or MultiPoint. Will return nil if invalid WKB.

func NewPointSetPreallocate 

func NewPointSetPreallocate(length, capacity int) *PointSet

NewPointSetPreallocate simply creates a new point set with points array of the given size.

func (PointSet) Bound 

func (ps PointSet) Bound() *Bound

Bound returns a bound around the point set. Simply uses rectangular coordinates.

func (PointSet) Centroid 

func (ps PointSet) Centroid() *Point

Centroid returns the average x and y coordinate of the point set. This can also be used for small clusters of lat/lng points.

func (PointSet) Clone 

func (ps PointSet) Clone() *PointSet

Clone returns a new copy of the point set.

func (PointSet) DistanceFrom 

func (ps PointSet) DistanceFrom(point *Point) (float64, int)

DistanceFrom returns the minimum euclidean distance from the point set.

func (PointSet) Equals 

func (ps PointSet) Equals(pointSet *PointSet) bool

Equals compares two point sets. Returns true if lengths are the same and all points are Equal

func (PointSet) First 

func (ps PointSet) First() *Point

First returns the first point in the point set. Will return nil if there are no points in the set.

func (PointSet) GeoCentroid 

func (ps PointSet) GeoCentroid() *Point

GeoCentroid uses a more advanced algorithm to compute the centroid of points on the earth's surface. The points are first projected into 3D space then averaged. The result is projected back onto the sphere. This method is about 6x slower than the Centroid function, which may be adequate for some datasets. NOTE: Points with longitude outside the standard -180:180 range will be remapped to within the range. The result will always have longitude between -180 and 180 degrees.

func (PointSet) GeoDistanceFrom 

func (ps PointSet) GeoDistanceFrom(point *Point) (float64, int)

GeoDistanceFrom returns the minimum geo distance from the point set, along with the index of the point with minimum index.

func (*PointSet) GetAt 

func (ps *PointSet) GetAt(i int) *Point

GetAt returns the pointer to the Point in the page. This function is good for modifying values in place. Returns nil if index is out of range.

func (*PointSet) InsertAt 

func (ps *PointSet) InsertAt(index int, point *Point) *PointSet

InsertAt inserts a Point at i in the point set. Panics if index is out of range.

func (PointSet) Last 

func (ps PointSet) Last() *Point

Last returns the last point in the point set. Will return nil if there are no points in the set.

func (PointSet) Length 

func (ps PointSet) Length() int

Length returns the number of points in the point set.

func (*PointSet) Pop 

func (ps *PointSet) Pop() *Point

Pop removes and returns the last point in the point set

func (*PointSet) Push 

func (ps *PointSet) Push(point *Point) *PointSet

Push appends a point to the end of the point set.

func (*PointSet) RemoveAt 

func (ps *PointSet) RemoveAt(index int) *PointSet

RemoveAt removes a Point at i in the point set. Panics if index is out of range.

func (*PointSet) Scan 

func (ps *PointSet) Scan(value interface{}) error

Scan implements the sql.Scanner interface allowing line structs to be passed into rows.Scan(...interface{}) The column must be of type LineString, Polygon or MultiPoint or an error will be returned. Data must be fetched in WKB format. Will attempt to parse MySQL's SRID+WKB format if obviously no WKB or parsing as WKB fails. If the column is empty (not null) an empty point set will be returned.

func (*PointSet) SetAt 

func (ps *PointSet) SetAt(index int, point *Point) *PointSet

SetAt updates a position at i in the point set

func (*PointSet) SetPoints 

func (ps *PointSet) SetPoints(points []Point) *PointSet

SetPoints sets the points in the point set

func (PointSet) String 

func (ps PointSet) String() string

String returns a string representation of the path. The format is WKT, e.g. MULTIPOINT(30 10,10 30,40 40) For empty paths the result will be 'EMPTY'.

func (PointSet) ToGeoJSON 

func (ps PointSet) ToGeoJSON() *geojson.Feature

ToGeoJSON creates a new geojson feature with a multipoint geometry containing all the points.

func (PointSet) ToWKT 

func (ps PointSet) ToWKT() string

ToWKT returns the point set in WKT format, eg. MULTIPOINT(30 10, 10 30, 40 40)

type Pointer 

type Pointer interface {
	// Point should return the "center" or other canonical point
	// for the object. The caller is expected to Clone
	// the point if changes need to be make.
	Point() *Point
}

A Pointer is the interface for something that has a point.

type Projection 

type Projection struct {
	Project Projector
	Inverse Projector
}

A Projection is a set of projectors to map forward and backwards to the projected space.

func BuildTransverseMercator 

func BuildTransverseMercator(centerLng float64) Projection

BuildTransverseMercator builds a transverse Mercator projection that automatically recenters the longitude around the provided centerLng. Works correctly around the anti-meridian. http://en.wikipedia.org/wiki/Transverse_Mercator_projection

type Projector 

type Projector func(p *Point)

A Projector is a function that converts the given point to a different space.

type Reducer 

type Reducer interface {
	Reduce(*Path) *Path
}

A Reducer reduces a path using any simplification algorithm. It should return a copy of the path, not modify the original.

type Surface 

type Surface struct {
	Width, Height int

	// represents the underlying data, as [x][y]
	// where x in [0:Width] and y in [0:Height]
	Grid [][]float64 // x,y
	// contains filtered or unexported fields
}

Surface is the 2d version of path.

func NewSurface 

func NewSurface(bound *Bound, width, height int) *Surface

NewSurface build and allocates all the memory to create a surface defined by the bound represented by width*height discrete points. Note that surface.Grid[width-1][height-1] will be on the boundary of the bound.

func (*Surface) Bound 

func (s *Surface) Bound() *Bound

Bound returns the same bound given at creation time.

func (*Surface) GradientAt 

func (s *Surface) GradientAt(point *Point) *Point

GradientAt returns the surface gradient at the given point. Bilinearlly interpolates the grid cell to find the gradient.

func (*Surface) MarshalJSON 

func (s *Surface) MarshalJSON() ([]byte, error)

MarshalJSON enables surfaces to be encoded as JSON using the encoding/json package.

func (*Surface) PointAt 

func (s *Surface) PointAt(x, y int) *Point

PointAt returns the point, in the bound, corresponding to this grid coordinate. x in [0, s.Width()-1], y in [0, s.Height()-1]

func (*Surface) UnmarshalJSON 

func (s *Surface) UnmarshalJSON(data []byte) error

UnmarshalJSON enables surfaces to be decoded as JSON using the encoding/json package.

func (*Surface) ValueAt 

func (s *Surface) ValueAt(point *Point) float64

ValueAt returns the bi-linearly interpolated value for the given point. Returns 0 if the point is out of surface bounds TODO: cleanup and optimize this code

func (*Surface) WriteOffFile 

func (s *Surface) WriteOffFile(w io.Writer)

WriteOffFile writes an Object File Format representation of the surface to the writer provided. This is for viewing in MeshLab or something like that. You should close the writer yourself after this function returns. http://segeval.cs.princeton.edu/public/off_format.html

Source Files

View all Source files

Directories

Path Synopsis
helpers
Package quadtree implements a quadtree using rectangular partitions.
 Package quadtree implements a quadtree using rectangular partitions.

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.