(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210656175.2 (22)申请日 2022.06.10 (71)申请人 北京优锘科技有限公司 地址 100015 北京市朝阳区酒仙桥路10号 82幢一层10 5室 (72)发明人 潘振兴　谢帅　 (74)专利代理 机构 北京安度修典专利代理事务 所(特殊普通 合伙) 11424 专利代理师 杨方成　马欢萍 (51)Int.Cl. G06F 16/2455(2019.01) (54)发明名称 一种确定多边形的方法、 装置、 电子设备及 存储介质 (57)摘要 本申请实施例提供了一种确定多边形的方 法， 包括： 根据针对已有多 边形的操作 指令， 确定 数据发生变化的第一多边形和第一外围多边形； 基于第一多边形和第一外围多边形所拥有的顶 点和边， 利用基于DCEL生成多边形的算法得到第 二多边形， 在判断第二多边形是否包含已有的外 围多边形后， 删除第二多边形， 并将第二多边形 包含已有外围多边形的外围多边形合并至第一 外围多边形； 将合并后的第一外围多边形的边和 顶点合并到预处理后的边和顶 点中， 并利用上述 算法得到第三多边形和第三外围多边形； 基于已 有多边形、 第三多边形对第一多边形进行筛选删 除； 从第三外围多边形中删除包含已有外围多边 形的外围多边形； 删除合并后的第一外围多边 形。 权利要求书2页 说明书13页 附图10页 CN 115048414 A 2022.09.13 CN 115048414 A 1.一种确定多边形的方法， 其特 征在于， 包括： 根据针对已有多边形的操作指令， 确定数据发生变化的第一多边形和第一外围多边 形， 其中， 一个外围多边形为 一个或者多个相连多边形以外的所有区域； 将所述第一多边形和所述第 一外围多边形所拥 有的顶点和边进行预处理， 将预处理后 的顶点和边利用基于双向边链 表DCEL生成多边形的算法得到第二多边形； 判断所述第二多边形是否包含已有的外围多边形， 删除所述第二多边形， 并将包含已 有外围多边形的外围多边形合并至所述第一外围多边形中； 将合并后的第一外围多边形的边和顶点， 分别合并到预处理后的边和顶点中， 并进行 去重后， 利用基于DC EL生成多边形的算法得到第三多边形和第三外围多边形； 基于所述已有 多边形、 所述第三多边形对所述第一多边形进行筛 选删除； 从所述第三外围多边形中删除所述包 含已有外围多边形的外围多边形； 删除合并后的第一外围多边形。 2.根据权利要求1所述的方法， 其特征在于， 若所述操作指令为修改一个或多个顶点的 位置， 在确定数据发生变化的第一多边形和第一外围多边形之前， 所述方法还 包括： 确定被修改顶点所在的边与已有 多边形的边重 叠及相交的点； 基于确定的点创建新 边， 并删除被修改顶点所在的边后统计顶点和边； 其中， 所述确定数据发生变化的第一多边形和第一外围多边形， 包括： 将产生事件的顶点或边所在的多边形及外围多边形， 确定为所述第 一多边形和所述第 一外围多边形。 3.根据权利要求1所述的方法， 其特征在于， 若所述操作指令为添加一条边， 在确定数 据发生变化的第一多边形和第一外围多边形之前， 所述方法还 包括： 确定新添加的边与已有 多边形的边重 叠及相交的点； 基于确定的点创建新 边， 并删除所述 新添加的边后统计顶点和边； 其中， 所述确定数据发生变化的第一多边形和第一外围多边形， 包括： 将产生事件的顶点或边所在的多边形及外围多边形， 确定为所述第 一多边形和所述第 一外围多边形。 4.根据权利要求2或3所述的方法， 其特征在于， 所述产生事件的顶点或边包括以下至 少一项： 位置发生变化的顶点； 被删除的顶点； 被删除的边； 添加的一条新 边； 所连接的边发生变化的顶点。 5.根据权利要求1 ‑3中任一项所述的方法， 其特 征在于， 所述方法还 包括： 基于统计的顶点和边， 对所述第 一多边形和所述第 一外围多边形所拥 有的顶点和边进 行去重， 得到预处 理后的顶点和边。 6.根据权利要求1 ‑3中任一项所述的方法， 其特征在于， 所述基于所述已有多边形、 所 述第三多边形对所述第一多边形进行筛 选删除， 包括： 基于所述已有 多边形， 从所述第一多边形中筛 选出数据没有发生变化的第四多边形；权　利　要　求　书 1/2 页 2 CN 115048414 A 2从所述第三多边形中筛 选出与所述第一多边形不同的第五多边形； 从所述第五多边形中筛 选出不包 含所述第四多边形的第六多边形； 从所述第三多边形中删除不是 所述第六多边形的多边形； 从所述第一多边形中删除包 含所述第六多边形的多边形。 7.一种确定多边形的方法， 其特 征在于， 包括： 根据针对已有多边形删除顶点或边的操作指令， 确定数据发生变化的第 一多边形和第 一外围多边形， 其中， 一个外围多边形为 一个或者多个相连多边形以外的所有区域； 将所述第一多边形和所述第 一外围多边形所拥 有的顶点和边， 进行预处理后的顶点和 边， 利用双向边链 表DCEL算法得到第二多边形和第二外围多边形； 删除所述第一多边形和所述第一外围多边形， 并且遍历已有外围多边形， 删除被所述 第二外围多边形包 含的已有外围多边形。 8.一种确定多边形的装置， 其特 征在于， 包括： 确定模块， 用于根据针对已有多边形的操作指令， 确定数据发生变化的第一多边形和 第一外围多边形， 其中， 一个外围多边形为 一个或者多个相连多边形以外的所有区域； 处理模块， 用于将所述第一多边形和所述第一外围多边形所拥有的顶点和边， 进行预 处理后的顶点和边， 利用基于DC EL生成多边形的算法得到第二多边形； 还用于判断所述第二多边形是否包含已有的外围多边形， 删除所述第二多边形， 并将 包含已有外围多边形的外围多边形合并至所述第一外围多边形中； 还用于将合并后的第一外围多边形的边和顶点， 分别合并到预处理后的边和顶点中， 并进行去重后， 利用基于DC EL生成多边形的算法得到第三多边形和第三外围多边形； 还用于基于所述已有 多边形、 所述第三多边形对所述第一多边形进行筛 选删除； 还用于从所述第三外围多边形中删除所述包 含已有外围多边形的外围多边形； 还用于删除合并后的第一外多边形。 9.一种电子设备， 包括存储器、 处理器及存储在存储器上的计算机程序， 其特征在于， 所述处理器执行所述计算机程序以实现权利要求1 ‑7任一项所述方法的步骤。 10.一种计算机可读存储介质， 其上存储有计算机程序， 其特征在于， 所述计算机程序 被处理器执行时实现权利要求1 ‑7任一项所述的方法的步骤。权　利　要　求　书 2/2 页 3 CN 115048414 A 3