Geometry/geography library in Go, DEPRECATED, use ->

Related tags

GIS go.geo
Overview

go.geo (deprecated)

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.

Important, deprecated

This package is deprecated. While bugs will be fixed, new features will not be added, at least by me :). I have written a new geometry library orb that does things much better in both a Geo way and a Go way.

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("[email protected]{[email protected]{[email protected]}[email protected]@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:

Comments
  • feature proposal for projecting points onto lines/paths

    feature proposal for projecting points onto lines/paths

    This implements very basic linear referencing functions on Lines and Paths, e.g.

        p := NewPath()
        p.Push(NewPoint(0, 0))
        p.Push(NewPoint(6, 8))
        p.Push(NewPoint(12, 0))
        p.Project(NewPoint(3, 4)) // 5
        p.ProjectNormalized(NewPoint(3, 4)) // 0.25
    

    Happy to hear any feedback.

    Thanks for this library!

    opened by bdon 10
  • ST_AsBinary return result of 44 length hex

    ST_AsBinary return result of 44 length hex

    By following the example, it returned "\x010100000000000000000024c00000000000003e40" to go.geo causing "go.geo: incorrect geometry" error

    Any idea what's wrong? thanks!

    opened by mwei0210 9
  • compute center of a path

    compute center of a path

    heya, is it currently possible to compute the mid point along a path (a point on the line string which is exactly 50% along the line)?

    I had a look at the APIs and I guess I could use path.Distance() to get the total distance, then I think I would need to walk the points to find the line segment which lies in the center, from there it's a task of interpolating along that segment to find the correct position.

    is this all possible with the existing methods or would it require me to open a PR to add additional methods?

    opened by missinglink 9
  • Marshal to GeoJSON by default

    Marshal to GeoJSON by default

    Rather than having to use ToGeoJSON(), is there a reason not to just have a built in custom MarshalJSON() that defaults to GeoJSON? That would allow embedded geo fields to marshal properly to GeoJSON out of the box.

    opened by derekperkins 9
  • postgresql/postgis: geo.PointSet scan fails for multipoint

    postgresql/postgis: geo.PointSet scan fails for multipoint

    I'm trying to select postgis multipoint to geo.PointSet - and scan fails. Checking code - seems like format actually returned by postgis is different from what's expected by geo.PointSet.

    BTW for geo.Point WKB scan works fine.

    Here is sample code demonstrating issue (manually setup postgresql + postgis server required for test):

    package main
    
    import (
    	"database/sql"
    	"testing"
    
    	_ "github.com/lib/pq"
    	geo "github.com/paulmach/go.geo"
    	"github.com/stretchr/testify/require"
    )
    
    func TestMultipointScan(t *testing.T) {
    	/*
    		select version() union select postgis_full_version();
    		                                                                               version
    		----------------------------------------------------------------------------------------------------------------------------------------------------------------------
    		 POSTGIS="2.3.2 r15302" GEOS="3.4.2-CAPI-1.8.2 r3921" PROJ="Rel. 4.8.0, 6 March 2012" GDAL="GDAL 1.10.1, released 2013/08/26" LIBXML="2.9.1" LIBJSON="0.11.99" RASTER
    		 PostgreSQL 9.6.2 on x86_64-pc-linux-gnu, compiled by gcc (Debian 4.9.2-10) 4.9.2, 64-bit
    	*/
    	db, err := sql.Open("postgres", "user=x password=x dbname=x sslmode=disable")
    	require.NoError(t, err)
    
    	const query = `
    		SELECT ST_AsBinary(ST_Collect(ST_GeomFromText('POINT(1 2)'), ST_GeomFromText('POINT(1 2)')))
    	`
    	var ps geo.PointSet
    	err = db.QueryRow(query).Scan(&ps)
    
    	require.NoError(t, err)
    
    	/*
    		go test -run TestMultipointScan -v
    		=== RUN   TestMultipointScan
    		--- FAIL: TestMultipointScan (0.04s)
    			Error Trace:	sample_test.go:23
    			Error:		Received unexpected error:
    					sql: Scan error on column index 0: go.geo: invalid WKB data
    	*/
    }
    
    opened by sbinq 5
  • MySQL scanning POLYGON WKB Always results in EMPTY

    MySQL scanning POLYGON WKB Always results in EMPTY

    For example I used this and scanned it to a geo.PointSet

    SET @g = 'POLYGON((50.866753 5.686455, 50.859819 5.708942, 50.851475 5.722675, 50.841611 5.720615, 50.834023 5.708427, 50.840744 5.689373, 50.858735 5.673923, 50.866753 5.686455))';
    SELECT ST_AsBinary(PolyFromText(@g));
    

    var p *geo.PointSet
    row.Scan(&p)
    
    //  p == EMPTY
    

    It's very likely that I'm way off on this. What am I doing wrong?

    opened by mfzl 5
  • centroid calc

    centroid calc

    hey @paulmach I've been playing with an alternate irregular polygon centroid algorithm which I borrowed from https://github.com/manuelbieh/Geolib/blob/master/src/geolib.js#L404

    in theory it should provide a better 'center of gravity' calc than than the existing PointSet.Centroid() algo as it converts the coords to a spherical coordinate space before averaging the values.

    what are your thoughts? is this something you'd be interested in merging at some point?

    see: http://geojson.io/#id=gist:anonymous/ecd1ce4af92368aa4aea&map=3/-72.39/167.70

    package main
    
    import "fmt"
    import "math"
    import "github.com/paulmach/go.geo"
    
    func main() {
      // berlin := geo.NewPoint(13.408056,52.518611)
      // moscow := geo.NewPoint(37.617778,55.751667)
      // points := geo.PointSet{}
      // points.Push(berlin).Push(moscow)
    
      // rough new zealand polygon
      // ref: http://geojson.io/#id=gist:anonymous/adc4993b4b85f55ea9ae
      // points := geo.PointSet{}
      // points.Push(geo.NewPoint(172.1298828125,-33.97980872872456))
      // points.Push(geo.NewPoint(172.1298828125,-37.30027528134431))
      // points.Push(geo.NewPoint(165.8974609375,-38.54816542304658))
      // points.Push(geo.NewPoint(168.1728515625,-46.10370875598026))
      // points.Push(geo.NewPoint(179.7802734375,-47.8721439688873))
      // // points.Push(geo.NewPoint(-188.1298828125,-33.97980872872456))
    
      // antarctica bbox
      points := geo.PointSet{}
      points.Push(geo.NewPoint(148.7109375,-84.83422451455142))
      points.Push(geo.NewPoint(148.7109375,-76.51681887717322))
      points.Push(geo.NewPoint(186.6796875,-76.51681887717322))
      points.Push(geo.NewPoint(186.6796875,-84.83422451455142))
    
      fmt.Println(points)
      fmt.Println(points.Centroid())
      fmt.Println(getCentroid(points))
    }
    
    func getCentroid(ps geo.PointSet) *geo.Point {
    
      X := 0.0
      Y := 0.0
      Z := 0.0
    
      var toRad = math.Pi / 180
      var fromRad = 180 / math.Pi
    
      for _, point := range ps {
    
        var lon = point[0] * toRad
        var lat = point[1] * toRad
    
        X += math.Cos(lat) * math.Cos(lon)
        Y += math.Cos(lat) * math.Sin(lon)
        Z += math.Sin(lat)
      }
    
      numPoints := float64(len(ps))
      X = X / numPoints
      Y = Y / numPoints
      Z = Z / numPoints
    
      var lon = math.Atan2(Y, X)
      var hyp = math.Sqrt(X * X + Y * Y)
      var lat = math.Atan2(Z, hyp)
    
      var centroid = geo.NewPoint(lon * fromRad, lat * fromRad)
    
      return centroid;
    }
    
    opened by missinglink 5
  • Adding identifer column to Point object for quad tree investigation

    Adding identifer column to Point object for quad tree investigation

    Hi, not an issue so much, as something I'm struggling with adapting.

    I need the ability to have a number associated with a geo point, in order to reference back to what it relates to. I've customised the point type to have length of 3 instead of 2, with the 3rd float been the ID, so the idea was, when I ran a nearest command against the quad tree of points, I'd be able to find it's owner.

    The creating of the point works, and the existing tests pass. But soon as the point is added to the quad tree, it appears to lose it's 3rd value, returning X and Y as expected, but the 3rd number is always 0.

    Is there something I'm missing in the quad tree section, that is removing this 3rd column. Any help or advice on the best way to approach this would be much appreciated!

    opened by jvalentine 4
  • A quadtree of pointers

    A quadtree of pointers

    This PR implements a quadtree for use with objects that implement the geo.Pointer interface:

    type Pointer interface {
        Point() *Point
    }
    

    It supports Find which locates the nearest pointer to given point and InBound which finds all the points in the bounds. I think performance is really good:

    BenchmarkInsert-4                2000000           749 ns/op          72 B/op          1 allocs/op
    BenchmarkInsert1000-4            2000000           668 ns/op          72 B/op          1 allocs/op
    BenchmarkFromPointer1000-4         10000        197301 ns/op      100003 B/op          8 allocs/op
    BenchmarkRandomFind1000-4        2000000           907 ns/op         112 B/op          5 allocs/op
    BenchmarkRandomInBound1000-4      300000          4928 ns/op        1828 B/op         10 allocs/op
    BenchmarkRandomInBound1000Buf-4   500000          3245 ns/op          80 B/op          4 allocs/op
    

    This is based on a tree with 1000 random points. So it'll be different in practice, but I think it's pretty good.

    Still left to do:

    • [x] Think about TODO that deals with how to handle close/duplicate points.
    • [x] ~~Remove point~~ leave for v2
    • [x] Write a README with some examples

    If you have a chance. @mlerner please review.

    opened by paulmach 4
  • Support MultiPolygon type when reading the WKB data from db

    Support MultiPolygon type when reading the WKB data from db

    I'd like to be able to scan data from the multipolygon column from the PostGIS database into Go app.

    I was hoping I could simply define a struct where one of the fields is of type MultiPolygon:

    import(geo "github.com/paulmach/go.geo")
    ...
    type Area struct {
    	ID        uuid.UUID        `gorm:"column:id" json:"id"`
    	Shape     *geo.MultiPolygon `gorm:"column:shape" json:"shape"`
    

    However, of course such a type is not yet defined.

    Is there a way to actually read the MultiPolygon data from PostGIS?

    Also it seems that we have to run the ST_AsBinary function when fetching data from the database. Failing to do so results in the sql: Scan error on column index 3: go.geo: invalid WKB data error.

    Couldn't we always apply the ST_AsBinary function? eg. when defining the struct? I'd say that the typical scenario is that the data is actually saved as WKB binary and the ST_AsBinary function simply changes:

    shape | 01060...E614340
    

    to

    st_asbinary | \x01060...e614340
    
    opened by januszm 3
  • QuadKey tile

    QuadKey tile

    Currently I'm doing something like:

    quadkey := geo.NewPoint(v.Lon, v.Lat).QuadkeyString(quadKeyLevel)
    

    With v.Lon and v.Lat not necessarily being on a tile boundary. I'm not sure, based on the results, whether QuadKeyString will represent a tile, or if it'll be different based on different points with a tile at the same level.

    opened by tmcw 3
  • normalize cartesian coordinate range

    normalize cartesian coordinate range

    I have this javascript code which normalizes geographic coordinates to within the ranges of lat +-90 and lon +-180 (it unwinds multiple rotations around the globe).

    This function is quite nice as it avoids floating point precision errors which can occur when using other methods.

    Would you be interested in me porting the code to go.geo? If so what would you call the method? it's specific to geographic coordinates.

    Maybe this could close https://github.com/paulmach/go.geo/pull/41 as it appears to be doing something similar?

    Could be named something like point.NormalizeGeographicCoordinates()

    opened by missinglink 2
Releases(v0.1)
Efficient 2D geometry library for Go.

geometry An efficient 2D geometry library for Go. Features Point, Rect, Line, and Polygon geometry types Operations such as Intersects, Contains, and

Josh Baker 30 Aug 30, 2022
Package geom implements efficient geometry types for geospatial applications.

go-geom Package geom implements efficient geometry types for geospatial applications. Key features OpenGeo Consortium-style geometries. Support for 2D

Tom Payne 641 Nov 29, 2022
Types and utilities for working with 2d geometry in Golang

orb Package orb defines a set of types for working with 2d geo and planar/projected geometric data in Golang. There are a set of sub-packages that use

Paul Mach 604 Dec 4, 2022
Go bindings for the Cartographic Projections Library PROJ.4

The Go package proj provides a limited interface to the Cartographic Projections Library PROJ. For PROJ version 5 and beyond, see also: https://github

Peter Kleiweg 42 Nov 10, 2022
General purpose library for reading, writing and working with OpenStreetMap data

osm This package is a general purpose library for reading, writing and working with OpenStreetMap data in Go (golang). It has the ability to read OSM

Paul Mach 241 Nov 25, 2022
Go (golang) wrapper for GDAL, the Geospatial Data Abstraction Library

------------- About ------------- The gdal.go package provides a go wrapper for GDAL, the Geospatial Data Abstraction Library. More information about

null 232 Nov 12, 2022
geoserver is a Go library for manipulating a GeoServer instance via the GeoServer REST API.

Geoserver geoserver Is a Go Package For Manipulating a GeoServer Instance via the GeoServer REST API. How to install: go get -v gopkg.in/hishamkaram/g

Hisham waleed karam 76 Sep 26, 2022
A library provides spatial data and geometric algorithms

Geoos Our organization spatial-go is officially established! The first open source project Geoos(Using Golang) provides spatial data and geometric alg

spatial-go 548 Nov 25, 2022
S2 geometry library in Go

Overview S2 is a library for spherical geometry that aims to have the same robustness, flexibility, and performance as the best planar geometry librar

Go 1.5k Dec 1, 2022
S2 geometry library in Go

Overview S2 is a library for spherical geometry that aims to have the same robustness, flexibility, and performance as the best planar geometry librar

Go 1.5k Nov 23, 2022
Efficient 2D geometry library for Go.

geometry An efficient 2D geometry library for Go. Features Point, Rect, Line, and Polygon geometry types Operations such as Intersects, Contains, and

Josh Baker 30 Aug 30, 2022
Package geom implements efficient geometry types for geospatial applications.

go-geom Package geom implements efficient geometry types for geospatial applications. Key features OpenGeo Consortium-style geometries. Support for 2D

Tom Payne 641 Nov 29, 2022
Types and utilities for working with 2d geometry in Golang

orb Package orb defines a set of types for working with 2d geo and planar/projected geometric data in Golang. There are a set of sub-packages that use

Paul Mach 604 Dec 4, 2022
Dorival Pedroso 1.7k Nov 24, 2022
Types and utilities for working with 2d geometry in Golang

orb Package orb defines a set of types for working with 2d geo and planar/projected geometric data in Golang. There are a set of sub-packages that use

Paul Mach 604 Dec 7, 2022
Transitland routes geometry generator from gtfs shapes

Transitland route geometry generator Generate your transitland route shapes from gtfs trips - WIP This project aims to generate transitland gtfs route

phoops s.r.l. 3 Dec 8, 2021
*DEPRECATED* Please use https://gopkg.in/redsync.v1 (https://github.com/go-redsync/redsync)

Redsync.go This package is being replaced with https://gopkg.in/redsync.v1. I will continue to maintain this package for a while so that its users do

Mahmud Ridwan 302 Nov 20, 2022
Go Library [DEPRECATED]

Tideland Go Library Description The Tideland Go Library contains a larger set of useful Google Go packages for different purposes. ATTENTION: The cell

Tideland 194 Nov 15, 2022
Go Library [DEPRECATED]

Tideland Go Library Description The Tideland Go Library contains a larger set of useful Google Go packages for different purposes. ATTENTION: The cell

Tideland 194 Nov 15, 2022
Go Library [DEPRECATED]

Tideland Go Library Description The Tideland Go Library contains a larger set of useful Google Go packages for different purposes. ATTENTION: The cell

Tideland 194 Nov 15, 2022