Z차 곡선

Z-order curve
Z 곡선 또는 Z 차수와 혼동하지 마십시오.
Z 차수 곡선의 4회 반복.
Z-차 곡선 반복이 3차원으로 확장되었습니다.

수학 해석 및 컴퓨터 공학에서, Z차, 르베그 곡선, 모튼 공간 채우기 곡선,[1] 모튼 순서 또는 모튼 코드인 함수는 데이터 포인트의 인접성을 유지하면서 다차원 데이터를 1차원으로 매핑합니다.1904년 연구한[2] 앙리 르베그(Henri Lebesgue)의 이름을 따 프랑스에서는,[3] 1966년 처음으로 순서 부여 명령을 적용한 가이 맥도널드 모튼(Guy Macdonald Morton)의 이름을 따왔다.다차원 점의 z 값은 해당 좌표 값의 이진 표현을 인터리브하여 계산됩니다.데이터가 이 순서로 정렬되면 이진 검색 트리, B-트리, 건너뛰기 목록 또는 (낮은 유효 비트가 잘린) 해시 테이블과 같은 모든 1차원 데이터 구조를 사용할 수 있습니다.결과 순서는 쿼드트리 또는 옥트리의 깊이 우선 트래버스에서 얻을 수 있는 순서라고 할 수 있습니다.

좌표값

z 값 2479의 인터리브 비트에서 Z 순서 곡선(x,y) 좌표 계산

아래 그림은 정수 좌표가 0 x x 7 7, 0 y y 7 7인 2차원 케이스의 Z 값을 보여줍니다(10진수 및 이진수 모두 표시).이진 좌표 값(x비트(파란색)에서 오른쪽으로 시작하고 y비트(빨간색)에서 왼쪽으로 번갈아 가면서)을 인터리브하면 이진 z 값(그림과 같이 45° 기울어짐)이 생성됩니다.z 값을 숫자 순서로 연결하면 Z 모양의 곡선이 반복적으로 생성됩니다.2차원 Z 값은 쿼드키 값이라고도 합니다.

Z-curve45.svg

x 좌표의 Z 값은 Moser-de Bruijn 시퀀스의 이진수로 설명되며, 짝수 위치에만 0이 아닌 비트가 있습니다.

x [ ] = { 0b0000, 0b000001, 0b000100, 0b000101, 0b010001, 0b0101, 0b0101}

두 x 값의 합과 차이는 비트 연산을 사용하여 계산됩니다.

x[i+j] = ((x[i] 0b10101) + x[j] & 0b0101 x[i-j] = ((x[i] & 0b010101) - x[j]) & 0b010101 (i=0101)

이 속성을 사용하여 Z 값을 오프셋할 수 있습니다. 예를 들어 2차원에서 현재 Z 값 z에서 위쪽(y 감소), 아래쪽(y 증가), 왼쪽(x 감소) 및 오른쪽(x 증가) 좌표는 다음과 같습니다.

상단 = ((z & 0b10101) - 1) & 0b10101) 하단 = ((z 0b010101) + 1) & 0b10101010101) 좌측 = ((z & 0b010101) & 0b1010101) & 0b10101 z (z & 0b0101)

그리고 일반적으로 2차원 Z 값 w와 z를 추가합니다.

합계 = ((z 0b1010) + (w & 0b0101) & 0b010101) (z 0b010101) + (w & 0b1010) & 0b10101010)

4중 및 8중 트리를 효율적으로 구축

Z 순서를 사용하면 일련의 [4][5]포인트에 대해 쿼드 트리(2D) 또는 옥트리(3D)를 효율적으로 구축할 수 있습니다.기본 개념은 입력 세트를 Z 순서에 따라 정렬하는 것입니다.정렬된 포인트는 바이너리 검색 트리에 저장하여 [6]선형 쿼드트리라고 불리는 직접 사용하거나 포인터 기반 쿼드트리를 구축하는 데 사용할 수 있습니다.

입력점은 일반적으로 단위 범위 [0, 1]에 대한 고정점 표현으로 또는 기계어 크기에 해당하는 양의 정수로 각 차원에서 축척됩니다.두 표현 모두 동일하며 0이 아닌 가장 높은 순서의 비트를 일정한 시간 내에 찾을 수 있습니다.쿼드트리 내의 각 정사각형은 2의 거듭제곱인 변 길이와 변 길이의 배수인 코너 좌표를 가진다.두 점을 지정하면 두 점에 대한 파생 제곱은 두 점을 모두 포함하는 가장 작은 제곱입니다.각 점의 x 및 y 성분에서 비트가 인터리빙되는 것을 x와 y의 셔플이라고 하며, 더 높은 [4]차원으로 확장할 수 있습니다.

