Location: PHPKode > scripts > Hilbert curve > hilbert.php
<?php
/***************************************************************
*  Copyright notice
*  
*  (c) 2010 Chi Hoang (hide@address.com)
*  All rights reserved
*
***************************************************************/
/**************************************************************
* Lo Shu-Magic-Square
*
*  4     9	 2
*  3	   5	 7
*  8	   1	 6
*
*  hilbert_map_1  =  N
*  hilbert_map_9  =  S
*  hilbert_map_3  = W
*  hilbert_map_7  =  E
*
***************************************************************/

class hilbert {
	
	var $moore_map = array ( 		"0,0" => array ( 0, "hilbert_map_7"), 
									"0,1" => array ( 1, "hilbert_map_7"),
									"1,1" => array ( 2, "hilbert_map_3"),
									"1,0" => array ( 3, "hilbert_map_3"),
							);
					
	var $hilbert_map_1 = array (		'a' => array (
											"0, 0" => array (0, 'd'),
											"0, 1" => array (1, 'a'), 
											"1, 0" => array (3, 'b'),
											"1, 1" => array (2, 'a')
									), 
									 'b' => array ( 
											 "0, 0" => array (2, 'b'), 
											 "0, 1" => array (1, 'b'), 
											 "1, 0" => array (3, 'a'),
											 "1, 1" => array (0, 'c')
									), 
									'c' => array ( 
											"0, 0" => array (2, 'c'),
											"0, 1" => array (3, 'd'),
											"1, 0" => array (1, 'c'),
											"1, 1" => array (0, 'b')
										), 
									'd' => array (
											"0, 0" => array (0, 'a'), 
											"0, 1" => array (3, 'c'), 
											"1, 0" => array (1, 'd'), 
											"1, 1" => array (2, 'd')
									),
								);

	var $hilbert_map_7 = array ( 		'a' => array (
											 "0, 0" => array (2, 'a'), 
											 "0, 1" => array (1, 'a'), 
											 "1, 0" => array (3, 'b'),
											 "1, 1" => array (0, 'c')
									), 
									 'b' => array ( 
											"0, 0" => array (0, 'd'),
											"0, 1" => array (1, 'b'), 
											"1, 0" => array (3, 'a'),
											"1, 1" => array (2, 'b')
										), 
									'c' => array ( 
											"0, 0" => array (2, 'c'),
											"0, 1" => array (3, 'd'),
											"1, 0" => array (1, 'c'),
											"1, 1" => array (0, 'a')
										), 
									'd' => array (
											"0, 0" => array (0, 'b'), 
											"0, 1" => array (3, 'c'), 
											"1, 0" => array (1, 'd'), 
											"1, 1" => array (2, 'd')
									),
							);

	var $hilbert_map_3 = array ( 	'a' => array (
										"0, 0" => array (0, 'b'), 
										"0, 1" => array (3, 'c'), 
										"1, 0" => array (1, 'a'), 
										"1, 1" => array (2, 'a')
								), 
								 'b' => array ( 
								 		"0, 0" => array (0, 'a'),
										"0, 1" => array (1, 'b'), 
										"1, 0" => array (3, 'd'),
										"1, 1" => array (2, 'b')
									), 
								'c' => array ( 
										"0, 0" => array (2, 'c'),
										"0, 1" => array (3, 'a'),
										"1, 0" => array (1, 'c'),
										"1, 1" => array (0, 'd')
									), 
								'd' => array (
										 "0, 0" => array (2, 'd'), 
										 "0, 1" => array (1, 'd'), 
										 "1, 0" => array (3, 'b'),
										 "1, 1" => array (0, 'c')
								),
						);
			
