| 摘要 |
An edge routing system is described herein that uses a spatial decomposition to achieve faster routing, and more quickly generates a sparse visibility graph using a cone spanner. The system provides two approaches that can be used separately or in combination to achieve faster—and hence more scalable and more interactive—edge routing using approximate shortest paths. The first approach uses a spatial decomposition of the nodes in a graph, moving them slightly to obtain strictly disjoint convex hulls around groups of nodes, and then computing visibility graphs over these composite hulls rather than individual nodes. The second approach generates a sparse visibility-graph spanner to accelerate the process of producing the visibility graph. The system allows high quality obstacle avoiding edge routing for large diagrams in interactive diagramming applications where very fast refreshes of routing are used with many nodes moving at the same time.
|