포인트는 명시적으로 비트를 인터리브하지 않고 셔플에 따라 정렬할 수 있습니다.이를 위해 각 치수에 대해 해당 치수에 대한 두 점의 배타적 또는 좌표 중 가장 유의한 비트를 조사합니다.다음으로 최상위 비트가 가장 큰 치수를 사용하여 두 점을 비교하여 셔플 순서를 결정합니다.

배타적 또는 연산은 두 좌표가 동일한 상위 비트를 마스크합니다.셔플은 상위에서 하위로 비트를 인터리브하기 때문에 가장 큰 유효비트를 가진 좌표를 식별함으로써 다른 셔플 순서로 첫 번째 비트를 식별하고 그 좌표를 사용하여 두 [7]점을 비교할 수 있습니다.이것은 다음 Python 코드에 나타나 있습니다.

방어하다 cmp_zorder(lhs, rhs) -> 부울:     "z순서를 비교합니다."""     # lhs 및 rhs 배열과 같은 인덱스의 객체를 가정합니다.     주장하다 렌(lhs) == 렌(rhs)     # 가장 중요한 차원이 포함됩니다.     메시지 = 0     # 다른 차원 위로 루프합니다.     위해서 어둡다 에 범위(1, 렌(lhs)):         # 현재 치수가 더 중요한지 확인         # 최상위 비트를 비교합니다.         한다면 less_internals(적음)(lhs[메시지] ^ rhs[메시지], lhs[어둡다] ^ rhs[어둡다]):             메시지 = 어둡다     돌아가다 lhs[메시지] < > rhs[메시지]

가장 유의한 비트가 작은지 여부를 확인하는 한 가지 방법은 각 점의 2진수 로그 바닥을 비교하는 것입니다.다음의 조작은 동등하고, 배타적 또는 [7]조작만을 필요로 하는 것으로 나타났습니다.

방어하다 less_internals(적음)(x: 인트, y: 인트) -> 부울:     돌아가다 x < > y 그리고. x < > (x ^ y)

또한 동일한 기술을 사용하여 부동 소수점 수를 비교할 수도 있습니다.그less_msb함수를 수정하여 먼저 지수를 비교합니다.그것들이 같을 때만 기준이 된다.less_msb사마귀에 [8]사용되는 기능.

포인트가 정렬되면 다음 두 가지 속성을 사용하여 쿼드 트리를 쉽게 구축할 수 있습니다.첫 번째는 쿼드트리의 정사각형에 포함된 점이 정렬된 순서로 연속된 간격을 형성한다는 것입니다.두 번째는 사각형의 두 개 이상의 하위 항목이 입력점을 포함하는 경우 사각형이 정렬된 순서로 인접한 두 점에 대해 파생된 사각형이 된다는 것입니다.

인접한 점의 각 쌍에 대해 도출된 정사각형이 계산되고 그 변의 길이가 결정된다.파생된 각 정사각형에 대해 이를 포함하는 간격은 정렬된 [4]순서대로 오른쪽과 왼쪽으로 큰 첫 번째 정사각형에 의해 경계됩니다.이러한 간격은 각각 쿼드트리의 정사각형에 대응합니다.그 결과 입력점 또는 2개 이상의 자식을 포함하는 노드만 존재하는 압축 쿼드트리가 됩니다.필요에 따라 누락된 노드를 복원하여 비압축 쿼드 트리를 구축할 수 있습니다.

포인터 베이스의 쿼드 트리를 작성하는 대신에, 포인트는 바이너리 검색 트리등의 데이터 구조내에서 소트 된 순서로 보관 유지할 수 있습니다.이를 통해 O(log n) 시간 내에 포인트를 추가 및 삭제할 수 있습니다.정렬된 두 점 세트를 병합하고 중복을 제거하여 두 개의 사분원 트리를 병합할 수 있습니다.점 위치는 정렬된 순서로 조회점 앞뒤를 검색하여 수행할 수 있습니다.쿼드 트리가 압축되어 있는 경우, 검출된 선행 노드는 압축된 대상 노드 내의 임의의 리프일 수 있습니다.이 경우 쿼리 포인트의 최소 공통 상위 항목과 [9]발견된 리프의 이전 항목을 찾아야 합니다.

범위 검색에 1차원 데이터 구조 사용

