(简单？)线图的标签放置

Question

我正在绘制高程剖面图,显示沿着轨迹的高程增益/损失,类似于下面的:

带有手工标签的样品高程剖面图http://img38.imageshack.us/img38/4079/profilewithgoodlabels.png

这基本上是一个折线图,其中x轴为起点,y轴为高程.

我想在沿着路径的有趣点提供带有点高程的花式标签,就像我手工添加到样本图像中一样.我正在寻找关于如何最好地放置这些标签的想法,以便:

• 它们彼此不重叠
• 它们与轮廓本身不重叠,或者至少这种情况以清晰的方式发生(例如,在陡峭的山谷中间可能需要它)
• 它们不会延伸到限制整体图像的框外

为了实现这些目标,我认为我可以(至少):

• 翻转文本(参见示例)
• 为领导者选择合适的长度
• 为领导者选择合适的角度(但出于美学原因,最小化变化可能是合乎需要的)
• 在拥挤的地区降低不太重要的地方的海拔高度
• 拥挤区域中的缩写名称(PlaceName我的环境中的s已经以非常好的方式支持缩写,因此从"南双山"切换到"S Twin Mtn"很容易)
• 完全在拥挤的区域删除不太重要的注释

但我不知道如何最好地构建这个算法.这似乎是一个优化问题？(最小化与注释相关的臭味,并为我试图避免的每一件事提供数字惩罚？)但是因为有很多离散变量需要优化而且我并不真正关心"最佳"解决方案(只是一个好的,最好是稳定的)我不知道该怎么做.

通常如何处理图形中的这类问题？动态编程？分支？优化理念是否偏离基础？是否有任何有用的.NET库我可能想看一下？

(我不想直接将它放到一般的图形绘制库中,因为它是整个产品的一个关键特性,我计划了一些更多自定义功能,可能很难插入通用图形绘制库)

Answer 1

我可能会放置一个标签，然后放置下一个，检查它是否与第一个标签重叠，如果是，则翻转它，如果不起作用，则向上推动它，直到它不再重叠......作为起点反正。也许添加一个成本函数作为与理想或默认放置的距离（如果没有其他标签妨碍），这将被最小化。然后找到成本最低的标签排列。可以为翻转、移动、旋转、缩写和放置赋予不同的成本。