Crate zhang_hilbert

Source
Expand description

This crate provides iterator types that produce an arbitrary-sized pseudo-Hilbert scan based on “A Pseudo-Hilbert Scan for Arbitrarily-Sized Arrays” by Zhang, et al.

use zhang_hilbert::ArbHilbertScan32;
for [x, y] in ArbHilbertScan32::new([11, 42]) {
    assert!(x >= 0 && y >= 0 && x < 11 && y < 42);
    println!("{:?}", [x, y]);
}

§Differences from the original algorithm

§The last E_B(E, O) block

This implementation uses a different curve-type selection rule for the last E_B(E, O) block in a E_R(E, O) rectangle. This makes the leaving point fixed at a known point in more cases, making the output suitable for tiling.

cargo run --example hilbertgen -- -a zhang 6 7
  ,---, ,---,        ,---, ,---,
  '-, '-' ,-'        '-, '-' ,-'
  ,-' ,-, '-,        ,-' ,-, '-,
  '-, | '---'        '-, | '---'
  ,-' '-, ,--        ,-' '-----,
  '-, ,-' '-,        '-, ,-----'
  --' '-----'        --' '------
   Original      This implementation

cargo run --example hilbertgen -- -a zhang 4 3
    ,------           ,-----,
    '-----,           '-, ,-'
    ------'           --' '--
   Original      This implementation

§Aspect-ratio bounded tiling

The algorithm accepts any rectangle size, but the output quality deteriorates as the proportions of the rectangle gets distant from square. ArbHilbertScanCore improves it by dividing the rectangle into multiple rectangles whose proportions are closer to square than the original rectangle is (thus their aspect ratios are bounded).

$ cargo run --example hilbertgen -- 40 7
,---, ,---, ,---, ,---, ,---, ,-, ,---, ,---, ,---, ,---, ,-, ,---, ,---, ,---,
'-, '-' ,-' '-, '-' ,-' '-, '-' '-' ,-' '-, '-' ,-' '-, '-' '-' ,-' '-, '-' ,-'
,-' ,-, '-, ,-' ,-, '-, ,-' ,-, ,-, '-, ,-' ,-, '-, ,-' ,-, ,-, '-, ,-' ,-, '-,
'-, | '---' '-, | '---' '---' | | '---' '-, | '---' '---' | | '---' '-, | '---'
,-' '-----, ,-' '-----, ,-----' '-----, ,-' '-----, ,-----' '-----, ,-' '-----,
'-, ,-----' '-, ,-----' '-----, ,-----' '-, ,-----' '-----, ,-----' '-, ,-----'
--' '---------' '-------------' '---------' '-------------' '---------' '------

$ cargo run --example hilbertgen -- -a zhang 40 7
,-----------------------, ,-, ,-, ,-, ,-, ,-, ,-, ,-, ,-, ,-, ,---------------,
'---------------------, '-' '-' '-' '-' '-' '-' '-' '-' '-' '-' ,-------------'
,---------------------' ,-, ,-, ,-, ,-, ,-, ,-, ,-, ,-, ,-, ,-, '-------------,
'-----------------------' '-' '-' '-' '-' '-' | | '-' '-' '-' '---------------'
,---------------------------------------------' '-----------------------------,
'---------------------------------------------, ,-----------------------------'
----------------------------------------------' '------------------------------

§The division function

The division internal function was modified for efficient implementation. As a result, the function produces an different output for the input 3⋅2ⁿ.

Structs§

  • ArbHilbertScanCore
    An iterator wrapping HilbertScanCore that produces better results for rectangles having extreme proportions.
  • HilbertScanCore
    An iterator producing a pseudo-Hilbert scan.
  • LevelInfo
    Stores pre-calculated values used to generate a pseudo-Hilbert scan of a specific size.
  • LevelState
    Stores the state data required for a single subdivision level.

Functions§

Type Aliases§