一种面向TIN构建的Peano排序方法

摘要

本发明涉及一种面向TIN构建的Peano排序方法，包括如下步骤：读入待排序的二维点集P；分解点集P为三个子点集，以调整点集P内点的存储顺序；依次分解三个子点集，以调整子点集内点的存储顺序；判断每个子点集是否分解完毕；等待所有子点集分解结束，即完成点集的Peano排序。本发明的方法能够直接根据点集的坐标来对点集进行Peano排序，从而摆脱对网格的依赖，能够有效地解决TIN构建过程中点集的Peano排序问题，大大减少了不必要的计算开销，进而提高TIN构建的算法效率。

主权项

一种面向TIN构建的Peano排序方法，其特征在于，包括以下步骤：(1)读入待排序的二维点集P＝{p_i，i∈[0，n)}，包括n个点的X坐标和Y坐标，定义点集在坐标轴上的排序方向：升序Asc和降序Des，设初始点集P在X轴上的排序方向D_x为升序Asc，在Y轴上的排序方向D_y为升序Asc；(2)分解点集P以调整点集P内点的存储顺序：将点集P分为三部分：P₁、P₂和P₃，具体过程为：计算点集P的X坐标数和X坐标数利用和调整点集P内点的存储顺序，以满足如下条件：如果排序方向D_x是升序Asc，如果排序方向D_x是降序Des，此时，设(3)分解点集P₁以调整点集P₁内点的存储顺序：将点集P₁分为三个子点集：P₁₁、P₁₂和P₁₃，具体过程为：计算点集P₁的Y坐标数和Y坐标数利用和调整点集P₁内点的存储顺序，以满足如下条件：如果排序方向D_y是升序Asc，如果排序方向D_y是降序Des，此时，设(4)分解点集P₂以调整点集P₂内点的存储顺序：将点集P₂分为三个子点集：P₂₁、P₂₂和P₂₃，具体过程为：计算点集P₂的Y坐标数和Y坐标数利用和调整点集P₂内点的存储顺序，以满足如下条件：如果排序方向D_y是升序Asc，如果排序方向D_y是降序Des，此时，设(5)分解点集P₃以调整点集P₃内点的存储顺序：将点集P₃分为三个子点集：P₃₁、P₃₂和P₃₃，具体过程为：计算点集P₃的Y坐标数和Y坐标数利用和调整点集P₃内点的存储顺序，以满足如下条件：如果排序方向D_y是升序Asc，如果排序方向D_y是降序Des，此时，设(6)对于步骤(2)、(3)、(4)和(5)中分解得到的子点集P₁₁、P₁₂、P₁₃、P₂₁、P₂₂、P₂₃、P₃₁、P₃₂和P₃₃，逐个判断其中包含的点数是否大于1，如果是，则说明该子点集需要继续分解，以该子节点作为输入点集P，递归执行步骤(2)、(3)、(4)和(5)，其中每个子点集的划分方向，依次为：(D_x，D_y)、(！D_x，D_y)、(D_x，D_y)、(D_x，！D_y)、(！D_x，!D_y)、(D_x，!D_y)、(D_x，D_y)、(！D_x，D_y)、(D_x，D_y)，括号中！表示对排序方向取反方向；(7)等待所有子点集分解结束，即完成点集的Peano排序。