基于并行模拟退火算法的划界线生成方法

摘要

本发明涉及划界谈判领域，提供了一种基于并行模拟退火算法的划界线生成方法，包括：将两个图层中的栅格形式的山脊线和山谷线融合到同一图层中，对融合后的图层的悬挂特征栅格进行反向追踪后进行栅格转矢量操作，得到矢量地形特征网络，遍历该矢量地形特征网络中的各地形特征线，建立各地形特征线首末端点的点-点拓扑关系；随机搜索从划界线起点到终点的点串作为初始点串；预设初始温度值，将初始点串作为初始解，开启并行模拟退火线程，完成从划界线起点到划界线终点的最优点串的搜索；对所述最优点串进行解码，得到划界线；本发明使得划界线与实际地形相吻合，且提高了最优划界线的生成速度。

主权项

一种基于并行模拟退火算法的划界线生成方法，其特征在于，所述方法包括：S1、建立实际地形的数字高程模型，并从该数字高程模型中分别提取栅格形式的山脊线和山谷线，所述栅格形式的山脊线和山谷线存储在两个图层中；S2、将所述两个图层中的栅格形式的山脊线和山谷线融合到同一图层中，得到特征图层，获取该特征图层中的所有特征栅格，所述特征栅格包括悬挂特征栅格和非悬挂特征栅格；S3、对所述特征图层中的悬挂特征栅格进行反向追踪，使得特征图层中的山脊线与山谷线相连，形成特征栅格网络；并对所述特征栅格网络进行栅格转矢量操作，得到矢量地形特征网络，该矢量地形特征网络中的各连线为地形特征线；S4、遍历所述各地形特征线，并对每一地形特征线的首末端点进行编号；根据矢量地形特征网络，建立各地形特征线首末端点的点‑点拓扑关系；S5、根据所述各地形特征线首末端点的点‑点拓扑关系，随机搜索从划界线起点到划界线终点的点串作为初始点串，所述初始点串为各端点编号的集合；S6、预设初始温度值，将所述初始点串作为初始解，开启并行模拟退火线程，以完成从划界线起点到划界线终点的最优点串的搜索；S7、对所述最优点串进行解码，得到从划界线起点到划界线终点的地形特征线的集合，将该集合中的各地形特征线首尾相连，得到划界线。