德國數學家David Hilbert在1891年構造了一種曲線，首先把一個正方形等分成四個小正方形，依次從西北角的正方形中心出發往南到西南正方形中心，再往東到東南角的正方形中心，再往北到東北角正方形中心，這是一次迭代；如果對四個小正方形繼續上述程序，往下劃分，反復進行，最終就得到一條可以填滿整個正方形的曲線，這就是Hibert曲線，其生成程序如圖1所示，
圖1 Hilbert曲線的生成
Hilbert曲線可以采用遞回程序實作，在遞回處理時，連接中點的方式有4種，如圖2所示，
圖2 連接中心點的4種方式
設正方形左上角的頂點坐標為（x1,y1），右下角頂點坐標為（x2,y2），若將方式（3）的正方形左上角坐標置為（x2,y2），右下角坐標置為（x1,y1），則方式（3）等同于方式（1），相當于旋轉180°；同理，方式（4）等同于方式（2），因此，4種連接中心點的方式可以看成（1）和（2）兩種，
兩種連線方式的連線走向及下一次擴展的方式如圖3所示，
圖3 兩種連線方式走向及擴展
其中，方式（1）的四個中心點坐標分別為：
①（x1+dx/4,y1+dy/4） ②（x1+dx/4, y1+3*dy/4）
③ （x1+3*dx/4, y1+3*dy/4） ④（x1+3*dx/4,y1+dy/4） （dx=x2-1,dy=y2-y1）
方式（2）的四個中心點坐標分別為：
①（x1+dx/4,y1+dy/4） ②（x1+3*dx/4,y1+dy/4）
③ （x1+3*dx/4, y1+3*dy/4） ④（x1+dx/4, y1+3*dy/4）
為此，引入一個標識變數s，s=1表示方式（1），s=-1表示方式（2），這樣兩種方式的中心點坐標可以統一表示為：
①（x1+dx/4,y1+dy/4） ②（x1+(2-s)*dx/4, y1+(2+s)*dy/4）
③（x1+3*dx/4, y1+3*dy/4） ④（x1+(2+s)*dx/4,y1+(2-s)*dy/4）
遞回擴展時，方式（1）中4個小正方形的擴展方式分別是：方式（2）、方式（1）、方式（1）和方式（4）（注意：給定兩個頂點坐標順序調整后等同于方式（2））；方式（2）中4個小正方形的擴展方式分別是：方式（1）、方式（2）、方式（2）和方式（3），
撰寫如下的HTML代碼，
<!DOCTYPE html>
<head>
<title>Hilbert曲線</title>
</head>
<body>
<canvas id="myCanvas" width="500" height="500" style="border:3px double #996633;">
</canvas>
<script type="text/javascript">
var canvas = document.getElementById('myCanvas');
var ctx = canvas.getContext('2d');
var depth=5;
ctx.lineWidth = 2;
ctx.strokeStyle = "red";
ctx.beginPath();
ctx.moveTo(50+400/Math.pow(2,depth+1),50+400/Math.pow(2,depth+1));
drawShapes(depth,1,50,50,450,450);
ctx.stroke();
function drawShapes(n,s,x1,y1,x2,y2)
{
dx = x2 - x1,
dy = y2 - y1;
if (n>1)
{
if(s>0)
{
drawShapes(n-1,-1,x1,y1,(x1+x2)/2,(y1+y2)/2);
drawShapes(n-1,1,x1,(y1+y2)/2,(x1+x2)/2,y2);
drawShapes(n-1,1,(x1+x2)/2,(y1+y2)/2,x2,y2);
drawShapes(n-1,-1,x2,(y1+y2)/2,(x1+x2)/2,y1);
}
else
{
drawShapes(n-1,1,x1,y1,(x1+x2)/2,(y1+y2)/2);
drawShapes(n-1,-1,(x1+x2)/2,y1,x2,(y1+y2)/2);
drawShapes(n-1,-1,(x1+x2)/2,(y1+y2)/2,x2,y2);
drawShapes(n-1,1,(x1+x2)/2,y2,x1,(y1+y2)/2);
}
}
if (n==1)
{
ctx.lineTo(x1+dx/4,y1+dy/4);
ctx.lineTo(x1+(2-s)*dx/4, y1+(2+s)*dy/4);
ctx.lineTo(x1+3*dx/4, y1+3*dy/4);
ctx.lineTo(x1+(2+s)*dx/4,y1+(2-s)*dy/4);
}
}
</script>
</body>
</html>
在瀏覽器中打開包含這段HTML代碼的html檔案，可以看到在瀏覽器視窗中繪制出如圖4所示的Hilbert曲線，
圖4 遞回深度maxdepth =5的Hilbert曲線
上面的程式需要推出方式（一）和方式（二）的坐標統一形式，還需注意方式（3）和方式（4）與方式（一）和方式（二）的同一性，
由于Hilbert曲線可以看成是4種方式進行組合，因此可以直接對4種方式撰寫遞回程序，撰寫如下的HTML檔案，
<!DOCTYPE html>
<head>
<title>Hilbert曲線</title>
</head>
<body>
<canvas id="myCanvas" width="500" height="500" style="border:3px double #996633;">
</canvas>
<script type="text/javascript">
var canvas = document.getElementById('myCanvas');
var ctx = canvas.getContext('2d');
ctx.lineWidth = 2;
ctx.strokeStyle = "red";
ctx.beginPath();
var depth=5; // 遞回深度
var h=400/Math.pow(2,depth);
var x = 50+h;
var y = 50+h;
ctx.moveTo(x,y);
One(depth);
ctx.stroke();
function One(n) // 方式（1）的遞回呼叫
{
if(n > 0)
{
Two(n-1);
ctx.lineTo(x, y+h); y+=h;
One(n-1);
ctx.lineTo(x+h, y); x+=h;
One(n-1);
ctx.lineTo(x, y-h); y-=h;
Four(n-1);
}
}
function Two(n) // 方式（2）的遞回呼叫
{
if(n > 0)
{
One(n-1);
ctx.lineTo(x+h, y); x+=h;
Two(n-1);
ctx.lineTo(x, y+h); y+=h;
Two(n-1);
ctx.lineTo(x-h, y); x-=h;
Three(n-1);
}
}
function Three(n) // 方式（3）的遞回呼叫
{
if(n > 0)
{
Four(n-1);
ctx.lineTo(x, y-h); y-=h;
Three(n-1);
ctx.lineTo(x-h, y); x-=h;
Three(n-1);
ctx.lineTo(x, y+h); y+=h;
Two(n-1);
}
}
function Four(n) // 方式（4）的遞回呼叫
{
if(n > 0)
{
Three(n-1);
ctx.lineTo(x-h,y); x-=h;
Four(n-1);
ctx.lineTo(x, y-h); y-=h;
Four(n-1);
ctx.lineTo(x+h, y); x+=h;
One(n-1);
}
}
</script>
</body>
</html>
在瀏覽器中打開包含這段HTML代碼的html檔案，可以看到在瀏覽器視窗中繪制出如圖5所示的Hilbert曲線，
圖5 呼叫One(depth)時繪制的圖形
將程式中的呼叫陳述句“One(depth)”改寫成“Two(depth)”，則在瀏覽器視窗中繪制出如圖6所示的Hilbert曲線，這個圖形可以看成是圖5向左旋轉90°得到的，實際上，由圖2可知，將方式（一）的圖形向左旋轉90°得到的就是方式（二）的圖形，
圖6 呼叫Two(depth)時繪制的圖形
將程式中呼叫陳述句“One(depth)”改寫成“Three(depth)”，同時修改初始坐標為
“var x = 450-h; var y = 450-h;”，則在瀏覽器視窗中繪制出如圖7所示的Hilbert曲線，
圖7 呼叫THree(depth)時繪制的圖形
將程式中呼叫陳述句“One(depth)”改寫成“Four(depth);”，同時修改初始坐標為
“var x = 450-h; var y = 450-h;”，則在瀏覽器視窗中繪制出如圖8所示的Hilbert曲線，
圖8 呼叫Four(depth)時繪制的圖形
將Hilbert曲線的生成程序進行影片展示，撰寫如下的HTML代碼，
<!DOCTYPE>
<html>
<head>
<title>Hilbert曲線</title>
</head>
<body>
<canvas id="myCanvas" width="500" height="500" style="border:3px double #996633;"></canvas>
<script type="text/javascript">
var canvas = document.getElementById('myCanvas');
var ctx = canvas.getContext('2d');
var depth=1;
function drawShapes(n,s,x1,y1,x2,y2)
{
dx = x2 - x1,
dy = y2 - y1;
if (n>1)
{
if(s>0)
{
drawShapes(n-1,-1,x1,y1,(x1+x2)/2,(y1+y2)/2);
drawShapes(n-1,1,x1,(y1+y2)/2,(x1+x2)/2,y2);
drawShapes(n-1,1,(x1+x2)/2,(y1+y2)/2,x2,y2);
drawShapes(n-1,-1,x2,(y1+y2)/2,(x1+x2)/2,y1);
}
else
{
drawShapes(n-1,1,x1,y1,(x1+x2)/2,(y1+y2)/2);
drawShapes(n-1,-1,(x1+x2)/2,y1,x2,(y1+y2)/2);
drawShapes(n-1,-1,(x1+x2)/2,(y1+y2)/2,x2,y2);
drawShapes(n-1,1,(x1+x2)/2,y2,x1,(y1+y2)/2);
}
}
if (n==1)
{
ctx.lineTo(x1+dx/4,y1+dy/4);
ctx.lineTo(x1+(2-s)*dx/4, y1+(2+s)*dy/4);
ctx.lineTo(x1+3*dx/4, y1+3*dy/4);
ctx.lineTo(x1+(2+s)*dx/4,y1+(2-s)*dy/4);
}
}
function go()
{
ctx.clearRect(0,0,canvas.width,canvas.height);
ctx.lineWidth = 2;
ctx.strokeStyle = "red";
ctx.beginPath();
ctx.moveTo(50+400/Math.pow(2,depth+1),50+400/Math.pow(2,depth+1));
drawShapes(depth,1,50,50,450,450);
ctx.stroke();
depth++;
if (depth>6)
{
depth=1;
}
}
window.setInterval('go()', 1000);
</script>
</body>
</html>
在瀏覽器中打開包含這段HTML代碼的html檔案，可以看到在瀏覽器視窗中呈現出如圖9所示的Hilbert曲線動態生成效果，
圖9 Hilbert曲線動態生成
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/45605.html
標籤：JavaScript
上一篇：實作 React Hooks