공간 채움 곡선 탐색기
선에는 길이가 있지만 넓이가 없고, 정사각형에는 넓이가 있습니다. 그런데도 선을 구부려 정사각형의 모든 부분을 지나게 할 수 있습니다. 칸 몇 개와 그 칸들을 지나는 구부러진 선 하나에서 시작합니다. 모든 칸을 더 작은 칸들로 나누고, 선을 구부려 그 칸들을 모두 지나게 합니다. 이를 되풀이합니다. 펜이 힐베르트 곡선, 페아노 곡선과 그 친척들을 레벨별로 그려 가는 모습을 지켜본 다음, 곡선 위 아무 곳에나 펜을 놓아 선의 어느 점이 정사각형의 어느 칸에 놓이는지 확인해 보세요. 공간 채움 곡선은 격자의 모든 칸을 지나는 하나의 선입니다. 레벨이 오를 때마다 모든 칸이 더 작은 칸들로 나뉘고, 선은 굽이치며 그 칸들을 모두 지납니다. ‘재생’을 누르면 펜이 각 레벨을 처음부터 끝까지 그리는 모습을 볼 수 있고, ‘한 단계’를 누르면 다음 레벨을 그립니다. 힐베르트 곡선, 무어 곡선, 페아노 곡선, Z-순서, 고스퍼의 flowsnake, 시에르핀스키 화살촉 곡선 가운데에서 고를 수 있습니다. 그림 위나 그 아래의 색칠된 선 위, 또는 ‘펜’ 슬라이더를 클릭하거나 드래그하면 펜이 곡선을 따라 움직입니다. ‘위치’ 타일은 걸음의 번호와 그 걸음이 놓인 칸을 알려 줍니다. 색은 선을 따라 차례로 변하므로, 색이 비슷한 칸들은 서로 가까운 걸음입니다.
작동 원리
- ‘재생’을 눌러 펜이 각 레벨을 처음부터 끝까지 그리는 모습을 보거나, ‘한 단계’를 눌러 다음 레벨을 그립니다. ‘레벨’을 드래그하면 원하는 레벨로 바로 이동합니다.
- 힐베르트 곡선, 무어 곡선, 페아노 곡선, Z-순서, 고스퍼 곡선, 시에르핀스키 화살촉 곡선 가운데 하나를 고릅니다.
- 그림 위나 그 아래의 색칠된 선 위, 또는 ‘펜’ 슬라이더를 클릭하거나 드래그해 펜을 곡선을 따라 움직입니다.
- 타일에서 선분 수, 길이, 프랙털 차원, 펜의 위치를 읽습니다.
모든 칸을 지나는 선
레벨 n의 힐베르트 곡선은 2ⁿ × 2ⁿ개의 칸으로 이루어진 격자를 지나며, 각 칸을 한 번씩 방문하고 언제나 이웃한 칸으로 나아갑니다. 레벨 1은 칸 4개를 지나는 굽이 하나입니다. 레벨이 오를 때마다 모든 칸은 더 작은 칸 4개로, 모든 걸음은 그 굽이의 작은 복사본으로 바뀌며, 복사본들은 끝과 끝이 이어지도록 돌려 놓입니다. 4ⁿ개의 칸을 지나는 선은 4ⁿ − 1걸음으로 이루어지고, 길이는 정사각형 한 변의 2ⁿ − 2⁻ⁿ배입니다. 그림의 크기는 그대로인데 길이는 레벨마다 거의 두 배가 됩니다. 페아노 곡선은 칸 하나를 칸 9개로 나누어 S자 굽이로 같은 일을 하고, 무어 곡선은 힐베르트 곡선 네 개를 이어 닫힌 고리를 만듭니다.
수직선에서 정사각형으로
그림 아래의 색칠된 선은 0에서 1까지의 수직선이고, 곡선은 그 수직선을 정사각형 안에 접어 넣은 것입니다. 펜을 움직이면 ‘위치’ 타일이 펜이 몇 번째 걸음에 있는지, 그리고 그곳이 어느 칸인지 알려 줍니다. 힐베르트 곡선에서는 번호가 가까운 걸음들이 언제나 가까운 칸에 있으며, 이는 색에서 확인할 수 있습니다. 색마다 한 덩어리로 모여 있기 때문입니다. 힐베르트 곡선이 지도, 이미지 같은 이차원 데이터를 일차원 메모리에 저장하는 데 쓰이는 것도 이 때문입니다. Z-순서는 계산하기가 더 쉽습니다. 칸의 좌표가 걸음 번호의 비트를 번갈아 나누어 준 것에 지나지 않기 때문입니다. 하지만 Z-순서는 점프를 합니다. 걸음의 거의 절반이 이웃한 칸으로 가지 않습니다.
다른 모양을 채우는 곡선
flowsnake라고도 하는 고스퍼 곡선은 삼각형 격자 위에서 선분 하나를 일곱 개로 바꾸며, 프랙털 해안선을 지닌 모양인 고스퍼 섬을 채웁니다. 그 차원은 정사각형을 채우는 곡선들과 마찬가지로 2, 곧 log 7 / log √7입니다. 시에르핀스키 화살촉 곡선은 선분 하나를 길이가 절반인 선분 세 개로 바꿉니다. 이 곡선은 결코 넓이를 채우지 못하고 시에르핀스키 삼각형에 점점 가까워지며, 차원은 log 3 / log 2 ≈ 1.585로 선과 면의 사이입니다.
자주 묻는 질문
선이 어떻게 정사각형을 채울 수 있나요?
어느 한 레벨만으로는 채우지 못합니다. 모든 레벨은 길이는 있고 넓이는 없는 평범한 선입니다. 하지만 레벨이 거듭될수록 선은 자리를 잡아 갑니다. 선을 따라 일정한 비율만큼 간 곳에 있는 점은 레벨이 바뀔 때마다 점점 덜 움직이고, 모든 레벨의 극한은 정사각형의 모든 점을 지나는 연속 곡선이 됩니다. 주세페 페아노는 1890년에 그런 곡선이 존재함을 증명해 당대의 수학자들을 놀라게 했습니다.
곡선은 모든 점을 정확히 한 번씩 지나나요?
각 레벨은 그 격자의 모든 칸을 정확히 한 번씩 지납니다. 그러나 극한 곡선은 정사각형의 일부 점을 두 번 이상 지날 수밖에 없습니다. 1879년에 오이겐 네토가 선을 정사각형 위로 연속이면서 동시에 일대일로 대응시킬 수는 없음을 증명했기 때문입니다. 힐베르트 곡선은 일부 점을 두 번, 세 번 또는 네 번 지납니다.
힐베르트 곡선과 Z-순서는 어떻게 다른가요?
둘 다 격자의 칸들을 긴 한 줄로 늘어놓습니다. 힐베르트 곡선은 언제나 이웃한 칸으로 나아가므로, 줄에서 가까운 칸들은 격자에서도 가깝습니다. Z-순서는 두 좌표의 비트를 번갈아 끼워 넣기만 하면 되어 계산이 더 빠르지만, 걸음의 거의 절반이 점프이고 그중 일부는 정사각형 전체를 가로지릅니다. ‘길이’ 타일이 점프의 수를 셉니다.
공간 채움 곡선은 어디에 쓰이나요?
이차원 데이터를 이웃을 가까이 두는 일차원 순서로 늘어놓는 데 쓰입니다. 데이터베이스와 지도 서비스는 힐베르트 곡선을 따라, 또는 Z-순서로 장소를 색인하고, 이미지 프로그램은 반올림 오차를 고르게 퍼뜨리기 위해 힐베르트 곡선을 따라 픽셀을 훑으며, 인터넷 주소 공간을 나타낸 지도는 관련된 주소들을 나란히 두기 위해 이 곡선을 사용합니다.
시에르핀스키 화살촉 곡선은 왜 정사각형을 채우지 못하나요?
선분 하나를 길이가 절반인 조각 세 개로만 나누기 때문입니다. 넓이를 채우려면 네 개가 필요합니다. 이 곡선은 넓이가 없고 차원이 log 3 / log 2 ≈ 1.585인 모양, 시에르핀스키 삼각형에 점점 가까워집니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동