物品放置算法

Question

我有一个“复杂”的问题，我可以在屏幕上随机放置一些元素（黑色）顶部的工具提示（橙色）。工具提示是一个大的正方形，在它的四个边中间有一个三角形指向元素方向。默认情况下，三角形将位于元素的中间，但只要靠近它就可以移动，所以我们不能轻易理解它是指这个元素而不是另一个元素。

问题是，工具提示不得彼此重叠，并且不能超出屏幕。

Image of my tooltip problem

我想到了第一次提示每次向配售（倒三角），它们的默认位置，然后检查它们是否出屏幕或重叠另外一个，如果是的话，尝试另一个位置。但是使用这种技术（这可能是最简单的方法），但我不能保证最好的放置位置，因为一旦放置了工具提示，如果另一个不适合任何地方，我不会替换他，否则会变得太复杂。

有人有任何提示/想法如何处理这种类型的问题？

谢谢！

Answer 1

这看起来像地图标记问题的一个实例。维基百科有an article about it。

Answer 2

您可以使用某种排斥电荷的物理模拟来放置所有工具提示，类似于某些algorithms中绘制图形所做的工作提示。您可以将每个工具提示建模为一个附有柔软弹簧的物体到其黑盒，同时模拟所有工具提示之间以及工具提示和图像边缘之间的强排斥力。你计算所有的力并迭代地移动工具提示，直到所有的位置收敛。你可以玩把力尺度作为反平方，逆立方等来找到好的结果。

这可能有点工作要实现，但应该给简单的情况下体面的结果。确保永远存在一个好的解决方案可能是不可能的，因为如果你添加了太多的工具提示，你的图像就会满了。