A solution to line routing problems on the continuous plane

摘要: This paper discusses a new line-routing algorithm. The algorithm has been programmed in FORTRAN II for the IBM 7094 and IV 360/65. It given good results when applied to many problems such as mazes, printed circuit boards, substrates, PERT diagrams. main advantages of this algorithm, which is based on continuous plane, over conventional algorithms discrete plane are twofold: 1. Since there theoretically no limit degree precision used describe position points. In practice, only factor restricting magnitude largest (or smallest) number may be stored computer. As result, nodes board, example, can input with mil accuracy. If feat were accomplished by existing methods 9×9 inch matrix 81,000,000 cells would have (and searched) 2. stores line segments; therefore find path, segments that currently defined need investigated. Usually methods, every cell lies possible minimal path must net result much faster than method.