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

摘要

本发明涉及一种面向TIN构建的Hilbert排序方法。该方法包括：(1)读入待排序的二维点集P；(2)分解点集P以调整点集P内点的存储顺序；(3)分解点集P_W以调整点集P_W中点的存储顺序；(4)分解点集P_E以调整点集P_E中点的存储顺序；(5)判断子点集是否分解完成；(6)等待所有子点集分解结束，即完成点集的Hilbert排序。本发明利用点集分割的思想来调整点集的存储顺序，能够摆脱对网格的依赖，直接根据点集的坐标进行Hilbert排序，从而避免传统Hilbert排序方法的不足，能够有效地解决TIN构建过程中点集的Hilbert排序问题，提高了排序的效率。

主权项

一种面向TIN构建的Hilbert排序方法，其特征在于，包括以下步骤：(1)读入待排序的二维点集P＝{p_i，i∈[0，n)}，包括n个点的X坐标和Y坐标，定义点集的四个方位：西北NW、西南SW、东北NE、东南SE，设初始点集P的方位为西南SW；(2)分解点集P以调整点集P内点的存储顺序：根据初始点集P的方位，将点集P分解为两部分：P_E和P_W，具体过程为：如果点集P的方位是西南SW或东北NE，则计算点集P的X坐标中位数X_0.5，否则计算P的Y坐标中位数Y_0.5，利用中位数调整点集P内点的存储顺序，以满足如下条件：对于西南SW或者东北NE方位，$p_i.x\le X_{0.5}\le p_j.x,i\in [0,\frac{n}{2}-1],j\in [\frac{n}{2}+1,n),p\in P;$对于西北NW方位，对于东南SE方位，此时，设(3)分解点集P_W以调整点集P_W中点的存储顺序：根据点集P的方位，将点集P_W分解为两个子点集：P_NW和P_SW，具体过程为：如果点集P的方位是西南SW或东北NE，则计算点集P_W的Y坐标中位数Y_0.5；若点集P的方位是西北NW或者东南SE，则计算P_W的X坐标中位数X_0.5，利用计算出的中位数调整点集P_W内点的存储顺序，以满足以下条件：对于西南SW或者东北NE方位，$p_i.y\le Y_{0.5}\le p_j.y,i\in [0,\frac{n}{4}-1],j\in [\frac{n}{4}+1,\frac{n}{2}),p\in P;$对于西北NW方位，对于东南SE方位，此时(4)分解点集P_E以调整点集P_E中点的存储顺序：根据点集P的方位，将点集P_E分解为两个子点集：P_NE和P_SE，具体过程为：如果点集P的方位是西南SW或东北NE，则计算点集P_E的Y坐标中位数Y_0.5；若点集P的方位是西北NW或者东南SE，则计算点集P_E的X坐标中位数X_0.5，利用计算出的中位数调整点集P_E内点的存储顺序，以满足以下条件：对于西南SW或者东北NE方位，$p_i.y\ge Y_{0.5}\ge p_j.y,i\in [\frac{n}{2},\frac{3n}{4}-1],j\in [\frac{3n}{4}+1,n),p\in P;$对于西北NW方位，对于东南SE方位，此时(5)对于步骤(3)和(4)中分解得到的子点集P_NW、P_SW、P_NE和P_SE，逐个判断其中包含的点数是否大于1，如果是，则说明该子点集需要继续进行分割，分别以子点集P_NW、P_SW、P_NE和P_SE作为输入点集P，各点集方位依次为西北NW、西南SW、东北NE和东南SE，递归执行步骤(2)、(3)、(4)和(5)；否则该子点集分解完成；(6)等待所有子点集分解结束，即完成点集的Hilbert排序。