Seeing Around Corners: Fast Orthogonal Connector Routing
Kim Marriott, Peter J Stuckey, Michael Wybrow, T Dwyer, H Purchase, A Delaney
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | SPRINGER-VERLAG BERLIN | Published : 2014
Orthogonal connectors are used in drawings of many types of network diagrams, especially those representing electrical circuits. One approach for routing such connectors has been to compute an orthogonal visibility graph formed by intersecting vertical and horizontal lines projected from the corners of all obstacles and then use an A* search over this graph. However the search can be slow since many routes are in some sense topologically equivalent. We introduce obstacle-hugging routes which we conjecture provide a canonical representative for a set of topologically equivalent routes. We also introduce a new 1-bend visibility graph that supports computation of these canonical routes. Essenti..View full abstract
Awarded by ARC through Discovery
We acknowledge the support of the ARC through Discovery Project Grants DP0987168 and DP110101390. We also thank the anonymous reviewers for their very helpful comments.