Fast edge routing for interactive diagramming
US8543944B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jun 14, 2010 |
| Grant date | Sep 24, 2013 |
| Priority date | — |
| Expiry date | Jun 12, 2031 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06T11/206
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.