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

摘要

本发明涉及一种面向TIN构建的Morton排序方法。该方法包括：读入待排序的二维点集P；分解点集P为两部分：P_N和P_S，以调整点集P内点的存储顺序；分别分解点集P_N和P_S以调整各点集中点的存储顺序；判断子点集是否分解完成；等待所有子点集分解结束，即完成点集的Morton排序。本发明利用点集分割的思想来调整点集的存储顺序，能够摆脱对网格的依赖，直接根据点集的坐标进行Morton排序，从而避免传统Morton排序方法的不足，能够有效地解决TIN构建过程中点集的Morton排序问题，提高了排序的效率，并且由于脱离了网格的辅助，因而极大降低了算法对于内存的需求，大大减少了不必要的计算开销。

主权项

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