物品放置算法

Question

我有一個「複雜」的問題，我可以在屏幕上隨機放置一些元素（黑色）頂部的工具提示（橙色）。工具提示是一個大的正方形，在它的四個邊中間有一個三角形指向元素方向。默認情況下，三角形將位於元素的中間，但只要靠近它就可以移動，所以我們不能輕易理解它是指這個元素而不是另一個元素。

問題是，工具提示不得彼此重疊，並且不能超出屏幕。

Image of my tooltip problem

我想到了第一次提示每次向配售（倒三角），它們的默認位置，然後檢查它們是否出屏幕或重疊另外一個，如果是的話，嘗試另一個位置。但是使用這種技術（這可能是最簡單的方法），但我不能保證最好的放置位置，因爲一旦放置了工具提示，如果另一個不適合任何地方，我不會替換他，否則會變得太複雜。

有人有任何提示/想法如何處理這種類型的問題？

謝謝！

Answer 1

這看起來像地圖標記問題的一個實例。維基百科有an article about it。

Answer 2

您可以使用某種排斥電荷的物理模擬來放置所有工具提示，類似於某些algorithms中繪製圖形所做的工作提示。您可以將每個工具提示建模爲一個附有柔軟彈簧的物體到其黑盒，同時模擬所有工具提示之間以及工具提示和圖像邊緣之間的強排斥力。你計算所有的力並迭代地移動工具提示，直到所有的位置收斂。你可以玩把力尺度作爲反平方，逆立方等來找到好的結果。

這可能有點工作要實現，但應該給簡單的情況下體面的結果。確保永遠存在一個好的解決方案可能是不可能的，因爲如果你添加了太多的工具提示，你的圖像就會滿了。