1. Foreword:
It was introduced by “Geographic Information Systems and Principles” and “Basics of Geographic Information Systems”. It seemed a bit interesting, so I wanted to implement it in C language and sort out the relevant content.
Prerequisite knowledge:
Leaf node: A node that has no child nodes.
The linear quadratic number only stores the last leaf node information, including the position, depth and grid value of the leaf node.
Address code (Morton code): Linear four-branch leaf nodes follow certain rules and imply the number of leaf node location information.
Expansion:
The 32-bit Morton code encoding method zyxzyx in the 3-dimensional space xyz, each dimension is represented by 10 bits (0~1023).
The node of the tree: contains a data element and several branches pointing to subtrees;
Child node: The root of the subtree of a node is called the child of the node;
Parent node: Node B is the child of node A, then node A is the parent of node B;
Brother nodes: nodes of children of the same parents; Cousin nodes: nodes on the same level;
Ancestor node: All nodes on the branches from the root to the node. Descendant nodes: Any node in the subtree rooted at a node is called a descendant of the node.
Node level: The level of the root node is defined as 1; the children of the root are the second level nodes, and so on;
Tree depth: the largest node level in the tree
Degree of node: the number of node subtrees
Degree of tree: The maximum node degree in the tree.
Leaf node: also called terminal node, it is a node with degree 0;
Branch node: a node whose degree is not 0;
Ordered tree: A tree with ordered subtrees, such as a family tree;
Unordered tree: the order of subtrees is not considered;
2. Basic principles:
Two methods:
There are two different solutions based on the generation of quaternary Morton codes and the establishment process of quaternary numbers.
1. The top-down splitting method gradually generates Morton codes in the process of establishing quadratic numbers;
2. First calculate the Morton code of each grid, and then merge it from bottom to top according to a certain scanning method to create a four-way number.
The quadratic numbers generated by bottom-up and top-down are the same, but the former is more efficient.
For the Morton code of the first method:
Step 1: Divide the sub-quadrants. The labels 0, 1, 2, and 3 represent the four sub-quadrants of the upper left, upper right, lower left, and lower right respectively.
Step 2: Perform testing and continue subdividing if necessary.
During the segmentation process, the number of digits of the label continues to increase, and this label is a Morton code.
And each digit of the Morton code is a quaternary number not greater than 3. Each time it is divided, one digit is added. The more divisions, the smaller the resulting sub-area, and the larger the corresponding Morton code value.
The Morton code value of the final node is the sum of the corresponding quadrant values of all bits, MQ=q1q2q3..qn=q1*10^(k-1) + q2*10^(k-2)… + qk
For the Morton code of the second method:
1. Convert decimal row and column numbers into binary representation
2. Based on MQ=2*Ib (binary row number) + Jb (binary column number)
3. Code implementation:
Try your skills:
Understand the quaternary Morton code:
#include<stdio.h>
#include<math.h>
//Calculate MQ value
int calculateMq(int Ib,int Jb)
{
return (2 * Ib + Jb);
}
//Calculate decimal numbers
int tenTransToTwo(int II)
{
int sum = 0;//used to store the converted binary
int n = 0;//Exponent used to convert the output form
while (II > 1)//Judge whether division by two and remainder is completed
{//Storage in reverse order
sum + = ((II % 2)*pow(10,n));
II = (II- II % 2)/2;
n + + ;
}
sum + = (II * pow(10, n));
return sum;
}
int main()
{
//Prompt user for input
printf("Please enter decimal II, JJ value\\
");
//Initialization and reading decimal numbers
int II=0;
int JJ=0;
scanf_s("%d", & amp;II);
scanf_s("%d", & amp;JJ);
//Implement binary conversion of rows and columns
printf("%d\\
", tenTransToTwo(II));
printf("%d\\
", tenTransToTwo(JJ));
//Output the quaternary Morton value (MQ value)
printf("%d\\
", calculateMq(tenTransToTwo(II), tenTransToTwo(JJ)));
return 0;
}
Output result:
Disadvantages of quaternary system:
1. The memory overhead inside and outside the code is large, and most languages do not support quaternary variables.
2. The computing efficiency is not high
Therefore, Mark et al. (1989) suggested using the decimal Morton code as the address code for linear quadratic numbers.
Experience it again:
Decimal Morton code:
Method 1:
Calculation method based on mathematical formulas
#include<stdio.h>
#include<math.h>
//Calculate MQ value
int calculateMq(int Ib, int Jb)
{
return (2 * Ib + Jb);
}
//Calculate decimal numbers
int tenTransToTwo(int II)
{
int sum = 0;//used to store the converted binary
int n = 0;//Exponent used to convert the output form
while (II > 1)//Judge whether division by two and remainder is completed
{//Storage in reverse order
sum + = ((II % 2)*pow(10, n));
II = (II - II % 2) / 2;
n + + ;
}
sum + = (II * pow(10, n));
return sum;
}
//Calculate binary numbers
int twoTransToFour(int transtedTwo)
{
int sum = 0;//used to store quaternary numbers
int n = 0;//Exponent used to convert the output form
int digit = 0;//used to temporarily store each digit;
//Follow the principle of output in reverse order and store in forward order
while(transtedTwo>0)
{
digit = transtedTwo % 2;
transtedTwo /= 2;
sum + = (digit*pow(4, n));
n + + ;
}
//return array i.e. return quaternary number
return sum;
}
int main()
{
//Prompt user for input
printf("Please enter decimal II, JJ value\\
");
//Initialization and reading decimal numbers
int II = 0;
int JJ = 0;
scanf_s("%d", & amp;II);
scanf_s("%d", & amp;JJ);
Implement binary conversion of rows and columns
//printf("Ib = %d\\
", tenTransToTwo(II));
//printf("Jb = %d\\
", tenTransToTwo(JJ));
Output the quaternary Morton value (MQ value)
//printf("The Morton code at the target is %d\\
", calculateMq(tenTransToTwo(II), tenTransToTwo(JJ)));
//Implement quaternary conversion of rows and columns
printf("Ib = %d\\
", twoTransToFour(II));
printf("Jb = %d\\
", twoTransToFour(JJ));
//Output the decimal Morton value (MQ value)
printf("The Morton code at the destination is %d\\
", calculateMq(twoTransToFour(II), twoTransToFour(JJ)));
return 0;
}
Method 2:
An algorithm based on bitwise operations. In order to simplify the use of bitwise operators, the author plans to use array simulation.
#include<stdio.h>
#include<math.h>
//Calculate decimal numbers
int tenTransToTwo(int II)
{
int sum = 0;//used to store the converted binary
int n = 0;//Exponent used to convert the output form
while (II > 1)//Judge whether division by two and remainder is completed
{//Storage in reverse order
sum + = ((II % 2)*pow(10,n));
II = (II- II % 2)/2;
n + + ;
}
sum + = (II * pow(10, n));
return sum;
}
//Calculate binary numbers
int MyBitOperator(int transtedTwo1, int transtedTwo2)
{
int sum = 0;//used to store quaternary numbers
int i=0;//Move array subscript
//Follow the principle of output in reverse order and store in forward order
int arr[8] = { 0 };//The bits used to store II and JJ, the even numbers (and 0) are the II bits, and the odd numbers are the JJ bits
while (transtedTwo1 > 0)
{
arr[0 + i] = transtedTwo1% 2;//0,2,4,6
transtedTwo1 /= 10;
i + = 2;
}
i = 0;
while (transtedTwo2 > 0)
{
arr[1 + i] = transtedTwo2 % 2;//1,3,5,7
transtedTwo2 /= 10;
i + = 2;
}
//Calculate Md
int n = 0;//Exponent used to convert the output form
for (int i = (sizeof(arr) / sizeof(arr[0]))-3; i >=0; i--)//The previous array is redundant
{
\t\t
if (arr[i] > 0) {
sum + = (arr[i] * pow(2, n));
printf("%d\\
", sum);
}
n + + ;
}
//return array i.e. return quaternary number
return sum;
}
int main() {
//Prompt user for input
printf("Please enter decimal II, JJ value\\
");
//Initialization and reading decimal numbers
int II = 0;
int JJ = 0;
scanf_s("%d", & amp;II);
scanf_s("%d", & amp;JJ);
printf("MD value is %d", MyBitOperator(tenTransToTwo(II), tenTransToTwo(JJ)));
return 0;
}
Output result:
Method 1:
Method 2:
