hilbert

Documentation

Overview

Package hilbert facilitates sorting 2D points along a single space-filling Hilbert curve.

Index

• Constants
• Variables
• func Compare(p1, p2 maf.Vec2) int
• func Less(p1, p2 maf.Vec2) bool
• func Vertices(spec PlotSpec) []maf.Vec
• type CurvePath
  • func Magnify(ori Orientation) CurvePath
• type CurveQuadrant
  • func (q CurveQuadrant) SubQuadrants() [4]CurveQuadrant
• type Orientation
• type PlotSpec
• type Quadrant

Constants

const (
	XY   = Orientation(iota) // Standard orientation.
	YnXn                     // Reflection of XY in the line y=-x.
	XnYn                     // Rotation of XY by 180 deg.
	YX                       // Reflection of XY in the line y=x.
)

An orientation specifies the mapping of the basic motif's positive X and Y-axis unit vectors respectively.

A small case 'n' suffix after a capital X or Y indicates a negative axis.

const (
	A = Quadrant(iota) // Top right.
	B                  // Top left.
	C                  // Bottom left.
	D                  // Bottom Right.
)

Variables

var InitialPath = Magnify(XY)

InitialPath is a Hilbert curve of order 2.

Functions

func Compare

func Compare(p1, p2 maf.Vec2) int

Compare the given points using the Hilbert less function.

func Less

func Less(p1, p2 maf.Vec2) bool

Less reports whether the first of the two given 2D points occurs before the second along a space filling Hilbert curve which is occupying the region.

Point coordinates shall be constrained to the range 0 to 1.

By sorting along a Hilbert curve, points which are close together in 2D space are still close together when sorted.

func Vertices

func Vertices(spec PlotSpec) []maf.Vec

Vertices of a 2D pseudo Hilbert curve.

Types

type CurvePath

type CurvePath [4]struct {
	Quadrant
	Orientation
}

CurvePath through a square which is split into four equal sized sub squares.

The curve path progresses through the indices in increasing order: 0, 1, 2, 3.

func Magnify

func Magnify(ori Orientation) CurvePath

Magnify a square section of the curve which consists of the basic motif with the given orientation.

type CurveQuadrant

type CurveQuadrant struct {
	Centre maf.Vec     // The center of the quadrant.
	HalfW  float64     // Half the width of the quadrant.
	Ori    Orientation // The orientation of the quadrant's basic motif.
}

CurveQuadrant is one of the quadrants of a pseudo Hilbert curve.

func (CurveQuadrant) SubQuadrants

func (q CurveQuadrant) SubQuadrants() [4]CurveQuadrant

SubQuadrants of the receiver quadrant in order of the direction of the curve through the sub quadrants.

type Orientation

type Orientation uint

Orientation of the basic motif.

The basic motif is an upside down rectangular 'U' shape and it goes from left to right.

type PlotSpec

type PlotSpec struct {
	// Centre of the 2D square region occupied by the Hilbert curve.
	//
	// The vertices of the curve will be in a plane parallel to the Z=0 plane.
	Centre maf.Vec
	// Order of the Hilbert curve.
	Order int
	// Width of the 2D square region occupied by the Hilbert curve.
	W float64
}

PlotSpec specifies the properties of a pseudo Hilbert curve.

type Quadrant

type Quadrant uint

A Quadrant is one of the four equal sized parts that a square is divided into when increasing the order of the curve by one.