	var $hilbert_map_9 = array ( 	'a' => array (
										"0, 0" => array (2, 'a'),
										"0, 1" => array (3, 'c'),
										"1, 0" => array (1, 'a'),
										"1, 1" => array (0, 'd')
								), 
								 'b' => array ( 
								 		"0, 0" => array (0, 'c'),
										"0, 1" => array (1, 'b'), 
										"1, 0" => array (3, 'd'),
										"1, 1" => array (2, 'b')
									), 
								'c' => array ( 
										"0, 0" => array (0, 'b'), 
										"0, 1" => array (3, 'a'), 
										"1, 0" => array (1, 'c'), 
										"1, 1" => array (2, 'c')
									), 
								'd' => array (
										 "0, 0" => array (2, 'd'), 
										 "0, 1" => array (1, 'd'), 
										 "1, 0" => array (3, 'b'),
										 "1, 1" => array (0, 'a')
								),
							);
			
	var $rev_map = array (       'a' => array (
									"0, 0" => array (0, 'b'),
									"0, 1" => array (1, 'b'), 
									"1, 0" => array (3, 'd'),
									"1, 1" => array (2, 'd')
							), 
							 'b' => array ( 
									 "0, 0" => array (0, 'a'), 
									 "0, 1" => array (2, 'b'), 
									 "1, 0" => array (3, 'b'),
									 "1, 1" => array (1, 'c')
								), 
							'c' => array ( 
									"0, 0" => array (3, 'd'),
									"0, 1" => array (2, 'c'),
									"1, 0" => array (0, 'c'),
									"1, 1" => array (1, 'b')
								), 
							'd' => array (
									"0, 0" => array (3, 'c'), 
									"0, 1" => array (1, 'd'), 
									"1, 0" => array (0, 'd'), 
									"1, 1" => array (2, 'a')
							),
				);
	
	var $z_map = array       (  'a' => array (
									"0, 0" => array (1, 'a'),
									"0, 1" => array (3, 'a'), 
									"1, 0" => array (0, 'a'),
									"1, 1" => array (2, 'a')
							), 
				);
			
		// a b c d  e  f g h  i  j   k   l     m  n  o    p  q    r   s   t    u   v  w   x    y  z
		// 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
	var $zcurve3d_map = array (    
								'a' => array (
											"0, 0, 0" => array(0,'a'),
											"0, 0, 1" => array(1,'a'),
											"0, 1, 1" => array(5,'a'),
											"0, 1, 0" => array(4,'a'),
											"1, 1, 0" => array(6,'a'),
											"1, 1, 1" => array(7,'a'),
											"1, 0, 1" => array(3,'a'),
											"1, 0, 0" => array(2,'a'),
										),
								);		
	
	
	function point_to_quadtree($x, $y, $order=16) {
		$current_square = 'a' ;
		$position = 0; 
		foreach (range($order-1, 0, -1) as $i) { 
			$quad_x = $x & (1 << $i) ? 1 : 0;
			$quad_y = $y & (1 << $i) ? 1 : 0;
			list($quad_position, $current_square) = $this->hilbert_map[$current_square]["$quad_x, $quad_y"];
			$position .= $quad_position;
		}
		return $position;
	}
	
	function point_to_hilbert3D($x, $y, $z, $order=16) {
		$current_square = 'a' ;
		$position = 0; 
		foreach (range($order-1, 0, -1) as $i) { 
			$position <<= 2; 
			$quad_x = $x & (1 << $i) ? 1 : 0;
			$quad_y = $y & (1 << $i) ? 1 : 0;
			$quad_z = $z & (1 << $i) ? 1 : 0;
			list($quad_position, $current_square) = $this->zcurve3d_map[$current_square]["$quad_x, $quad_y, $quad_z"];
			$position |= $quad_position;
		}
		return $position;
	}
		
	function point_to_hilbert($x, $y, $order=16, $map="hilbert_map_1") {
		$current_square = 'a' ;
		$position = 0; 
		foreach (range($order-1, 0, -1) as $i) { 
			$position <<= 2; 
			$quad_x = $x & (1 << $i) ? 1 : 0;
			$quad_y = $y & (1 << $i) ? 1 : 0;
			list($quad_position, $current_square) = $this->{$map}[$current_square]["$quad_x, $quad_y"];
			$position |= $quad_position;
		}
		return $position;
	}
	