지역성은 잘 보존되지만 효율적인 범위 검색을 위해서는 데이터 구조에서 만나는 지점에서 다차원 검색 범위에 있는 다음 Z 값을 계산하는 알고리즘이 필요합니다.

BIGMIN search in a Z-order curve.svg

이 예에서 쿼리되는 범위(x = 2, ..., 3, y = 2, ..., 6)는 점 있는 직사각형으로 표시됩니다.최대 Z값(MAX)은 45입니다.이 예에서는 데이터 구조를 Z-값 방향으로 검색할 때 F = 19 값이 발생하므로 F와 MAX(영역) 사이의 간격을 검색해야 합니다.검색 속도를 높이기 위해 검색 범위에 있는 다음 Z 값 BIGMIN(이 예에서는 36)을 계산하고 BIGMIN과 MAX(굵은 값) 사이의 간격에서만 검색하므로 대부분의 해치 영역은 건너뜁니다.내림차순방향 검색은 F보다 낮은 쿼리 범위에서 가장 높은Z 값인 LITMAX와 비슷합니다.BIGMIN 문제는 처음에 언급되었고 그 해결책은 Tropf와 Herzog에 [10]나와 있다.이 솔루션은 UB-tree('GetNextZ-address')에서도 사용됩니다.접근방식은 선택된 1차원 데이터 구조에 의존하지 않기 때문에 여전히 자유로운 데이터 구조화 선택이 가능하기 때문에 균형 나무와 같은 잘 알려진 방법을 사용하여 동적 데이터를 처리할 수 있다(예를 들어 특별한 고려사항이 필요한 R-tree와 대조).마찬가지로, 이러한 독립성을 통해 기존 데이터베이스에 방법을 쉽게 통합할 수 있습니다.

선택적으로 증가 및 감소 방향으로 계층적으로 방법을 적용하면 상업 및 기술 애플리케이션 모두에서 매우 효율적인 다차원 범위 검색이 생성되며, 예를 들어 가장 가까운 이웃 탐색의 기초가 되는 절차로서 중요하다.Z-order는 상용 데이터베이스 시스템(Oracle 데이터베이스 1995,[11] Transbase 2000)에 도입된 몇 안 되는 다차원 액세스 방법 중 하나입니다.

1966년 G.M.Morton은 정적 2차원 지리 데이터베이스의 파일 시퀀싱을 위한 Z-order를 제안했습니다.영역 데이터 단위는 크기와 오른쪽 하단 모서리 Z 값으로 표시되는 하나 또는 몇 개의 2차 프레임에 포함되며, 모서리 위치의 Z 차수에 따른 크기입니다.인접 프레임으로의 변경은, 1개 또는 [citation needed]몇개의 비교적 작은 스캔 스텝으로 행해집니다.

관련 구조

대안으로 힐버트 곡선은 더 나은 질서 보존 행동을 [5]가지며, 실제로 최적화된 지수인 [13]S2-기하학에 사용되었다.

적용들

