Struct hilbert::point::Point

pub struct Point { /* fields omitted */ }

An immutable, N-dimensional point with unsigned integer coordinates and an optimized distance function.

If the Point was created using make_points_i32 or make_points_f64 from the point_list module, or if the caller took special care to ensure the coordinate values are in the desired range for the Hilbert Curve, then the Point is fit to be converted into a Hilbert Index using the hilbert_transform method.

Use hilbert_sort if you are uninterested in the Hilbert Index and merely need many points sorted by the index.

Examples

        use crate::hilbert::point::Point;
        use crate::hilbert::point_list;
 
        // 1. Create two 3-D points and get the square of the distance between them.
        let p1 = Point::new(0, &[3, 4, 5]);
        let p2 = Point::new(1, &[0, 8, 10]);
        let sqr_dist = p1.square_distance(&p2);
        assert!(sqr_dist == 50, "Square distance should be 50");
 
        // 2. Perform the Hilbert Transform on a single point,
        //    using 5 bits per dimension (which assumes no coordinate exceeds 31).
        let index1 = p1.hilbert_transform(5);
 
        // 3. Create several points and normalize them.
        //    This will ensure that the ids begin at zero and that all values
        //    are multiplied by 10.0 before being rounded to the nearest integer,
        //    to preserve the predetermined precision.
        let point_data : Vec<Vec<f64>> = vec![
           vec![-10.5, 5.27, 3.66],
           vec![-4.802, 20.2, 100.19],
           vec![42.0, -100.0, 0.0]
        ];
        let (mut points, bits) = point_list::make_points_f64(&point_data, 0, None, None, 10.0);
 
        // 4. Sort the points by the Hilbert Curve, using 11 bits per dimension,
        //    because the range of data is 200.19, multiplied by the scale of 10 
        //  yields 2001.9, ceiling of that yields 2002, which is between 1024 (2^10) 
        //  and 2048 (2^11), so 11 bits are required to store the 
        //  highest coordinate value.
        Point::hilbert_sort(&mut points, 11);

Implementations

impl Point

pub fn new(id: usize, coords: &[u32]) -> Point

Construct a new Point with the given id.

Note: It is the caller’s duty to ensure that ids remain unique.

pub fn permute(&self, permutation: &Permutation) -> Self

Apply a permutation to the Point to generate a new Point where the coordinate values have been reordered, but the id is the same.

pub fn dimensions(&self) -> usize

Number of dimensions for the Point.

pub fn get_id(&self) -> usize

Gets the id for the Point.

pub fn get_coordinates(&self) -> &Vec<u32>

Gets the coordinate values for the point.

pub fn square_distance(&self, other_point: &Point) -> u64

Square of the Cartesian distance between the two points. This is optimized by using the following algebra:

 
 //    (A - B)² = A² + B² - 2·A·B

If you extend this to entire vectors, then:

• A² is the square magnitude of vector A,
• B² is the square magnitude of vector B,
• 2·A·B is twice the dot product of A and B. This saves about N subtractions.

pub fn square_distance_loop_unrolling(&self, other_point: &Point) -> u64

For the purpose of demonstrating benchmark improvement compared to square_distance_no_loop_unrolling.

pub fn square_distance_no_loop_unrolling(&self, other_point: &Point) -> u64

For the purpose of demonstrating benchmark regression compared to square_distance_loop_unrolling.

pub fn are_coordinates_identical(&self, other_point: &Point) -> bool

Compares the coordinates of the two Points to see if they match in value and sequence.

This comparison ignores the ids of the Points.

pub fn hilbert_transform(&self, bits_per_dimension: usize) -> BigUint

Perform a Hilbert transform from a single N-dimensional point to a 1-Dimensional index.

• bits_per_dimension - Number of bits used to encode each coordinate of the Point. This value must be at least one. The BigUint Hilbert Index for the Point will be composed of enough bytes to hold N * bits_per_dimension bits, where N is the number of points. If any coordinate of the Point has a value c >= 2^ bits_per_dimension, results are undefined and will be incorrect.

Note: This should not be called for Points with fewer than two dimensions.

pub fn new_from_hilbert_index(
    id: usize,
    hilbert_index: &BigUint,
    bits_per_dimension: usize,
    dimensions: usize
) -> Self

Create a point from its Hilbert index, by performing the inverse Hilbert transform.

• hilbert_index - One-dimensional distance along the Hilbert curve to get to the desired N-Dimensional point.
• bits_per_dimension - Number of bits used to encode each coordinate of the Point. This value must be at least one. The BigUint Hilbert Index for the Point will be composed of enough bytes to hold N * bits_per_dimension bits, where N is the number of points. If any coordinate of the Point has a value c >= 2^ bits_per_dimension, results are undefined and will be incorrect.
• dimensions - number of dimensions in the point.

pub fn hilbert_sort(points: &mut Vec<Point>, bits_per_dimension: usize)

Sort a collection of Points in ascending Hilbert Index order.

This method discards the Hilbert indices when done.

• points - Points to sort.
• bits_per_dimension - Number of bits used to encode each dimension. The BigUint Hilbert Index for each point will be composed of enough bytes to hold N * bits_per_dimension bits, where N is the number of points. If any coordinate of any Point has a value c >= 2^ bits_per_dimension, results are undefined and will be incorrect.

The points are sorted in place.

pub fn hilbert_sort_permuted(
    points: &mut Vec<Point>,
    bits_per_dimension: usize,
    permutation: &Permutation
)

Sort a collection of Points in ascending Hilbert Index order after applying a Permutation to each point. This has the effect of generating a rotated or reflected Hilbert curve. For N-dimensional points, there are N! variations of the Hilbert curve that can be generated in this way. One curve among these may be more useful than another for a given purpose.

This method discards the Hilbert indices when done.

• points - Points to sort.
• bits_per_dimension - Number of bits used to encode each dimension. The BigUint Hilbert Index for each point will be composed of enough bytes to hold N * bits_per_dimension bits, where N is the number of points. If any coordinate of any Point has a value c >= 2^ bits_per_dimension, results are undefined and will be incorrect.
• permutation - Defines how to reorder the many coordinates in a repeatable way.

Trait Implementations

impl Clone for Point

fn clone(&self) -> Point

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Point

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Hash for Point

fn hash<H: Hasher>(&self, state: &mut H)

To remain consistent with equals, this incorporates the id and square_magnitude into the hash.

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given Hasher.

impl PartialEq<Point> for Point

fn eq(&self, other: &Self) -> bool

Define equality to only compare the id and square_magnitude, for speed.

Note: To compare all the coordinate values, use are_coordinates_identical instead.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=.