quadtree

package
v0.0.0-...-a949315 Latest Latest
Warning

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

 Go to latest Published: Mar 17, 2023 License: Apache-2.0 Imports: 5 Imported by: 0

Documentation

Index

Constants

View Source 
const MaxZoom = 29

Variables

This section is empty.

Functions

This section is empty.

Types

type GroupDetails 

type GroupDetails struct {
	GroupID uint32

	// This tile is used for various tile types
	// use as bitmask. Assumption that will not have more than 16 tile types.
	Type TileType

	// This tile and all children/grandchildren/second cousins once removed etc... are present.
	// Full is tiletype specific.
	Full bool
}

GroupDetails has bare information about the "group" that created the tile this is associated with. GroupID is the ID of the data feed (simply has to be unique) Type is the tiletype assocated with this group. Full determines if this tile+groupID+type is "full"... if true then all child tiles are also full/exist. TODO(kpfaulkner) investigate if this can simply be changed to a uint64.

type QuadKey 

type QuadKey uint64

QuadKey is a key representing a Slippy tile.

func GenerateQuadKeyIndexFromSlippy 

func GenerateQuadKeyIndexFromSlippy(x uint32, y uint32, zoomLevel byte) QuadKey

GenerateQuadKeyIndexFromSlippy generates the quadkey index from slippy coords

func (QuadKey) ChildAtPos 

func (q QuadKey) ChildAtPos(pos int) (QuadKey, error)

ChildAtPos where pos is 0-3 based off https://learn.microsoft.com/en-us/bingmaps/articles/bing-maps-tile-system?redirectedfrom=MSDN

func (QuadKey) Children 

func (q QuadKey) Children() []QuadKey

Children get all the quadkeys for the 4 children of the passed quadkey

func (QuadKey) Envelope 

func (q QuadKey) Envelope() (geom.Envelope, error)

Envelope returns the lat/lon bounds of the slippy tile represented by a QuadKey.

func (QuadKey) GetMinMaxEquivForZoomLevel 

func (q QuadKey) GetMinMaxEquivForZoomLevel(zoom byte) (QuadKey, QuadKey, error)

GetMinMaxEquivForZoomLevel given a quadkey and a desired zoom level, keep converting quadkey to desired zoom level and get min/max quadkeys (top left, bottom right) Practically this will only be valid if the tile associated with the quadKey is "full", but it's up the caller to check this. This name utterly sucks, please suggest a better one.

func (QuadKey) IsAncestorOf 

func (q QuadKey) IsAncestorOf(desc QuadKey) bool

IsAncestorOf checks whether a QuadKey is an ancestor of (or equal to) another QuadKey.

func (QuadKey) Parent 

func (q QuadKey) Parent() (QuadKey, error)

Parent get parents quadkey for passed quadkey

func (QuadKey) Range 

func (q QuadKey) Range() (r QuadKeyRange)

Range returns the range of QuadKeys that contains q and all of its descendants.

func (QuadKey) SingleRange 

func (q QuadKey) SingleRange() QuadKeyRange

SingleRange returns a range that only contains this QuadKey.

func (QuadKey) SlippyCoords 

func (q QuadKey) SlippyCoords() (uint32, uint32, byte)

SlippyCoords generates the slippy coords from quadkey index

func (QuadKey) Zoom 

func (q QuadKey) Zoom() byte

Zoom get the zoom level of the quadkey Zoom is stored in lower 5 bits of quadkey

type QuadKeyRange 

type QuadKeyRange struct {
	// Start and endpoints of the range, both inclusive.
	// Note: Start and End aren't, in general, valid QuadKeys themselves.
	Start, End uint64
}

QuadKeyRange is a range containing QuadKeys.

func (QuadKeyRange) Contains 

func (r QuadKeyRange) Contains(q QuadKey) bool

type QuadMap 

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

QuadMap is a quadtree in disguise...

func NewQuadMap 

func NewQuadMap(initialCapacity int) *QuadMap

