힐베르트 곡선

힐베르트 곡선의 처음 6회 반복

힐베르트 곡선(힐베르트 공간 채우기 곡선이라고도 함)은 1891년 ^[1]독일 수학자 데이비드 힐베르트(David Hilbert)가 1890년 ^[2]주세페 페아노(Giuseppe Peano)가 발견한 공간 채우기 페아노(Peano) 곡선의 변형으로 처음 기술한 연속 프랙탈 공간 채우기 곡선이다.

공간을 채우고 있기 때문에 하우스도르프 치수는 2이다(정확히 그 이미지는 단위 정사각형이며, 그 치수는 어떤 차원 정의에서도 2이다.그래프는 하우스도르프 치수가 2인 닫힌 단위 간격과 동형인 콤팩트 집합이다).

힐버트 곡선은 구간별 선형 곡선의 한계로 구성됩니다.$(\displaystyle$ n$)$번째$$ 곡선의 길이는$(\$ 2$^{n}-{1\over$ 2$^{n$$\})$입니다. 즉, 각 곡선이 면적$1$의 정사각형에 포함되어 있어도 n$(\$$displaystyle$ n$)$에 따라 $길이$가 기하급수적으로 증가합니다.

이미지들

• 

  힐베르트 곡선, 1차

• 

  힐베르트 곡선, 1차 및 2차

• 

  힐베르트 곡선, 1차에서 3차까지

• 

  생산 규칙

• 

  Hilbert 곡선, 시공 색상 구분

• 

  진행률을 나타내는 색상의 3차원 힐버트 곡선

• 

  변종, 처음 3회 반복^[3]

응용 프로그램 및 매핑 알고리즘

실제 Hilbert 곡선과 이산 근사 모두 1D와 2D 공간 간의 매핑을 제공하여 국소성을 상당히 ^[4]잘 보존하기 때문에 유용합니다.즉, 1차원 공간에서 서로 가까운 두 데이터 지점도 접힌 후 서로 가깝습니다.역이 반드시 참을 수 없다.

이 지역 특성 때문에 힐버트 곡선은 컴퓨터 과학에서 널리 사용됩니다.예를 들어 컴퓨터가 사용하는 IP 주소의 범위를 힐버트 곡선을 사용하여 그림에 매핑할 수 있습니다.이미지를 생성하는 코드는 각 픽셀의 색상을 찾기 위해 2D에서 1D로 매핑되며,^[5] 그림에서 가까운 IP 주소를 서로 가깝게 유지하기 때문에 힐버트 곡선이 사용되기도 합니다.

Riemersma ditering이라고 하는 알고리즘에서는, 그레이스케일 사진을 임계치를 사용해 디더링 된 흑백 화상으로 변환해, 각 화소의 잔량을 힐버트 커브를 따라서 다음의 화소에 가산할 수 있습니다.이를 위한 코드는 1D에서 2D로 매핑되며, 힐버트 곡선은 ^[6]픽셀의 각 행에 걸쳐 단순히 왼쪽에서 오른쪽으로 순서를 지정하면 눈에 보이는 산만 패턴을 생성하지 않기 때문에 때때로 사용됩니다.고차원의 힐버트 곡선은 그레이 코드의 일반화의 한 예이며, 유사한 이유로 유사한 목적으로 사용되기도 한다.다차원 데이터베이스의 경우 힐버트 순서는 지역 보존 동작이 더 우수하기 때문에 Z 순서 대신 사용하도록 제안되었습니다.예를 들어 힐버트 곡선은 R-트리^[7] 인덱스를 압축하고 가속하는 데 사용되었습니다(힐버트 R-트리 참조).또한 데이터 ^[8][9]웨어하우스를 압축하는 데에도 사용되고 있습니다.

어플리케이션의 종류가 다양하기 때문에 쌍방향으로 매핑할 수 있는 알고리즘이 있으면 편리합니다.많은 언어에서 이러한 기능은 재귀가 아닌 반복을 통해 구현되는 것이 좋습니다.다음 C 코드는 재귀가 아닌 반복 및 비트 연산을 사용하여 양방향으로 매핑을 수행합니다.이 예제에서는 왼쪽 아래 모서리에 (0,0), 오른쪽 위 모서리에 (n - 1, n - 1)이 있는 정수 좌표를 가진 n x n 셀로 나누어진 정사각형과 오른쪽 아래 모서리에 있는 ${\displaystyle {n2\mathrm{}}^{}}$ ${\displaystyle {}^{}}$ $(표시 스타일$ n$^{2}-1)$로 이어지는 거리 d를 가정합니다.이는 곡선이 왼쪽 상단 모서리에서 시작하여 오른쪽 상단 모서리에서 끝나는 위의 애니메이션과는 다릅니다.

//(x,y)에서 d로 변경 인트 xy2d (인트 n, 인트 x, 인트 y) {     인트 rx, 라이, s, d=0;     위해서 (s=n/2; s>0; s/=2) {         rx = (x & s) > 0;         라이 = (y & s) > 0;         d += s * s * ((3 * rx) ^ 라이);         썩다(n, &x, &y, rx, 라이);     }     돌아가다 d; }  //d를 (x,y)로 변경 무효 d2xy(인트 n, 인트 d, 인트 *x, 인트 *y) {     인트 rx, 라이, s, t=d;     *x = *y = 0;     위해서 (s=1; s< >n; s*=2) {         rx = 1 & (t/2);         라이 = 1 & (t ^ rx);         썩다(s, x, y, rx, 라이);         *x += s * rx;         *y += s * 라이;         t /= 4;     } }  //쿼드런트를 적절히 조정/조정 무효 썩다(인트 n, int *x, int *y, int rx, int ry) {     한다면 (ry == 0) {         한다면 (rx == 1) {             *x = n-1 - *x;             *y = n-1 - *y;         }          //Swap x와 y         int t  = *x;         *x = *y;         *y = t;     } } 

이:, 상징은 비트 AND,^의 상징은 비트 XOR, += 통신사 변수에 저장하고 /= 운전자가 변수 구분 1을 추가 C규칙 및 사용한다.Cbooleans의 취급은 xy2d에 가변 rx0또는 1x의 비트 s과 ry을 맞추기 설정되어 있습니다.

그 xy2d 기능을 내려가면서, x와 y의 가장 중요한비트로 시작하여, 그리고 건물을 d의 가장 중요한 비트 먼저 맨 위 일한다.그 d2xy 기능은 반대로, d의 최소 유효 비트를 이용, x및 y는 최소 유효 비트를 시작으로 건물부터 일한다.둘 다 기능과 빠른 패스가 적절히(x, y)좌표계를 회전하려면 회전 기능을 사용한다.

두 지도 알고리즘도 이와 유사한 방식에서 일한다.정사각형 전체가 2x2로 배열된 4개의 영역으로 구성됩니다.각 영역은 여러 레벨에 대해 4개의 작은 영역으로 구성됩니다.레벨 s에서는, 각 영역은 s x s 셀입니다.레벨을 반복하는 단일 FOR 루프가 있습니다.각 반복에서 양은 d 또는 x 및 y에 추가되며 현재 수준에서 4개 영역 중 어느 영역에 속해 있는지에 따라 결정됩니다.4개의 영역 중 현재 영역은 (rx,ry)입니다.여기서 rx와 ry는 각각0 또는 1입니다따라서 2개의 입력 비트(d에서 2개 또는 x와 y에서 각각 1개)를 소비하고 2개의 출력 비트를 생성합니다.또한 다음 반복 시 (x,y)가 다음 수준에 적합하도록 회전 함수를 호출합니다.xy2d의 경우 전체 사각형에서 시작하여 개별 셀의 가장 낮은 수준까지 작동합니다.d2xy의 경우 맨 아래에서 셀로 시작하여 정사각형 전체를 포함합니다.

데이터 공간이 ^[10]정사각형을 형성하지 않더라도 힐버트 곡선을 효율적으로 구현할 수 있습니다.또한 힐베르트 곡선을 더 높은 ^[11][12]차원으로 일반화할 수 있는 몇 가지 방법이 있다.

Lindenmayer 시스템으로서의 표현

힐버트 곡선은 개서 시스템(L-system)으로 나타낼 수 있습니다.

알파벳 : A, B

상수: F + -

Axiom : A

생산 규칙:

A → +BF-AFA−FB+

B → -AF+BFB+FA−

여기서 'F'는 '앞으로', '+'는 '좌회전 90°', '-'는 '우회전 90°'를 의미하며, 'A'와 'B'는 그림 그리는 동안 무시된다.

기타 구현

Graphics Gems^[13] II는 Hilbert 곡선의 일관성에 대해 설명하고 구현을 제공합니다.

Hilbert 곡선은 이미지 또는 비디오를 렌더링하는 데 일반적으로 사용됩니다.Blender(블렌더) 및 Cinema 4D(시네마 4D)와 같은 일반 프로그램은 힐버트 곡선을 사용하여 객체를 추적하고 ^{[citation needed]}장면을 렌더링합니다.

「 」를 참조해 주세요.

Wikimedia Commons에는 Hilbert 곡선과 관련된 미디어가 있습니다.

• 힐베르트 곡선 스케줄링
• 힐베르트 R-트리
• 참조 위치
• 지역 구분 해시
• 무어 곡선
• 머레이 폴리곤
• 시에르핀스키 곡선
• 하우스도르프 차원에 따른 프랙탈 목록

메모들

추가 정보

• Warren Jr., Henry S. (2013). Hacker's Delight (2 ed.). Addison Wesley – Pearson Education, Inc. ISBN 978-0-321-84268-8.
• McKenna, Douglas M. (2019). Hilbert Curves: Outside-In and Inside-Gone. Mathemaesthetics, Inc. ISBN 978-1-7332188-0-1.

외부 링크

• JSXGraph를 사용한 동적 힐버트 곡선
• 3.js WebGL 3D Hilbert 곡선 데모
• 힐버트 곡선의 지역 특성을 사용하여 "인터넷 지도"를 만드는 XKCD 만화
• 힐베르트 곡선의 Gcode 발생기
• JavaScript에서 Hilbert 곡선을 그리기 위한 반복 알고리즘
• 알고리즘 781: 재귀에 의한 힐버트의 공간 채우기 곡선 생성(ACM 디지털 라이브러리)