基于空间分解和多叉树的路径连通方法

本发明提供一种基于空间分解和多叉树的路径连通方法，属于电子设计自动化领域。该方法确定主轴和交叉轴方向并为每个导线节点设置连接计数；以布线障碍为分割依据沿交叉轴方向递归分割路径空间，构建由安全区节点和分割节点组成的空间分割树；对安全区节点内的导线节点执行包括正向跳跃和反向顺序阶段的蛇形串接形成子链；对各分割节点利用开放空间内的导线节点将子链依次桥接，若桥接失败则将子节点上推至父节点并释放开放空间内的导线节点重新调度桥接；最后将子链依次拼接形成完整连通链。本发明能有效将一维平行导线无环、无开路且自动避障地串接为连续电气通路。