用于交互制图的快速边路由

摘要

一种用于交互制图的快速边路由的方法和系统。此处描述了使用空间分解来获得更快速路由并采用锥形生成器来更快生成稀疏可视性图的边路由系统。该系统提供使用近似最短路径的两种可单独或结合使用的方法来实现更快并由此更可伸缩和更具有交互性的边路由。第一种方法使用对图中节点的空间分解，稍微移动它们以得到围绕各组节点的严格脱节的凸壳，然后在这些合成壳而不是诸单个节点上计算可视性图。第二种方法生成一个稀疏的可视性图生成器来加速生成可视性图的过程。对于交互式制图应用程序中的大型图，该系统允许高品质的避障的边路由，在该交互式制图应用中采用了非常快的路由刷新并伴有许多节点同时移动。

主权项

一种用于在制图应用程序中对图进行快速边路由的计算机实现的方法，所述方法包括：接收(210)要对其各边进行路由以避开各节点的节点布局；在所接收到的节点布局上执行(220)空间分解，以减少在每个连接的节点对之间进行路由期间内所需要考虑的障碍物的数量，其中执行空间分解包括：创建容纳所接收到的图布局中的每个节点的树；在创建所述树之后，移动节点以去除节点形状之间的重叠；基于所创建的树中的一个或多个节点组来计算一个或多个凸壳；以及选择用于在所述树中的每个叶节点对之间进行路由的凸壳；其中所述空间分解包括：基于减少后的障碍物数量产生(230)可视性图；根据所产生的可视性图来路由(240)所述边以避开所述节点；以及基于所述节点布局以及所确定的边的路由来呈现(260)所述图以便在所述制图应用程序的用户界面中向用户显示所述节点和边，其中以上步骤由至少一个处理器来执行。