近實時計算曲面區域標籤(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