pinpoint

package module
v0.3.1 Latest Latest
Warning

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

 Go to latest Published: Dec 16, 2022 License: MIT Imports: 13 Imported by: 0

README

Pinpoint: a fast location finder for Go.

Quick Start

Go
// Use about 150MB memory for init, and 60MB after GC.
package main

import (
	"fmt"

	"github.com/deslittle/pinpoint"
)

func main() {
	finder, err := pinpoint.NewExampleCombinedFinder()
	if err != nil {
		panic(err)
	}
	fmt.Println(finder.GetLocationName(116.6387, 40.0786))
}

If you need 100% accurate query result, use below to got a finder:

// Use about 900MB memory for init, and 660MB after GC.
package main

import (
	"fmt"

	"github.com/deslittle/pinpoint"
	usstates "github.com/deslittle/pinpoint-us-states"
	"github.com/deslittle/pinpoint/pb"
	"google.golang.org/protobuf/proto"
)

func main() {
	input := &pb.Locations{}

	// Full data, about 83.5MB
	dataFile := usstates.FullData

	if err := proto.Unmarshal(dataFile, input); err != nil {
		panic(err)
	}
	finder, _ := pinpoint.NewFinderFromPB(input)
	fmt.Println(finder.GetLocationName(116.6386, 40.0786))
}
CLI Tool
go install github.com/deslittle/pinpoint/cmd/pinpoint@latest
pinpoint -lng 116.3883 -lat 39.9289

Data

Preprocessed probuf data can get from https://github.com/deslittle/pinpoint-us-states which has Go's embed support. Those files are Protocol Buffers messages for more efficiency binary distribution like Python wheels, you can view the pb/locinfo.proto or it's [HTML format docs][loc_html] for the internal format info.

pinpoint's data pipeline can be drew as:

graph TD
    Shp[Shapefile from US Census Bureau]
    Geobuf[Geobuf]
    GeoJSON[GeoJSON]
    Full[Full: Probuf based data]
    Lite[Lite: smaller of Full data]
    Compressed[Compressed: Lite compressed via Polyline]
    Preindex[Tile based data]

    Finder[Finder: Polygon Based Finder]
    FuzzyFinder[FuzzyFinder: Tile based Finder]
    CombinedFinder[CombinedFinder: combine FuzzyFinder and Compressed Finder]

    Shp --> |mapbox/shp2geobuf|Geobuf
    Geobuf --> |mapbox/geobuf2json|GeoJSON
    GeoJSON --> |cmd/geojson2locpb|Full
    Full --> |cmd/reducelocpb|Lite
    Lite --> |cmd/compresslocpb|Compressed
    Lite --> |cmd/preindexlocpb|Preindex

    Full --> |pinpoint.NewFinderFromPB|Finder
    Lite --> |pinpoint.NewFinderFromPB|Finder
    Compressed --> |pinpoint.NewFinderFromCompressed|Finder --> |CombinedFinder
    Preindex --> |pinpoint.NewFuzzyFinderFromPB|FuzzyFinder --> |CombinedFinder

The full data(~80MB) could work anywhere but requires more memory usage.

The lite data(~10MB) doesn't work well in some edge places.

You can see points that results diff in this page.

If a little longer init time is acceptable, the compressed data(~5MB) which come from lite data will be more friendly for binary distribution.

The preindex data(~1.78MB) are many tiles. It's used inside the CombinedFinder, which built on FuzzyFinder, to reduce raycasting algorithm execution times.

Performance

package pinpoint is designed for high performance geo queries related services like weather forecast API. And most queries could return in very limited time, averagely like 2000 nanoseconds.

Here is what have been done for performance improvements:

  1. Use preindexes to handle most queries, basically about 1000 nanoseconds
  2. Use RTree to filter candidate polygons instead of iter all polygons to reduce Ray Casting algorithm execution times
  3. Use a fine tuned Ray Casting algorithm package https://github.com/tidwall/geojson to check if polygon contain point

