一种基于三角拓展的哈密顿路径快速搜索方法专利查询专利号|摘要-满商公司网

一种基于三角拓展的哈密顿路径快速搜索方法

基本信息

申请号	CN202111033680.3	申请日	-
公开（公告）号	CN113554120A	公开（公告）日	2021-10-26
申请公布号	CN113554120A	申请公布日	2021-10-26
分类号	G06K9/62（2006.01）I	分类	计算；推算；计数;
发明人	司马晓;魏金占;陈小祥;刘荷蕾;吴瑞;纪宏	申请（专利权）人	深圳市城市规划设计研究院股份有限公司
代理机构	广西中知科创知识产权代理有限公司	代理人	吴震辉
地址	518000广东省深圳市福田区振兴路3号建艺大厦10楼
法律状态	-

摘要

本发明涉及计算机图形学与地理信息科学领域，具体公开了一种基于三角拓展的哈密顿路径快速搜索方法，包括以下步骤：S1、获取节点样本数据；S2、构建泰森多边形网络；S3、搜索任意相邻两个泰森多边形，并用连线连接搜索的两个泰森多边形内的节点；S4、搜索任意一个同时邻接两个基准多边形的泰森多边形；S5、将初始连线的两个节点分别连接搜索到的泰森多边形内的节点，以得到一个三角形；S6、删除三角形的初始连线，并以剩余的两条连线作为初始连线，返回步骤S4；S7、重复步骤S4‑S6，直至搜索完成所有节点。本发明的一种基于三角拓展的哈密顿路径快速搜索方法，原理简单，能够有效降低处理的难度、成本和时间，提高求解效率。