NewQuadMap create a new quadmap Should provide a large initialCapacity when dealing with large quadtree structures

func (*QuadMap) AddTile 

func (qm *QuadMap) AddTile(t *Tile) error

AddTile adds a pre-generated tile (which has its quadkey already)

func (*QuadMap) CreateTileAtSlippyCoords 

func (qm *QuadMap) CreateTileAtSlippyCoords(x uint32, y uint32, z uint32, groupID uint32, tileType TileType) (*Tile, error)

CreateTileAtSlippyCoords creates a tile to the quadmap at slippy coords If tile already exists at coords, then tile is modified with groupID/tiletype information Tile is returned

func (*QuadMap) GetChildInPos 

func (qm *QuadMap) GetChildInPos(t *Tile, pos int) (*Tile, error)

GetChildInPos returns child tile of passed in tile t which is in position pos pos is a number between 0 and 3, where 0 is top left, 1 is top right, 2 is bottom left and 3 is bottom right

func (*QuadMap) GetExactTileForQuadKey 

func (qm *QuadMap) GetExactTileForQuadKey(quadKey QuadKey) (*Tile, error)

GetExactTileForQuadKey returns tile for quadkey match. Does NOT traverse up the ancestry

func (*QuadMap) GetExactTileForSlippy 

func (qm *QuadMap) GetExactTileForSlippy(x uint32, y uint32, z byte) (*Tile, error)

GetExactTileForSlippy returns tile for slippy co-ord match. Does NOT traverse up the ancestry

func (*QuadMap) GetParentTile 

func (qm *QuadMap) GetParentTile(t *Tile) (*Tile, error)

GetParentTile returns parent tile of passed in tile t

func (*QuadMap) GetSlippyBoundsForGroupIDTileTypeAndZoom 

func (qm *QuadMap) GetSlippyBoundsForGroupIDTileTypeAndZoom(groupID uint32, tileType TileType, zoom byte) (uint32, uint32, uint32, uint32, error)

GetSlippyBoundsForGroupIDTileTypeAndZoom returns the minx,miny,maxx,maxy slippy coords for a given zoom level extracted from the quadmap. Brute forcing it for now.

func (*QuadMap) GetTileDetailsForQuadkey 

func (qm *QuadMap) GetTileDetailsForQuadkey(quadKey QuadKey, tileDetails *TileDetails, isTargetLevel bool) error

GetTileDetailsForQuadkey returns details for the tile for quadkey This may involve multiple groups (ie multiple data sets loaded into single quadmap) but also different tiletypes as well.

func (*QuadMap) GetTileDetailsForSlippyCoords 

func (qm *QuadMap) GetTileDetailsForSlippyCoords(x uint32, y uint32, z byte, tileDetails *TileDetails) error

GetTileDetailsForSlippyCoords returns details for the tile at slippy coord x,y,z. This may involve multiple groups (ie multiple data sets loaded into single quadmap) but also different tiletypes as well.

func (*QuadMap) GetTilesForTypeAndZoom 

func (qm *QuadMap) GetTilesForTypeAndZoom(tt TileType, zoom byte) []*Tile

GetTilesForTypeAndZoom gets tiles for a given tile type and zoom level

func (*QuadMap) HaveTileForGroupIDAndTileType 

func (qm *QuadMap) HaveTileForGroupIDAndTileType(quadKey QuadKey, groupID uint32, tileType TileType, actualTile bool) (bool, error)

HaveTileForGroupIDAndTileType returns bool indicating if we have details for a tile at the provided quadKey provided but also matching the tiletype and groupID. It will return true if tile requested is found OR an ancestor that is FULL The process is:

  • if quadkey exists, groupID exists and tiletype exists, return true

  • else

  • get parent quadkey

  • if parent quadkey exists and is full, return parent details

  • loop until no parent.

    What happens if we hit a parent that is NOT full? No tile therefore return error? Returns tile (actual or parent), bool indicating if actual (true == actual, false == ancestor) and error

