給定一組隨機點的隨機鏈接，如何定位它們使其鏈接線不相交？

Question

我有一組點，座標不是預先確定的，我可以在創建它們時設置它們，但它們的鏈接是預先確定的。一個點可以有一個或多個鏈接，但不能爲零。

我希望能夠在這些點之間的這些連接線不會相交的位置生成這些點的視覺表示。從我迄今在研究中學到的知識來看，我認爲這與平面圖有些類似，但是隻有一個鏈接會有點，而我不確定平面圖能夠表示這些點。

我不確定是否有一種很好的方法來做我想做或不做的事情，但我承認數學不是我的強大套件。到目前爲止，我的'最好'想法是以某種方式檢測這些交叉點，然後以某種方式移動點，以便以某種方式將交叉點位置考慮在內以重新定位它們，以便不發生該特定交叉點....並循環並執行此操作每個點直到沒有更多的交點被檢測到。然而，我可以使用某種更有效的數學算法，但我完全不知道。

我對這裏的所有建議感興趣，不管它是否有效。

Answer 1

這不是一個簡單的問題。這裏是Google search results for 「algorithm to draw a planar graph」。 Boost C++庫有some support for drawing planar embeddings，包括an example。這些當然使用C++，而不是你用C＃標記問題。