[−][src]Struct hilbert::point::Point
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);
Methods
impl Point
[src]
pub fn new(id: usize, coords: &[u32]) -> Point
[src]
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
[src]
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
[src]
Number of dimensions for the Point.
pub fn get_id(&self) -> usize
[src]
Gets the id
for the Point.
pub fn get_coordinates(&self) -> &Vec<u32>
[src]
Gets the coordinate values for the point.
pub fn square_distance(&self, other_point: &Point) -> u64
[src]
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
[src]
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
[src]
For the purpose of demonstrating benchmark regression compared to square_distance_loop_unrolling.
pub fn are_coordinates_identical(&self, other_point: &Point) -> bool
[src]
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
[src]
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. TheBigUint
Hilbert Index for thePoint
will be composed of enough bytes to hold N *bits_per_dimension
bits, where N is the number of points. If any coordinate of thePoint
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 hilbert_sort(points: &mut Vec<Point>, bits_per_dimension: usize)
[src]
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. TheBigUint
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 anyPoint
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
)
[src]
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. TheBigUint
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 anyPoint
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
[src]
impl PartialEq<Point> for Point
[src]
fn eq(&self, other: &Self) -> bool
[src]
Define equality to only compare the id and square_magnitude, for speed.
Note: To compare all the coordinate values, use are_coordinates_identical
instead.
#[must_use]
fn ne(&self, other: &Rhs) -> bool
1.0.0[src]
impl Debug for Point
[src]
impl Hash for Point
[src]
Auto Trait Implementations
impl Send for Point
impl Sync for Point
impl Unpin for Point
impl UnwindSafe for Point
impl RefUnwindSafe for Point
Blanket Implementations
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> From<T> for T
[src]
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
The type returned in the event of a conversion error.
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<V, T> VZip<V> for T where
V: MultiLane<T>,
V: MultiLane<T>,