<?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";
}
}
}
?>