That's all. There is no black magics inside package pinpoint.

Benchmark run version https://github.com/deslittle/pinpoint/releases/tag/v0.10.0

goos: darwin
goarch: amd64
pkg: github.com/deslittle/pinpoint
cpu: Intel(R) Core(TM) i9-9880H CPU @ 2.30GHz
BenchmarkDefaultFinder_GetLocationName_Random_WorldCities-16    	  443942	      2583 ns/op
BenchmarkFuzzyFinder_GetLocationName_Random_WorldCities-16      	 1580524	       769.3 ns/op
BenchmarkGetLocationName-16                                     	  184234	      6983 ns/op
BenchmarkGetLocationNameAtEdge-16                               	  145342	      8779 ns/op
BenchmarkGetLocationName_Random_WorldCities-16                  	  130540	      9247 ns/op
BenchmarkFullFinder_GetLocationName-16                          	  164649	      7256 ns/op
BenchmarkFullFinder_GetLocationNameAtEdge-16                    	  136508	      9382 ns/op
BenchmarkFullFinder_GetLocationName_Random_WorldCities-16       	   91137	     12385 ns/op
PASS
ok  	github.com/deslittle/pinpoint	19.073s

Thanks

Documentation

Index

Examples

Constants

This section is empty.

Variables

View Source 
var ErrNoLocationFound = errors.New("pinpoint: no location found")

Functions

func SetDropPBLoc 

func SetDropPBLoc(opt *Option)

SetDropPBLoc will make Finder not save github.com/deslittle/pinpoint/pb.Location in memory

Types

type ExampleCombinedFinder added in v0.3.0 

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

combinedFinder is an example implimentation using the `pinpoint-us-states` repo which combines both FuzzyFinder and Finder.

It's designed for performance first and allow some not so correct return at some area.

func NewExampleCombinedFinder added in v0.3.0 

func NewExampleCombinedFinder() (*ExampleCombinedFinder, error)

func (*ExampleCombinedFinder) GetLocationName added in v0.3.0 

func (f *ExampleCombinedFinder) GetLocationName(lng float64, lat float64) string

func (*ExampleCombinedFinder) GetLocationNames added in v0.3.0 

func (f *ExampleCombinedFinder) GetLocationNames(lng float64, lat float64) ([]string, error)

func (*ExampleCombinedFinder) LocationNames added in v0.3.0 

func (f *ExampleCombinedFinder) LocationNames() []string

type Finder 

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

Finder is based on point-in-polygon search algo.

Memeory will use about 100MB if lite data and 1G if full data. Performance is very stable and very accuate.

func NewFinderFromCompressed 

func NewFinderFromCompressed(input *pb.CompressedLocations, opts ...OptionFunc) (*Finder, error)

func NewFinderFromPB 

func NewFinderFromPB(input *pb.Locations, opts ...OptionFunc) (*Finder, error)

func NewFinderFromRawJSON 

func NewFinderFromRawJSON(input *convert.BoundaryFile, opts ...OptionFunc) (*Finder, error)

func (*Finder) GetLocation 

func (f *Finder) GetLocation(lng float64, lat float64) (*pb.Location, error)

func (*Finder) GetLocationName 

func (f *Finder) GetLocationName(lng float64, lat float64) string

GetLocationName will use alphabet order and return first matched result.

Example 
package main

import (
	"fmt"

	pinpoint "github.com/deslittle/pinpoint"
	usstates "github.com/deslittle/pinpoint-us-states"
	"github.com/deslittle/pinpoint/pb"
	"google.golang.org/protobuf/proto"
)

func main() {
	input := &pb.Locations{}

	// Lite data, about 16.7MB
	//dataFile := usstates.LiteData

	// Full data, about 83.5MB
	dataFile := usstates.FullData

	if err := proto.Unmarshal(dataFile, input); err != nil {
		panic(err)
	}
	finder, _ := pinpoint.NewFinderFromPB(input)

	// Need to use a point not so close to New York border for Fuzzy Search
	loc, err := finder.GetLocation(-74.03440821618342, 40.71579135708155)
	fmt.Printf("%v %v\n", loc.GetName(), err)
}

