２次元ヒルベルト曲線

なんとなく作ってみました。と言っても、wikipediaの英語版のサンプルをほぼコピペです。なので詳細はそちらを見てください(ぉ

class HilbertCurve2
{
public:
	HilbertCurve2( int order ):m_order(order){}
	virtual ~HilbertCurve2(){}

	int GetAllCount()const{
		const int size = GetSize();
		return size * size;
	}
	int GetSize()const{
		return 1 << m_order;
	}

	void GetPosition( int t, int& x, int& y )const{
		x = y = 0;
		for (int order = 0; order < m_order; ++order) {
			const int subSize = 1 << order;
			const int rx = (t >> 1) & 1;
			const int ry = (t ^ rx) & 1;
			rotate(subSize, x, y, rx, ry);
			x += subSize * rx;
			y += subSize * ry;
			t >>= 2;
		}
	}

	int GetLength( int x, int y )const{
		int length(0);
		for (int order = m_order - 1; order >= 0; --order) {
			const int rx = (x >> order) & 1;
			const int ry = (y >> order) & 1;
			const int subSize = 1 << order;
			length += subSize * subSize * ((3 * rx) ^ ry);
			rotate(subSize, x, y, rx, ry);
		}
		return length;
	}
private:
	void rotate(int n, int& x, int& y, int rx, int ry)const{
		if (ry == 0) {
			if (rx == 1) {
				x = n-1 - x;
				y = n-1 - y;
			}
			std::swap( x, y );
		}
	}
private:
	int m_order;
};

フラクタル図形なので再帰の形にしたかったのですが疲れたのでそのまんまorz
で、実際に表示してみました。サイズがでかいのでファイルに書き出しです。

const char direct[4][4][4] = 
{
	{ "─","　","┘","┐",},
	{ "　","─","└","┌",},
	{ "┌","┐","│","　",},
	{ "└","┘","　","│",},
};

int number( int x0, int y0, int xm, int ym ){
	if( xm<x0 ){
		return 0;
	}else if( xm>x0 ){
		return 1;
	}else if( ym>y0 ){
		return 2;
	}else{
		return 3;
	}
}

int main()
{
	int order(0);
	std::cout << "order ? ";
	std::cin >> order;
	HilbertCurve2 hil( order );
	const int size = hil.GetSize();

	std::ofstream fout( "HilbertCurve.txt" );

	for( int y0 = 0; y0 < size; ++y0 ){
		for( int x0 = 0; x0 < size; ++x0 ){
			const int l0 = hil.GetLength( x0, y0 );
			if( l0 == 0 || l0 == size*size-1 ){
				fout << "　";
			}else{
				int xm(0), ym(0), xp(0), yp(0);
				hil.GetPosition( l0-1, xm, ym );
				hil.GetPosition( l0+1, xp, yp );
				const int lm = number( x0, y0, xm, ym );
				const int lp = number( xp, yp, x0, y0 );
				fout << direct[lm][lp];
			}
		}
		fout << std::endl;
	}
}

なお出力されるファイルサイズは2^(order*2+1)なのでorderが１増えると４倍に増えるので注意です。

で、クラス名がHilbertCurve2ということで２がついていますが要するに２次元という意味です。３次元を作ろうとしたのですがデバッグに疲れたので休止中です。ていうか一般的なN次元生成出来るのを作ろうとしたのですが無謀でした。３次元ですら今年中に再開出来る見込みなしorz