packedrtree

package
v1.0.0 Latest Latest
Warning

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

 Go to latest Published: Dec 21, 2023 License: MIT Imports: 7 Imported by: 0

Documentation

Overview

Package packedrtree provides a packed Hilbert R-Tree spatial index.

Although designed for FlatGeobuf compatibility, the simple, reusable, constructs within this package can be used standalone from FlatGeobuf, wherever a spatial index is needed.

Index

Examples

Constants

View Source 
const (
	// HilbertOrder is the order of the Hilbert curve used in
	// HilbertSort.
	HilbertOrder = 16
)

Variables

View Source 
var EmptyBox = Box{
	XMin: math.Inf(1),
	YMin: math.Inf(1),
	XMax: math.Inf(-1),
	YMax: math.Inf(-1),
}

EmptyBox is an empty Box that can always be expanded.

Functions

func HilbertSort 

func HilbertSort(refs []Ref, bounds Box)

HilbertSort sorts a list of feature references, whose overall bounding box is given by bounds, in descending order of position on a Hilbert curve of order HilbertOrder.

The sort algorithm is not guaranteed to be stable, so the relative position of two feature references with the same index on the Hilbert curve may change as a result of the sort.

The descending sort order may be somewhat unexpected, as ascending order is perhaps more idiomatic. Descending order is done to maximize consistency with other FlatGeobuf implementations, but nothing turns on the sort order. Both ascending and descending sorts can be used to create a valid PackedRTree, and any FlatGeobuf implementation will work equally well with an index sorted either way.

Example 
package main

import (
	"fmt"

	"github.com/gogama/flatgeobuf/packedrtree"
)

// Create a Ref slice for example purposes.
var refs = []packedrtree.Ref{
	{Box: packedrtree.Box{XMin: -2, YMin: -2, XMax: -1, YMax: -1}, Offset: 0},
	{Box: packedrtree.Box{XMin: 1, YMin: 1, XMax: 2, YMax: 2}, Offset: 1},
	{Box: packedrtree.Box{XMin: -2, YMin: 1, XMax: -1, YMax: 2}, Offset: 2},
	{Box: packedrtree.Box{XMin: 1, YMin: -2, XMax: 2, YMax: -1}, Offset: 3},
}

func refsBounds(r []packedrtree.Ref) packedrtree.Box {
	b := packedrtree.EmptyBox
	for i := range r {
		b.Expand(&r[i].Box)
	}
	return b
}

func main() {
	packedrtree.HilbertSort(refs, refsBounds(refs))

	fmt.Println(refs)
}

Output:

[Ref{[1,-2,2,-1],Offset:3} Ref{[1,1,2,2],Offset:1} Ref{[-2,1,-1,2],Offset:2} Ref{[-2,-2,-1,-1],Offset:0}]

func Size 

func Size(numRefs int, nodeSize uint16) (int, error)

Size returns the disk size in bytes of a packed Hilbert R-Tree index having a given feature reference count and node size. Panics if numRefs is less than 1 or nodeSize is less than 2, and returns an error if integer overflow occurs.

Types

type Box 

type Box struct {
	XMin float64
	YMin float64
	XMax float64
	YMax float64
}

Box is a 2D bounding box.

func (*Box) Expand 

func (b *Box) Expand(c *Box)

Expand ensures one Box completely contains another Box.

Expand makes the minimum necessary expansion to the receiver Box, and only if a change is necessary to contain the parameter.

func (*Box) ExpandXY 

func (b *Box) ExpandXY(x, y float64)

ExpandXY ensures a Box contains a coordinate pair.

ExpandXY makes the minimum possible expansion to the receiver Box, and only if a change is necessary to contain the (x, y) coordinate.

func (*Box) Height 

func (b *Box) Height() float64

Height returns the height of the Box.

func (Box) String 

func (b Box) String() string

String serializes a Box as a GeoJSON-compliant bounding box string with 8 decimal digits of precision.

func (*Box) Width 

func (b *Box) Width() float64

Width returns the width of the Box.

type PackedRTree 

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

