近实时计算曲面区域标签(Human-Computer Interaction)

• 2020 年 1 月 14 日
• 筆記

在标记区域中的一个问题就出现在放置一个地理区域的标签之后。给定区域的外边界和一组可选的孔。我们的目标是找到一个标签位置，使标签跨越该区域，并符合其形状。

2001年Barrault在这一领域的最新研究提出了一种基于曲线支撑线的标签位置计算算法。他的解决方案有一些缺点，因为他正在评估许多非常简单的解决方案。此外，由于性能问题，他需要限制搜索空间，因此可能会错过一些有趣的解决方案。

我们提出了一个解决方案，评估搜索空间更广泛和更有效。为此，我们计算多边形的骨架。对骨架进行修剪，以便删除边界多边形附近的边。在这样修剪的骨架中，我们选择一组candi- date路径作为图的最长的不同的子路径。根据这些候选项计算标签支持线和评估标签位置。

原文题目：Computing Curved Area Labels in Near-Real Time

原文：IntheAreaLabelingProblemoneisafterplacingthelabelof a geographic area. Given the outer boundary of the area and an optional set of holes. The goal is to find a label position such that the label spans the area and is conform to its shape.

The most recent research in this field from Barrault in 2001 proposes an algorithm to compute label placements based on curved support lines. His solution has some drawbacks as he is evaluating many very simi- lar solutions. Furthermore he needs to restrict the search space due to performance issues and therefore might miss interesting solutions.

We propose a solution that evaluates the search space more broadly and much more efficient. To achieve this we compute a skeleton of the polygon. The skeleton is pruned such that edges close to the boundary polygon are removed. In the so pruned skeleton we choose a set of candi- date paths to be longest distinct subpaths of the graph. Based on these candidates the label support lines are computed and the label positions evaluated.

原文作者：Filip Krumpe, Thomas Mendel

原文地址： https://arxiv.org/abs/2001.02938