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

Question

我正在绘制高程剖面图，显示沿路径的高程增益/损失，类似于下面的:

Sample Elevation Profile with hand-placed labels http://img38.imageshack.us/img38/4079/profilewithgoodlabels.png

这基本上是一个折线图，x 轴为起点，y 轴为高程。

我想在路径沿线的有趣点提供带有点高程的精美标签，就像我手动添加到示例图像中的标签一样。我正在寻找有关如何最好地放置这些标签的想法，以便:

它们彼此不重叠

它们不与轮廓本身重叠，或者至少以一种干净的方式发生(例如，似乎在陡峭的山谷中间可能有必要)

它们不会超出限制整体图像的框

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

翻转文本(参见示例)

为领导选择合适的长度

为引线选择合适的角度(但出于美学原因，可能需要尽量减少变化)

降低拥挤区域中不太重要的地方的点高程

拥挤区域中的缩写名称(在我的环境中 PlaceName s 已经以非常好的方式支持缩写，因此从“South Twin Mountain”切换到“S Twin Mtn”很容易)

在拥挤的区域完全删除不太重要的注释

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

通常如何处理图形中的此类问题？动态规划？分界线？优化想法是否偏离基础？是否有任何有用的 .NET 库可供我查看？

(我不想直接将其交给通用图形绘制库，因为它是整个产品的一个关键功能，而且我计划了更多自定义功能，这些功能可能难以融入通用图形绘制库)

Answer 1

这是我的看法:

标记要放置标签的点

将它们分成距离至少为 2*size 的组他们之间

对于每个组，从右边开始尝试贴标签。

尝试将标签放在右侧或左侧。查看哪个导致垂直线的长度变短

如果没有关系，试着把它放在右边

除非是群尾，否则尽量往左边放

现在再次检查标签，看看是否可以在缩短垂直线长度的同时从一侧翻转到另一侧。

在我看来，应该会产生不错的输出。