PackedRTree is a packed Hilbert R-Tree.

func New 

func New(refs []Ref, nodeSize uint16) (*PackedRTree, error)

New creates a new packed Hilbert R-Tree from a non-empty, Hilbert-sorted list of feature references and a given R-Tree node size. Panics if the reference list is empty or node size is less than 2.

Use HilbertSort to sort the feature references. If the input slice is not Hilbert-sorted, the behavior of the new PackedRTree is undefined.

Example 
package main

import (
	"fmt"

	"github.com/gogama/flatgeobuf/packedrtree"
)

// Create a Ref slice for example purposes.
var refs = []packedrtree.Ref{
	{Box: packedrtree.Box{XMin: -2, YMin: -2, XMax: -1, YMax: -1}, Offset: 0},
	{Box: packedrtree.Box{XMin: 1, YMin: 1, XMax: 2, YMax: 2}, Offset: 1},
	{Box: packedrtree.Box{XMin: -2, YMin: 1, XMax: -1, YMax: 2}, Offset: 2},
	{Box: packedrtree.Box{XMin: 1, YMin: -2, XMax: 2, YMax: -1}, Offset: 3},
}

func refsBounds(r []packedrtree.Ref) packedrtree.Box {
	b := packedrtree.EmptyBox
	for i := range r {
		b.Expand(&r[i].Box)
	}
	return b
}

func main() {
	packedrtree.HilbertSort(refs, refsBounds(refs)) // Refs must be Hilbert-sorted for New.
	index, _ := packedrtree.New(refs, 10)           // Ignore error ONLY to keep example simple.

	fmt.Println(index)
}

Output:

PackedRTree{Bounds:[-2,-2,2,2],NumRefs:4,NodeSize:10}

func Unmarshal 

func Unmarshal(r io.Reader, numRefs int, nodeSize uint16) (*PackedRTree, error)

Unmarshal deserializes a stream from the FlatGeobuf index section format, returning the in-memory search tree built from the stream.

If you are reading from a FlatGeobuf file, the reader should be positioned ready to read the first byte of the index section. If this function returns without error, the reader will be positioned ready to read the first byte of the data section.

The Seek function can be used to search an on-disk or in-storage representation of the index without needing to unmarshal it.

Example 
package main

import (
	"bytes"
	"fmt"

	"github.com/gogama/flatgeobuf/packedrtree"
)

// Create a Ref slice for example purposes.
var refs = []packedrtree.Ref{
	{Box: packedrtree.Box{XMin: -2, YMin: -2, XMax: -1, YMax: -1}, Offset: 0},
	{Box: packedrtree.Box{XMin: 1, YMin: 1, XMax: 2, YMax: 2}, Offset: 1},
	{Box: packedrtree.Box{XMin: -2, YMin: 1, XMax: -1, YMax: 2}, Offset: 2},
	{Box: packedrtree.Box{XMin: 1, YMin: -2, XMax: 2, YMax: -1}, Offset: 3},
}

func refsBounds(r []packedrtree.Ref) packedrtree.Box {
	b := packedrtree.EmptyBox
	for i := range r {
		b.Expand(&r[i].Box)
	}
	return b
}

func main() {
	// Marshal an index to bytes so that we can Unmarshal it.
	packedrtree.HilbertSort(refs, refsBounds(refs)) // Refs must be Hilbert-sorted for New.
	index, _ := packedrtree.New(refs, 10)           // Ignore error ONLY to keep example simple.
	var b bytes.Buffer
	_, _ = index.Marshal(&b)

	// Unmarshal from bytes.
	index, _ = packedrtree.Unmarshal(&b, len(refs), 10)
	fmt.Println(index)
}

Output:

PackedRTree{Bounds:[-2,-2,2,2],NumRefs:4,NodeSize:10}

func (*PackedRTree) Bounds 

func (prt *PackedRTree) Bounds() Box

Bounds returns the bounding box around all features referenced by the packed Hilbert R-Tree.

func (*PackedRTree) Marshal 

func (prt *PackedRTree) Marshal(w io.Writer) (n int, err error)

