geoquad

README

geoquad: Quadtree for geographic coordinates

This package implements a quadtree using the Google Maps tiling logic for geographic coordinates (lat/lon) and nearest neighbor search.

See: https://www.maptiler.com/google-maps-coordinates-tile-bounds-projection

Documentation

Overview

Package geoquad provides a simple way to generate a quadtree for a given set of lat/lon coordinates. The quadtree is laid out like described in: https://www.maptiler.com/google-maps-coordinates-tile-bounds-projection/ to represent a tileset that is used by Google Maps, OpenStreetMap, etc. This will allow us to quickly find all coordinates within a given tile, or all coordinates within a given bounding box, as well as the closest coordinate to a given coordinate.

Index

• Constants
• type Point
• type QuadTree
  • func NewQuadTree(points []Point) *QuadTree
  • func (qt *QuadTree) ExportToPNG(filename string) error
  • func (qt *QuadTree) FindLeafTile(point Point) *QuadTree
  • func (qt *QuadTree) FindNearestNeighbor(point Point) (Point, bool)
  • func (qt *QuadTree) FindPoint(point Point) *QuadTree
  • func (qt *QuadTree) FindPointsInRect(rect Rect) []Point
  • func (qt *QuadTree) FindPointsInTile(x, y, zoom int) []Point
  • func (qt *QuadTree) Verify()
• type Rect
• type TileCoordinates
  • func (t TileCoordinates) String() string

Constants

const (
	MinLongitude float64 = -180.0
	MaxLongitude float64 = 180.0
	MinLatitude  float64 = -90.0
	MaxLatitude  float64 = 90.0
)

min and max latitude and longitude.

Types

type Point

type Point struct {
	Lat  float64
	Lon  float64
	Data interface{}
}

Point represents a point (latitude, longitude) in 2D space.

type QuadTree

type QuadTree struct {
	TileCoordinates // The coordinates and zoom of the tile this quadtree represents.
	Points          []Point
	Bounds          Rect // The bounds of the tile this quadtree represents.
	// The four child quadtrees.
	// The first two are the top left and top right quadtrees.
	// The second two are the bottom left and bottom right quadtrees.
	Children [4]*QuadTree
	Parent   *QuadTree
}

QuadTree represents a quadtree.

func NewQuadTree

func NewQuadTree(points []Point) *QuadTree

NewQuadTree creates a new quadtree for the given points.

func (*QuadTree) ExportToPNG

func (qt *QuadTree) ExportToPNG(filename string) error

ExportToPNG exports the quadtree to a PNG image.

func (*QuadTree) FindLeafTile

func (qt *QuadTree) FindLeafTile(point Point) *QuadTree

FindLeafTile returns the leaf tile that contains the given point.

func (*QuadTree) FindNearestNeighbor

func (qt *QuadTree) FindNearestNeighbor(point Point) (Point, bool)

FindNearestNeighbor returns the closest point to the given point within the quadtree.

func (*QuadTree) FindPoint

func (qt *QuadTree) FindPoint(point Point) *QuadTree

FindPoint returns the QuadTree that contains the given point.

func (*QuadTree) FindPointsInRect

func (qt *QuadTree) FindPointsInRect(rect Rect) []Point

FindPointsInRect returns all points in the given rectangle.

func (*QuadTree) FindPointsInTile

func (qt *QuadTree) FindPointsInTile(x, y, zoom int) []Point

FindPointsInTile returns all points in the given tile.

func (*QuadTree) Verify

func (qt *QuadTree) Verify()

type Rect

type Rect struct {
	MinLat float64
	MaxLat float64
	MinLon float64
	MaxLon float64
}

Rect represents a rectangle in 2D space.

type TileCoordinates

type TileCoordinates struct {
	X, Y, Zoom int
}

func (TileCoordinates) String

func (t TileCoordinates) String() string