Output:

34 <nil>

func (*Finder) GetLocationNames 

func (f *Finder) GetLocationNames(lng float64, lat float64) ([]string, error)

func (*Finder) GetLocationShapeByName 

func (f *Finder) GetLocationShapeByName(name string) (*pb.Location, error)
Example 
package main

import (
	"fmt"

	pinpoint "github.com/deslittle/pinpoint"
	usstates "github.com/deslittle/pinpoint-us-states"
	"github.com/deslittle/pinpoint/pb"
	"google.golang.org/protobuf/proto"
)

func main() {
	input := &pb.Locations{}

	// Lite data, about 16.7MB
	dataFile := usstates.FullData

	if err := proto.Unmarshal(dataFile, input); err != nil {
		panic(err)
	}
	finder, _ := pinpoint.NewFinderFromPB(input)
	pbloc, err := finder.GetLocationShapeByName("34")
	fmt.Printf("%v %v\n", pbloc.GetName(), err)
}

Output:

34 <nil>

func (*Finder) LocationNames 

func (f *Finder) LocationNames() []string

type FuzzyFinder 

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

FuzzyFinder use a tile map to store location name. Data are made by github.com/deslittle/pinpoint/cmd/preindexlocpb which powerd by github.com/deslittle/pinpoint/preindex.PreIndexLocations.

func NewFuzzyFinderFromPB 

func NewFuzzyFinderFromPB(input *pb.PreindexLocations) (*FuzzyFinder, error)

func (*FuzzyFinder) GetLocationName 

func (f *FuzzyFinder) GetLocationName(lng float64, lat float64) string
Example 
package main

import (
	"fmt"

	pinpoint "github.com/deslittle/pinpoint"
	usstates "github.com/deslittle/pinpoint-us-states"
	"github.com/deslittle/pinpoint/pb"
	"google.golang.org/protobuf/proto"
)

func main() {
	input := &pb.PreindexLocations{}
	if err := proto.Unmarshal(usstates.PreindexData, input); err != nil {
		panic(err)
	}
	finder, _ := pinpoint.NewFuzzyFinderFromPB(input)

	loc := finder.GetLocationName(-74.666645, 40.736032)
	fmt.Println(loc)
}

Output:

34

func (*FuzzyFinder) GetLocationNames 

func (f *FuzzyFinder) GetLocationNames(lng float64, lat float64) ([]string, error)

type Option 

type Option struct {
	DropPBLoc bool
}

type OptionFunc 

type OptionFunc = func(opt *Option)

Source Files

View all Source files

Directories

Path Synopsis
cmd
combinegeojson
CLI tool to combine multiple geojson files into one.
 CLI tool to combine multiple geojson files into one.
comparelocpb
compresslocpb
CLI tool to reduce polygon filesize
 CLI tool to reduce polygon filesize
filtergeojson
CLI tool to combine multiple geojson files into one.
 CLI tool to combine multiple geojson files into one.
geojson2locpb
CLI tool to convert GeoJSON based Location boundary to pinpoints's Probuf format.
 CLI tool to convert GeoJSON based Location boundary to pinpoints's Probuf format.
namegeojson
CLI tool to convert GeoJSON based Location boundary to pinpoints's Probuf format.
 CLI tool to convert GeoJSON based Location boundary to pinpoints's Probuf format.
pinpoint
pinpoint-cli tool for local query.
 pinpoint-cli tool for local query.
preindexlocpb
CLI tool to preindex location shape.
 CLI tool to preindex location shape.
reducelocpb
CLI tool to reduce polygon filesize
 CLI tool to reduce polygon filesize
Package preindex
 Package preindex
Package reduce could reduce Polygon size both polygon lines and float precise.
 Package reduce could reduce Polygon size both polygon lines and float precise.

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.