Marshal serializes the packed Hilbert R-Tree as a FlatGeobuf index section. It returns the number of bytes written.

If you are writing a complete FlatGeobuf file, the writer should be positioned ready to write the first byte of the index. If this method returns without error, the writer will be positioned ready to write the first byte of the data section.

func (*PackedRTree) NodeSize 

func (prt *PackedRTree) NodeSize() uint16

NodeSize returns the number of R-Tree child nodes per parent node.

func (*PackedRTree) NumRefs 

func (prt *PackedRTree) NumRefs() int

NumRefs returns the number of feature references stored in the packed Hilbert R-Tree.

func (*PackedRTree) Search 

func (prt *PackedRTree) Search(b Box) Results

Search searches the packed Hilbert R-Tree for qualified matches whose bounding rectangles intersect the query box. The order of the search results is not defined.

To directly search the index section of FlatGeobuf file without creating a PackedRTree, consider using the Seek function.

Example 
package main

import (
	"fmt"

	"github.com/gogama/flatgeobuf/packedrtree"
)

// Create a Ref slice for example purposes.
var refs = []packedrtree.Ref{
	{Box: packedrtree.Box{XMin: -2, YMin: -2, XMax: -1, YMax: -1}, Offset: 0},
	{Box: packedrtree.Box{XMin: 1, YMin: 1, XMax: 2, YMax: 2}, Offset: 1},
	{Box: packedrtree.Box{XMin: -2, YMin: 1, XMax: -1, YMax: 2}, Offset: 2},
	{Box: packedrtree.Box{XMin: 1, YMin: -2, XMax: 2, YMax: -1}, Offset: 3},
}

func refsBounds(r []packedrtree.Ref) packedrtree.Box {
	b := packedrtree.EmptyBox
	for i := range r {
		b.Expand(&r[i].Box)
	}
	return b
}

func main() {
	packedrtree.HilbertSort(refs, refsBounds(refs)) // Refs must be Hilbert-sorted for New.
	index, _ := packedrtree.New(refs, 10)           // Ignore error ONLY to keep example simple.

	rs1 := index.Search(packedrtree.EmptyBox) // Search 1
	fmt.Println("Search 1:", rs1)

	rs2 := index.Search(packedrtree.Box{XMin: -10, YMin: -10, XMax: -5, YMax: -5}) // Search 2
	fmt.Println("Search 2:", rs2)

	rs3 := index.Search(index.Bounds()) // Search 3
	fmt.Printf("Search 3: %+v\n", rs3)

	rs4 := index.Search(packedrtree.Box{XMin: 0, YMin: -1, XMax: 1, YMax: 0}) // Search 4
	fmt.Printf("Search 4: %+v\n", rs4)
}

Output:

Search 1: []
Search 2: []
Search 3: [{Offset:3 RefIndex:0} {Offset:1 RefIndex:1} {Offset:2 RefIndex:2} {Offset:0 RefIndex:3}]
Search 4: [{Offset:3 RefIndex:0}]

func (*PackedRTree) String 

func (prt *PackedRTree) String() string

String returns a summary description of the packed Hilbert R-Tree.

type Ref 

type Ref struct {
	// The Box is the bounding box of the referenced feature.
	Box

	// Offset is the referenced feature's byte offset into the data
	// section, when working with FlatGeobuf; otherwise it can contain
	// any arbitrary data useful for identifying the referenced feature.
	Offset int64
}

A Ref is a single item within the PackedRTree and represents a reference to a feature stored elsewhere. That "elsewhere" will often be the data section of a FlatGeobuf file.

func (Ref) String 

func (r Ref) String() string

type Result 

type Result struct {
	// Offset contains the Offset field from the matched Ref.
	//
	// If working with FlatGeobuf, this is the byte offset of the result
	// feature in the FlatGeobuf data section.
	Offset int64
	// RefIndex is the index of the matched Ref.
	//
	// If working with a PackedRTree created by new, this is the index
	// of the Ref in the input slice passed to New. If working with a
	// PackedRTree deserialized with Unmarshal, this is the index of
	// the Ref relative to the start of the leaf nodes in the serialized
	// representation.
	RefIndex int
}

