You need to enable JavaScript to run this app. 基于已知线段端点与交点坐标的图像多quad拆分方案咨询
优惠活动
大模型
产品
解决方案
定价
更多

基于已知线段端点与交点坐标的图像多quad拆分方案咨询

相邻四边形拆分的稳定实现方案

前置数据规整(替代全量遍历的基础)

先把三类原始数据全部转成可快速查询的结构化映射,彻底消弭多层循环的性能问题:

  • 对所有输入坐标(端点1、端点2、相交角点)设置统一容差(匹配实际采集的坐标误差范围,比如1~2像素对应的坐标差),做量化哈希生成唯一点ID:把容差范围内的所有浮点坐标映射到同一个整数ID,存成全局point_id_map。后续所有坐标邻近判断全部转为查字典的O(1)操作,不用在循环里反复算距离。
  • 构建点到线段的反向索引:遍历所有原始线段,无需区分端点1、端点2的顺序,直接把每条线段的两个端点通过point_id_map转成唯一ID,生成adj_seg字典——键是点ID,值是所有以该点为端点的线段ID列表。
  • 做一次原子边校验:对照已采集的所有相交角点,把所有跨角点的长线段切分成最小的、两端都是角点的独立短边(也就是原子边),从根源上消除共线判断的额外计算。

四边形单元提取(替代逐点凑顶点的错误逻辑)

核心思路是靠平面网格的边邻接关系走闭合环,不要逐个点匹配拼凑顶点:

  • 给每条原子边维护邻接标记:初始状态下所有边的邻接Quad标识为空,代表还没有被归属到任何单元。
  • 从任意一条未被标记的边出发,沿着连续的原子边走闭合环:
    • 取边e1连接P1-P2,在P2点查adj_seg的邻接边列表,排除往回走到P1的反向边,选择和e1方向夹角最小的邻接边e2,走到P3。
    • 重复上述过程:到每个当前点,排除回退的上一条边,沿最小转向的邻接边前进,直到回到起点P1,形成完整闭合环。
    • 判断环的边数:如果是4条边,就是目标独立Quad,把环上的所有边标记为当前Quad的ID,避免后续重复遍历。

异常修正

  • 如果走出来的闭合环边数不是4,两种处理方式:如果是整个图形的最外边界环,直接跳过不纳入Quad结果;如果是内部环,说明量化容差设置不对,调整后重新生成point_id_map即可。
  • 整个流程的遍历次数和总原子边数线性相关,不存在多层嵌套循环,计算效率远高于原有方案,也不会出现因为顶点匹配错位把相邻四边形的边混进来的问题。

内容的提问来源于stack exchange,提问作者Hai Luu

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.02 02:06:04