Interactive focus maps using least-squares optimization
Interactive focus maps using least-squares optimization
复制标题
DOI：
10.1080/13658816.2014.887718
复制
发表时间：
2014-10
影响因子：
5.7
通讯作者：
Thomas C. van Dijk;J. Haunert
中科院分区：
文献类型：
--
作者：
Thomas C. van Dijk;J. Haunert
我们提出了一种新的算法，在不从地图中删除非焦点(即上下文)网络部分或改变地图大小的情况下，扩大给定网络地图中的焦点区域。在制图中，这个问题通常是通过鱼眼投影来解决的，然而，这会带来严重的失真。我们的新算法将失真降到最低，并且与现有算法相比，产生的结果具有类似的质量。与现有算法相比，新算法具有较高的实时性，可以应用于交互式系统。我们的目标是这样的应用：用户通过刷动网络部分来设置焦点，或者焦点区域被定义为移动用户的邻居。该算法的一个关键特征是它能够避免不想要的边缘交叉。基本上，我们首先解决一个没有约束的最小二乘优化问题，以避免边交叉。然后，我们找到的解决方案用于确定无交叉解决方案所需的一小部分约束，除此之外，还允许我们在找到最终的无交叉解决方案之前开始放大焦点区域的动画。此外，记忆算法初始运行中的非交叉约束允许我们在任何进一步运行时获得更好的运行时间-假设焦点区域在两个连续运行之间不会移动太多。正如我们在真实世界数据上的实验所表明的那样，这使得响应时间远远低于1秒。
We present a new algorithm that enlarges a focus region in a given network map without removing non-focus (i.e., context) network parts from the map or changing the map’s size. In cartography, this problem is usually tackled with fish-eye projections, which, however, introduce severe distortion. Our new algorithm minimizes distortion and, with respect to this objective, produces results of similar quality compared to an existing algorithm. In contrast to the existing algorithm, the new algorithm achieves real-time performance that allows its application in interactive systems. We target applications where a user sets a focus by brushing parts of the network or the focus region is defined as the neighborhood of a moving user. A crucial feature of the algorithm is its capability of avoiding unwanted edge crossings. Basically, we first solve a least-squares optimization problem without constraints for avoiding edge crossings. The solution we find is then used to identify a small set of constraints needed for a crossing-free solution and, beyond this, allows us to start an animation enlarging the focus region before the final, crossing-free solution is found. Moreover, memorizing the non-crossing constraints from an initial run of the algorithm allows us to achieve a better runtime on any further run – assuming that the focus region does not move too much between two consecutive runs. As we show with experiments on real-world data, this enables response times well below 1 second.