x+ { 및 {\ y의 덧셈 테이블은 모두 Moser-de Bruijn 시퀀스에 속하며 합계를 숫자 순서로 연결하는 Z-차 곡선입니다.

선형 대수

행렬 곱셈을 위한 Strassen 알고리즘은 행렬을 4개의 블록으로 분할한 후 이들 각 블록을 4개의 작은 블록으로 재귀적으로 분할하여 블록이 단일 요소가 될 때까지(또는 보다 실용적으로: 행렬이 너무 작아서 Moser-de Bruijn 시퀀스 사소한 알고리즘이 더 빠를 때까지)를 기반으로 합니다.매트릭스 요소를 Z순으로 배열하면 로컬리티가 향상되고 2개의 블록을 곱하는 서브루틴이 매트릭스의 총 크기를 알 필요가 없으며 블록의 크기와 메모리 내 위치만 알 필요가 있다는 장점이 있습니다.Strassen 곱셈과 Z 차수의 효과적인 사용은 Valsalam과 Skjellum의 2002년 [14]논문을 참조하십시오.

Bulucc 등은 Z가 병렬 행렬-벡터 [15]곱셈을 가능하게 하기 위해 0이 아닌 요소를 정렬하는 희박한 행렬 데이터 구조를 제시한다.

텍스처 매핑

일부 GPU는 텍스처 맵 래스터라이제이션 중에 참조의 공간적 인접성을 높이기 위해 텍스처 맵을 Z 순서로 저장합니다.이를 통해 캐시 라인이 직사각형 타일을 나타낼 수 있으므로 캐시에 근접한 액세스가 있을 가능성이 높아집니다.또한 대규모로 SDRAM/DDRAM에서 비용이 많이 드는 이른바 "페이지 분할"(행 변경 비용)의 확률도 감소합니다.3D 렌더링에는 임의 변환(회전, 스케일링, 원근법 및 애니메이션 표면에 의한 왜곡)이 수반되기 때문에 이는 중요합니다.

이러한 형식은 종종 스위즐드 텍스처 또는 트위들드 텍스처라고 불립니다.다른 타일 형식도 사용할 수 있습니다.

N체 문제

반즈 씨-Hut 알고리즘에서는 옥트리의 구축이 필요합니다.데이터를 포인터 기반 트리로 저장하려면 깊이 우선 순위(분산 메모리 시스템에서는 비용이 많이 든다)로 옥트리를 반복하기 위해 많은 순차 포인터 디렉터가 필요합니다.대신 데이터를 Oct-tree 해시를 사용하여 해시 테이블에 저장하는 경우 Z 순서 곡선은 자연스럽게 깊이 우선 [5]순서로 Oct-tree를 반복합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ "Discrete Global Grid Systems Abstract Specification" (PDF). Open Geospatial Consortium. 2017.
  2. ^ Dugundji, James (1989), Wm. C. Brown (ed.), Topology, Dubuque (Iowa), p. 105, ISBN 0-697-06889-7
  3. ^ Morton, G. M. (1966), A computer Oriented Geodetic Data Base; and a New Technique in File Sequencing (PDF), Technical Report, Ottawa, Canada: IBM Ltd.
  4. ^ a b c 를 클릭합니다Bern, M.; Eppstein, D.; Teng, S.-H. (1999), "Parallel construction of quadtrees and quality triangulations", Int. J. Comput. Geom. Appl., 9 (6): 517–532, CiteSeerX 10.1.1.33.4634, doi:10.1142/S0218195999000303.
  5. ^ a b c Warren, M. S.; Salmon, J. K. (1993). "A parallel hashed Oct-Tree N-body algorithm". Proceedings of the 1993 ACM/IEEE conference on Supercomputing - Supercomputing '93. Portland, Oregon, United States: ACM Press: 12–21. doi:10.1145/169627.169640. ISBN 978-0-8186-4340-8.
  6. ^ 를 클릭합니다Gargantini, I. (1982), "An effective way to represent quadtrees", Communications of the ACM, 25 (12): 905–910, doi:10.1145/358728.358741, S2CID 14988647.
  7. ^ a b 를 클릭합니다Chan, T. (2002), "Closest-point problems simplified on the RAM", ACM-SIAM Symposium on Discrete Algorithms.
  8. ^ Connor, M.; Kumar, P (2009), "Fast construction of k-nearest neighbour graphs for point clouds", IEEE Transactions on Visualization and Computer Graphics (PDF)
  9. ^ Har-Peled, S. (2010), Data structures for geometric approximation (PDF)
  10. ^ 를 클릭합니다Tropf, H.; Herzog, H. (1981), "Multidimensional Range Search in Dynamically Balanced Trees" (PDF), Angewandte Informatik, 2: 71–77.
  11. ^ 를 클릭합니다Gaede, Volker; Guenther, Oliver (1998), "Multidimensional access methods" (PDF), ACM Computing Surveys, 30 (2): 170–231, CiteSeerX 10.1.1.35.3473, doi:10.1145/280277.280279, S2CID 7075919.
  12. ^ 를 클릭합니다Ramsak, Frank; Markl, Volker; Fenk, Robert; Zirkel, Martin; Elhardt, Klaus; Bayer, Rudolf (2000), "Integrating the UB-tree into a Database System Kernel", Int. Conf. on Very Large Databases (VLDB) (PDF), pp. 263–272, archived from the original (PDF) on 2016-03-04.
  13. ^ "S2 Geometry".
  14. ^ Vinod Valsalam, Anthony Skjellum:계층적 추상화, 알고리즘 및 최적화된 로우 레벨 커널에 기반한 고성능 매트릭스 곱셈 프레임워크.동시성과 계산: 연습과 경험 14 (10) : 805-839 (2002) [1][2]
  15. ^ Buluç, Aydın; Fineman, Jeremy T.; Frigo, Matteo; Gilbert, John R.; Leiserson, Charles E. (2009). Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks (PDF). ACM Symp. on Parallelism in Algorithms and Architectures. CiteSeerX 10.1.1.211.5256.

외부 링크