	function hilbert_to_point($hilbert, $order) {
		$current_square = 'a' ;
		$quad_x=$quad_y=$x=$y=0;
		for ($i = 0; $end = 2*$order, $i < $end; $i += 2) {
			$x <<= 1;  $y <<= 1;
			$quad_x = ($hilbert >> ($i+1)) & 1;      // Get bit i+1 of s. 
			$quad_y = ($hilbert >> $i) & 1;          // Get bit i of s.
			list($quad_position, $current_square) = $this->rev_map[$current_square]["$quad_x, $quad_y"];
			$x |= $quad_position & 2 ? 1 : 0;
			$y |= $quad_position & 1 ? 1 : 0;
		} 
		return "$x, $y";
	} 
	
	function point_to_z($x, $y, $order=16) {
		$current_square = 'a' ;
		$position = 0; 
		foreach (range($order-1, 0, -1) as $i) { 
			$position <<= 2; 
			$quad_x = $x & (1 << $i) ? 1 : 0;
			$quad_y = $y & (1 << $i) ? 1 : 0;
			list($quad_position, $current_square) = $this->z_map[$current_square]["$quad_x, $quad_y"];
			$position |= $quad_position;
		}
		return $position;
	}
		
		// points $x,$y should be 2^1 higher than $order
		// example $this->point-to-moore(7,7,2);
		//               $this->point-to-moore(15,15,3);
	function point_to_moore($x, $y, $order=4) {
		$quad = pow(2,$order)-1;
		switch ($order) {
			case 2:
				$curve_length = 16;
				break;
			case  1:
				$curve_length = 8;
				break;
			case  0:
				$curve_length = 4;
				break;	
			default:
				$curve_length = pow(2,$quad)+1;
				//~ $curve_length = pow(2, ($order+1))+1;
				break;
		}
		//~ echo "o:$order,q:$quad,offset:$curve_length\n";
		//~ die();
		
		$quad_x = $x & (1 << $order) ? 1 : 0;
		$quad_y = $y & (1 << $order) ? 1 : 0;
		
		list($pos, $map) = $this->moore_map["$quad_x,$quad_y"];
		$pos*=$curve_length; $quad_x*=$quad+1; $quad_y*=$quad+1;
		$px=$x-$quad_x; $py=$y-$quad_y;
		$index = ($this->point_to_hilbert($px, $py, $order, $map)-$curve_length)*-1+$pos;
		//~ echo "px:$px, py:$py,$map,i:$index\n";
		return $index;
	}
	
	function test_ptm() {
		foreach (range(127,0,-1) as $x) {
			foreach (range(127,0,-1) as $y) {
				$sort[] = $points["$x,$y"] = $this->point_to_moore($x, $y, 6);
			}
		}
		array_multisort($points, $sort);
		foreach ($points as $k => $v) {
			echo $k."\n";
		}
	}
	
	function test_pth() {
		$i=1;
		foreach (range(15,0,-1) as $x) {
			foreach (range(15,0,-1) as $y) {
				//~ echo ($i);
				if (($i % 2) == 0) {
					$context = 7;
				} else {
					$context = 6;
				}
				$sort[] = $points["$x,$y"] = $this->point_to_hilbert($x, $y, $context);
				$i++;
			}
		}
		array_multisort($points, $sort);
		foreach ($points as $k => $v) {
			echo $k."\n";
		}
	}
	
	function test_pth3d() {
		foreach (range(7,0,-1) as $x) {
			foreach (range(7,0,-1) as $y) {
				foreach (range(7,0,-1) as $z) {
					$sort[] = $points["$x,$y,$z"] = $this->point_to_hilbert3D($x, $y, $z, 3);
				}
			}
		}
		array_multisort($points, $sort);
		foreach ($points as $k => $v) {
			echo $k."\n";
		}
	}
}
?>
Return current item: Hilbert curve