如何处理动态放置标签的重叠

Question

我正在 WPF 中创建一个可视化工具来显示我正在编写的游戏的流场信息，并且遇到了一些标签彼此非常接近的问题。

在上面的屏幕截图中，扇区 (0,0) 位于左上角。在扇区 (1,1) 中，我突出显示了两个带有彼此非常接近的箭头的标签。在扇区 (2,1) 中，我圈出了两个完全重叠的标签。我需要能够以某种方式放置标签，使它们不会重叠并且有一定的距离。我追求的是一种简单的算法，它允许我在竞争点上放置标签。

blue/black 单元格是 Items 控件上的虚拟化项目，canvas 作为 ItemsPanel。红色扇形正方形位于一个装饰器上，而绿线、方框、贝塞尔曲线和红色成本标签位于第二个装饰器上。两个装饰器都使用绘图上下文以及在渲染时动态创建的所有内容。

var typeface = new Typeface(new FontFamily("Segoe UI"), FontStyles.Normal, FontWeights.Normal, FontStretches.Normal);
var formattedText = new FormattedText(curve.Cost.ToString(), CultureInfo.CurrentUICulture, FlowDirection.LeftToRight, typeface, 12, Brushes.Red, null, TextFormattingMode.Display);

var textLocation = new Point(midPoint2.X - (formattedText.WidthIncludingTrailingWhitespace / 2), midPoint2.Y - formattedText.Height);
drawingContext.DrawText(formattedText, textLocation);

Answer 1

一个建议:

一组几何实体的 Voronoi 图是将平面划分为多个区域，在这些区域中，点与给定实体的距离比与所有其他实体的距离更近。

如果你构建你的曲线的 Voronoi 图，如果你把标签全部放在相应的区域，这就解决了你的问题。

假设所有标签具有相同的范围（相同的边界框），您可以通过应用 erosion 操作找到合适的空白空间，即删除所需区域轮廓上的像素层 width/height.其余像素可能是标签的中心。

在一般情况下，用几何方法计算维诺图是非常困难的。但是，如果您使用数字图像，绘制几何实体并从中计算 distance map 就足够了。

这需要您对数字图像处理技术有所了解。

Answer 2

在考虑了几种放置标签的方法之后，包括词云、基于物理的方法、voronoi 图。我决定将我的方法基于算法的实证研究对于 Point-Feature Label Placement，因为我看到了一种简单快捷的定位标签的方法。第 2 页给了我一个想法，即为所需的点设置四个可能的位置，我用非常简单的规则构建了自己的实现。

我用两种方法创建了一个名为 PointLabelPlacer 的 class 添加标签 ComputeNewPositions

我会将所有标签连同点一起发送到 AddLabel 方法。完成并准备就绪后，我将调用 ComputeNewPositions。这将针对所有四个可能的位置计算来自另一个标签的重叠位置的数量。

如果某个位置与另一个标签的原始点重叠，我也会对其进行标记。

如果两个标签完全重叠，我会再次选择第一个没有重叠的标签，但我会将所有其他标签位置标记为已使用

然后我会选择我找到的第一个重叠次数最少且没有与其他点重叠且未标记为已使用的点。

如果毕竟找不到替代位置，我默认在左上角并允许重叠。

这是以黄色显示的备用位置

这是最终结果

如何处理动态放置标签的重叠

How to handle overlapping of dynamically placed labels

c#

wpf

algorithm

label

overlap