func (*QuadMap) HaveTileForSlippyGroupIDAndTileType 

func (qm *QuadMap) HaveTileForSlippyGroupIDAndTileType(x uint32, y uint32, z byte, groupID uint32, tileType TileType) (bool, error)

HaveTileForSlippyGroupIDAndTileType returns bool indicating if we have details for a tile at the provided slippy co-ords but also matching the tiletype and groupID.

func (*QuadMap) NumberOfTiles 

func (qm *QuadMap) NumberOfTiles() int

NumberOfTiles returns number of tiles in quadmap

func (*QuadMap) NumberOfTilesForZoom 

func (qm *QuadMap) NumberOfTilesForZoom(zoom byte) int

NumberOfTilesForZoom returns number of tiles for a given zoom level. It will NOT include parents that may be used when querying (and the parents are marked as full) Given we don't keep track of zoom levels separately, we need to traverse the entire quadmap. If this is a common operation we'll need to track/cache this information somewhere. Although for the limited test cases so far it's pretty much instant

type Tile 

type Tile struct {
	// stupid to keep it in here?
	// Will also store the zoom level in the key.
	QuadKey QuadKey
	// contains filtered or unexported fields
}

Tile is a node within a quadtree. Although a Tile instance will only be in the quadmap once (for a given quadkey) it may be the case that the same tile+quadkey is used by multiple "groups" and also for multiple tiletypes within a group.

For example, if we populate the quadmap with one set of data (called group1) and group1 in turn has information about tiletype1 and tiletype2, this means that we'll need to track at a per quadkey level if the files are full (and for which tiletypes). Once the caller then populates with a completely different group, then we'll need to store that information as well (in the same tile). This means that we'll need to store a map of groupID -> GroupDetails.

We *could* skip all this if we wanted a separate quadmap per group, but given we need to search all groups at once, this would be incredibly inefficient

func NewTile 

func NewTile(x uint32, y uint32, z byte) *Tile

NewTile creates a new tile at slippy co-ords x,y,z Will probably only be used for root tile

func (*Tile) GetFullForGroupIDAndTileType 

func (t *Tile) GetFullForGroupIDAndTileType(groupID uint32, tileType TileType) bool

GetFullForGroupIDAndTileType gets the full flag for a given tile type. Defaults to false if no flag found

func (*Tile) GetTileZoomLevel 

func (t *Tile) GetTileZoomLevel() byte

GetTileZoomLevel returns zoom level of tile

func (*Tile) HasTileType 

func (t *Tile) HasTileType(groupID uint32, tt TileType) bool

HasTileType... needs to loop through array. Hopefully wouldn't be too many FIXME(kpfaulkner) measure and confirm

func (*Tile) SetFullForGroupIDAndTileType 

func (t *Tile) SetFullForGroupIDAndTileType(groupID uint32, tileType TileType, full bool) error

SetFullForGroupIDAndTileType sets the full flag for a given tile type. Only creates Full map at this stage (saves us creating a potential mass of unused maps)

func (*Tile) SetTileType 

func (t *Tile) SetTileType(groupID uint32, tt TileType) error

SetTileType for a given groupID and tiletype. Checks if groupID + tiletype combination already exists. Returns error if so.

type TileDetails 

type TileDetails struct {
	Groups []TileDetailsGroup
}

TileDetails information about a tile, groups its associated with, tiletypes etc etc. TileDetails is used when returning query results and NOT actually part of the quadmap itself.

type TileDetailsGroup 

type TileDetailsGroup struct {
	GroupDetails
	QuadKey QuadKey
}

TileDetailsGroup is same as TileDetails but we also want the quadkey that gave us the match. TileDetailsGroup is used when returning query results and NOT actually part of the quadmap itself.

type TileType 

type TileType uint16

TileType is the type of a given tile Given we'll have very few tile types we could just use a byte, but may eventually use this as a bitmask to help filtering. So will keep it as a uint16 for now. Can change later if space becomes an issue

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.