A solution to line-routing problems on the continuous plane
A solution to line-routing problems on the continuous plane
复制标题
DOI：
10.1145/800260.809014
复制
发表时间：
1969
期刊：
影响因子：
--
通讯作者：
Dave Hightower
中科院分区：
文献类型：
--
作者：
Dave Hightower
本文讨论了一种新的线路路由算法。该算法已在 IBM 7094 的 FORTRAN II 中和 IBM 360/65 的 FORTRAN IV 中编程。当应用于迷宫、印刷电路板、基板和 PERT 图等许多线路布线问题时，它给出了良好的结果。与基于离散平面的传统算法相比，该基于连续平面的算法的主要优点有两个： 1. 由于该算法基于连续平面，因此理论上用于描述点位置的精度没有限制。实际上，限制精度的唯一因素是可以存储在计算机中的最大（或最小）数字的大小。因此，例如印刷电路板上的节点可以以百万级精度输入。如果要通过现有方法在 9×9 英寸板上实现这一壮举，则必须在计算机中存储（和搜索）81,000,000 个单元的矩阵。 2、算法只存储线段；因此，要找到路径，只需研究当前定义的段。通常使用传统方法，必须研究位于每个可能的最小路径上的每个细胞。最终结果是该算法比传统方法快得多。
This paper discusses a new line-routing algorithm. The algorithm has been programmed in FORTRAN II for the IBM 7094 and in FORTRAN IV for the IBM 360/65. It has given good results when applied to many line-routing problems such as mazes, printed circuit boards, substrates, and PERT diagrams. The main advantages of this algorithm, which is based on the continuous plane, over conventional algorithms based on the discrete plane are twofold: 1. Since the algorithm is based on the continuous plane, there is theoretically no limit to the degree of precision used to describe the position of points. In practice, the only factor restricting the precision is the magnitude of the largest (or smallest) number which may be stored in a computer. As a result, the nodes on a printed circuit board, for example, can be input with mil accuracy. If this feat were to be accomplished by existing methods on a 9×9 inch board, a matrix of 81,000,000 cells would have to be stored (and searched) in the computer. 2. The algorithm stores only line segments; therefore to find a path, only the segments that are currently defined need be investigated. Usually with conventional methods, every cell that lies on every possible minimal path must be investigated. The net result is that this algorithm is much faster than the conventional method.