Result is a qualified index search result. It represents a matched Ref, i.e. a Ref whose bounding box intersected the query box.

type Results 

type Results []Result

Results is a slice of Result structures implementing sort.Interface. The sort.Sort function will sort a Results instance in ascending order of Result.Offset.

func Seek 

func Seek(rs io.ReadSeeker, numRefs int, nodeSize uint16, b Box) (Results, error)

Seek searches the serialized representation of a packed Hilbert R-Tree index directly, from a seekable stream, without needing to Unmarshal the index into an in-memory data structure.

Seek returns all qualified matches whose bounding boxes intersect the query box. Results are guaranteed to be in ascending order of Result.Offset.

The seekable reader should be positioned ready to read the first byte of the FlatGeobuf index section. If this function returns without error, the seekable reader will be positioned ready to read the first byte of the data section.

Example 
package main

import (
	"bytes"
	"fmt"

	"github.com/gogama/flatgeobuf/packedrtree"
)

// Create a Ref slice for example purposes.
var refs = []packedrtree.Ref{
	{Box: packedrtree.Box{XMin: -2, YMin: -2, XMax: -1, YMax: -1}, Offset: 0},
	{Box: packedrtree.Box{XMin: 1, YMin: 1, XMax: 2, YMax: 2}, Offset: 1},
	{Box: packedrtree.Box{XMin: -2, YMin: 1, XMax: -1, YMax: 2}, Offset: 2},
	{Box: packedrtree.Box{XMin: 1, YMin: -2, XMax: 2, YMax: -1}, Offset: 3},
}

func refsBounds(r []packedrtree.Ref) packedrtree.Box {
	b := packedrtree.EmptyBox
	for i := range r {
		b.Expand(&r[i].Box)
	}
	return b
}

func main() {
	// Marshal an index to bytes so that we can seek within the raw bytes.
	packedrtree.HilbertSort(refs, refsBounds(refs)) // Refs must be Hilbert-sorted for New.
	index, _ := packedrtree.New(refs, 10)           // Ignore error ONLY to keep example simple.
	var b bytes.Buffer
	_, _ = index.Marshal(&b)

	// Do four streaming index searches on the raw index bytes.
	rs1, err1 := packedrtree.Seek(bytes.NewReader(b.Bytes()), len(refs), 10, packedrtree.EmptyBox)
	fmt.Println("Seek 1:", rs1, err1)

	rs2, err2 := packedrtree.Seek(bytes.NewReader(b.Bytes()), len(refs), 10, packedrtree.Box{XMin: -10, YMin: -10, XMax: -5, YMax: -5}) // Seek 2
	fmt.Println("Seek 2:", rs2, err2)

	rs3, err3 := packedrtree.Seek(bytes.NewReader(b.Bytes()), len(refs), 10, index.Bounds()) // Seek 3
	fmt.Printf("Seek 3: %+v %v\n", rs3, err3)

	rs4, err4 := packedrtree.Seek(bytes.NewReader(b.Bytes()), len(refs), 10, packedrtree.Box{XMin: 0, YMin: -1, XMax: 1, YMax: 0}) // Seek 4
	fmt.Printf("Seek 4: %+v %v\n", rs4, err4)
}

Output:

Seek 1: [] <nil>
Seek 2: [] <nil>
Seek 3: [{Offset:3 RefIndex:0} {Offset:1 RefIndex:1} {Offset:2 RefIndex:2} {Offset:0 RefIndex:3}] <nil>
Seek 4: [{Offset:3 RefIndex:0}] <nil>

func (Results) Len 

func (rs Results) Len() int

Len returns the length of the slice. It implements the corresponding method of sort.Interface.

func (Results) Less 

func (rs Results) Less(i, j int) bool

Less establishes an absolute ordering by ascending order of Result.Offset. It implements the corresponding method of sort.Interface.

func (Results) Swap 

func (rs Results) Swap(i, j int)

Swap swaps two elements of the slice. It implements the corresponding method of sort.Interface.

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.